Алгоритмы и анализ сложности. Структуры данных. Деревья. (Тема 2)

Сентябрь 7, 2022

Главная
Алгебра
Алгоритмы и анализ сложности. Структуры данных. Деревья. (Тема 2)

Содержание

2. Абстрактные структуры данных. Деревья. Дерево – связный граф, не содержащий циклов. Деревья: корневые и некорневые. Свойства
3. Абстрактные структуры данных. Деревья. Мат. модель корневого дерева – множество записей со следующими свойствами: 1. существует
4. Абстрактные структуры данных. Деревья. Позиционные деревья. Позиционное дерево – это либо пустое множество, либо дерево, которое
5. Абстрактные структуры данных. Деревья. Способы представления деревьев. Корневые деревья Общий случай: реализация с помощью списков. Вершина
6. Абстрактные структуры данных. Деревья. Способы представления деревьев. 4) Специальный способ организации позиционного дерева – с помощью
7. Абстрактные структуры данных. Деревья. Способы представления деревьев. Некорневые деревья Общий случай: с помощью списков смежности. Есть
8. Абстрактные структуры данных. Деревья. Способы представления деревьев. Некорневые деревья 2) Код Прюффера. Пусть вершины дерева пронумерованы
9. Абстрактные структуры данных. Деревья. Способы представления деревьев. Некорневые деревья 2) Восстановление дерева из кода Прюффера. Заводим
10. Абстрактные структуры данных. Деревья. Двоичные деревья поиска. Двоичное дерево поиска (ДДП) – это бинарное дерево такое,
11. Абстрактные структуры данных. Деревья. Двоичные деревья поиска. Операции в двоичном дереве поиска Поиск ключа FindKey(key) Найти
12. Абстрактные структуры данных. Операции в ДДП. Высотой дерева называется максимальная длина пути от корня дерева к
13. Абстрактные структуры данных. Операции в ДДП. FindNext(key)/ FindPrev(key) Выполняется операция FindKey(key). Пусть вершина А – результат
14. Абстрактные структуры данных. Операции в ДДП. Min()/Max() Ищется самый левый/правый лист в дереве. Модификация операции: FindMin(key)/FindMax(key)
15. Delete(key) Выполняется операция FindKey(key). Пусть вершина А – результат выполнения этой операции. Рассмотрим 3 случая: а.
16. Delete(key) в. А имеет 2 поддерева. осуществляем поиск FindNext(A); пусть это вершина В; вершина В не
17. Абстрактные структуры данных. Операции в ДДП. Выводы: Все интерфейсные операции имеют сложность O(h). Операции вставки и
18. Абстрактные структуры данных. Красно-черные деревья. Красно-черное дерево – это дерево двоичного поиска, у которого выполняются следующие
19. Абстрактные структуры данных. Красно-черные деревья. Примеры КЧ-деревьев Свойства сбалансированности КЧ-деревьев: для каждого узла высота левого и
20. Абстрактные структуры данных. Красно-черные деревья. Операция вращения ДДП Операция вращения выполняется за константное время и позволяет
21. Абстрактные структуры данных. Красно-черные деревья. Операция вставки в красно-черное дерево. Вставка элемента X как в обычное
22. Абстрактные структуры данных. Красно-черные деревья. Операция вставки в красно-черное дерево. а. красный «предок», красный «дядя» Перекрашиваем
24. Скачать презентацию

Слайд 2

Абстрактные структуры данных. Деревья.
Дерево – связный граф, не содержащий циклов.
Деревья: корневые

и некорневые.
Свойства некорневых деревьев.
Пусть Т – неориентированный граф, тогда следующие свойства эквивалентны:
Т – дерево
Для любых двух вершин Т существует единственный путь, соединяющий их
Т – связен, но распадается на 2 связных подграфа при удалении любого ребра
Т – связен, количество_вершин=количество_ребер+1
Т – ацикличен, количество_вершин=количество_ребер+1
Т – ацикличен, но добавление любого ребра порождает цикл

Слайд 3

Абстрактные структуры данных. Деревья.
Мат. модель корневого дерева – множество записей со

следующими свойствами:
1. существует выделенный узел (корень дерева);
2. остальные узлы распределены по непересекающимся подмножествам, которые снова образуют деревья:
- корни этих поддеревьев называются потомками
- количество этих поддеревьев называется степенью вершины
- корень поддерева с нулевой степенью называется листом
- уровень узла – длина пути от корня до этого узла
- все вершины на пути от корня к узлу называются предками этого узла
Если порядок поддеревьев имеет значение, то дерево называется упорядоченным.

Слайд 4

Абстрактные структуры данных. Деревья. Позиционные деревья.
Позиционное дерево – это либо пустое

множество, либо дерево, которое можно разбить на k+1 непересекающихся подмножеств, где k – это количество поддеревьев у каждого узла.
Двоичное дерево – частный случай позиционное при k=2.

Слайд 5

Абстрактные структуры данных. Деревья. Способы представления деревьев.
Корневые деревья
Общий случай: реализация с

помощью списков.
Вершина = информационное поле + список указателей на потомков
2) Двоичное дерево:
Вершина = информационное поле + левый указатель + правый указатель
3) Позиционное дерево:
Вершина = информационное поле + массив указателей

Слайд 6

Абстрактные структуры данных. Деревья. Способы представления деревьев.
4) Специальный способ организации позиционного

дерева – с помощью массива
Потомком s-ого узла в массиве являются вершины
ks+1, ks+2,…, ks+k.
Какие плюсы и минусы данной реализации?

Слайд 7

Абстрактные структуры данных. Деревья. Способы представления деревьев.
Некорневые деревья
Общий случай: с помощью

списков смежности.
Есть массив всех вершин дерева. Для каждой вершины есть список вершин, с которыми она связана.
Какой очевидный минус можно отметить?

Слайд 8

Абстрактные структуры данных. Деревья. Способы представления деревьев.
Некорневые деревья
2) Код Прюффера. Пусть

вершины дерева пронумерованы числами от 1 до N. Тогда кодом Прюффера называется последовательность из N-2 чисел, построенная по следующему алгоритму:
1. находим висячую вершину с минимальным номером
2. заносим смежную с ней вершину в выходную последовательность
3. повторяем пункты 1-2 N-3 раза
Выходная последовательность и будет кодом Прюффера.

Слайд 9

Абстрактные структуры данных. Деревья. Способы представления деревьев.
Некорневые деревья
2) Восстановление дерева из

кода Прюффера.
Заводим список неиспользованных вершин. Изначально в него помещаются все вершины дерева.
Выбираем из этого списка минимальное число, которого нет в коде Прюффера.
Строим ребро, соединяющее найденное число с первым числом из ряда Прюффера. Вычеркиваем числа из списка и из кода.
Повторяем пункт 2-3, пока не закончатся все числа в коде Прюффера.
Строим ребро, соединяющее оставшиеся 2 числа из списка неиспользованных вершин.

Слайд 10

Абстрактные структуры данных. Деревья. Двоичные деревья поиска.
Двоичное дерево поиска (ДДП) –

это бинарное дерево такое, что каждому узлу предписан ключ, причем в левом поддереве ключи всегда меньше, чем в узле, а в правом – не меньше.

Слайд 11

Абстрактные структуры данных. Деревья. Двоичные деревья поиска.
Операции в двоичном дереве поиска
Поиск

ключа FindKey(key)
Найти предыдущий ключ FindPrev(key)
Найти следующий ключ FindNext(key)
Добавить вершину Add(key)
Удалить вершину Delete(key)
Найти минимальный и максимальный ключ Min(), Max()

Слайд 12

Абстрактные структуры данных. Операции в ДДП.
Высотой дерева называется максимальная длина пути

от корня дерева к листу. Часто обозначается h.
FindKey(key)
Пошаговое сравнение искомого ключа с ключами в узлах ДДП.
Сложность алгоритма – O(h).
Add(key)
Прим. Предполагается, что все ключи уникальны.
Вставляем ключ key туда, где есть пустое место, которое удовлетворяет всем условиям дерева двоичного поиска.
Сложность алгоритма – O(h).

Слайд 13

Абстрактные структуры данных. Операции в ДДП.
FindNext(key)/ FindPrev(key)
Выполняется операция FindKey(key). Пусть вершина

А – результат выполнения этой операции.
Рассмотрим 2 случая:
а. А имеет правое поддерево. Искомое значение – минимальный элемент в правом поддереве.
б. А не имеет правого поддерева. Искомое значение – ближайший предок А, для которого А находится в левом поддереве.
Сложность алгоритма – O(h).

Слайд 14

Абстрактные структуры данных. Операции в ДДП.
Min()/Max()
Ищется самый левый/правый лист в дереве.
Модификация

операции:
FindMin(key)/FindMax(key) – поиск минимального/ максимального ключа в левом/правом поддереве для заданного ключа key.
Сложность алгоритма – O(h).

Слайд 15

Delete(key)
Выполняется операция FindKey(key). Пусть вершина А – результат выполнения этой операции.
Рассмотрим

3 случая:
а. А не имеет потомков. Удаление вершины А – просто уничтожение вершины без изменений остального дерева.
б. А имеет ровно 1 потомка. Удаляем А и «подцепляем» её единственное поддерево к ближайшему предку вершины А.
Сложность алгоритма – O(h).

Абстрактные структуры данных. Операции в ДДП.

Слайд 16

Delete(key)
в. А имеет 2 поддерева.
осуществляем поиск FindNext(A); пусть это

вершина В;
вершина В не имеет левого поддерева;
удаляем вершину А; записываем ключ В вместо А; удаляем вершину В из старого места в соответствии с п.а или п.б.
Сложность алгоритма – O(h).

Абстрактные структуры данных. Операции в ДДП.

Слайд 17

Абстрактные структуры данных. Операции в ДДП.
Выводы:
Все интерфейсные операции имеют сложность O(h).
Операции

вставки и удаления не заботятся о сбалансированности дерева.

Слайд 18

Абстрактные структуры данных. Красно-черные деревья.
Красно-черное дерево – это дерево двоичного поиска,

у которого выполняются следующие условия:
каждая вершина имеет цвет: красный или черный;
каждый лист имеет двух фиктивных потомков, которые окрашены в черный цвет; если у вершины только один реальный потомок, то второй будет фиктивным и окрашен в черный;
каждый красный узел имеет двух черных потомков;
на каждом пути от корня до листа содержится одинаковое количество черных вершин, которое называется черной высотой.

Слайд 19

Абстрактные структуры данных. Красно-черные деревья.
Примеры КЧ-деревьев
Свойства сбалансированности КЧ-деревьев:
для каждого узла высота

левого и правого поддерева отличается не более, чем в 2 раза;
высота КЧ-дерева, содержащего n вершин, не превосходит 2log2(n+1).

Слайд 20

Абстрактные структуры данных. Красно-черные деревья.
Операция вращения ДДП
Операция вращения выполняется за константное

время и позволяет преобразовать одно ДДП в другое ДДП (тот же набор ключей, но другая структура).
Прим. Данная операция позволяет выравнивать высоту ДДП.

Слайд 21

Абстрактные структуры данных. Красно-черные деревья.
Операция вставки в красно-черное дерево.
Вставка элемента X

как в обычное ДДП; новая вершина X помечается красным цветом. Она имеет двух фиктивных черных потомков.
При вставке новой красной вершины X могло нарушиться только 3-е условие (имеет красного предка).
Возможны 2 ситуации:
а. красный «предок», красный «дядя»
б. красный «предок», черный «дядя»

Слайд 22

Абстрактные структуры данных. Красно-черные деревья.
Операция вставки в красно-черное дерево.
а. красный «предок»,

красный «дядя»
Перекрашиваем «предка» и «дядю» в черный цвет, а «дедушку» вершины X – в черный. При этом черная высота дерева не изменится.
Необходимо проверить предка вершины В. Если он окажется красным, то применяем перекрашивание вершин дальше, пока не будет выполнено условие 3 из определения.

Алгоритмы и анализ сложности. Структуры данных. Деревья. (Тема 2)

Содержание

Абстрактные структуры данных. Деревья.Дерево – связный граф, не содержащий циклов.Деревья: корневые

Абстрактные структуры данных. Деревья.Мат. модель корневого дерева – множество записей со

Абстрактные структуры данных. Деревья. Позиционные деревья.Позиционное дерево – это либо пустое

Абстрактные структуры данных. Деревья. Способы представления деревьев.Корневые деревьяОбщий случай: реализация с

Абстрактные структуры данных. Деревья. Способы представления деревьев.4) Специальный способ организации позиционного

Абстрактные структуры данных. Деревья. Способы представления деревьев.Некорневые деревьяОбщий случай: с помощью

Абстрактные структуры данных. Деревья. Способы представления деревьев.Некорневые деревья2) Код Прюффера. Пусть

Абстрактные структуры данных. Деревья. Способы представления деревьев.Некорневые деревья2) Восстановление дерева из

Абстрактные структуры данных. Деревья. Двоичные деревья поиска.Двоичное дерево поиска (ДДП) –

Абстрактные структуры данных. Деревья. Двоичные деревья поиска.Операции в двоичном дереве поискаПоиск

Абстрактные структуры данных. Операции в ДДП.Высотой дерева называется максимальная длина пути

Абстрактные структуры данных. Операции в ДДП.FindNext(key)/ FindPrev(key)Выполняется операция FindKey(key). Пусть вершина

Абстрактные структуры данных. Операции в ДДП.Min()/Max()Ищется самый левый/правый лист в дереве.Модификация

Delete(key)Выполняется операция FindKey(key). Пусть вершина А – результат выполнения этой операции.Рассмотрим

Delete(key)в. А имеет 2 поддерева. осуществляем поиск FindNext(A); пусть это

Абстрактные структуры данных. Операции в ДДП.Выводы:Все интерфейсные операции имеют сложность O(h).Операции

Абстрактные структуры данных. Красно-черные деревья.Красно-черное дерево – это дерево двоичного поиска,

Абстрактные структуры данных. Красно-черные деревья.Примеры КЧ-деревьевСвойства сбалансированности КЧ-деревьев:для каждого узла высота

Абстрактные структуры данных. Красно-черные деревья.Операция вращения ДДПОперация вращения выполняется за константное

Абстрактные структуры данных. Красно-черные деревья.Операция вставки в красно-черное дерево.Вставка элемента X

Абстрактные структуры данных. Красно-черные деревья.Операция вставки в красно-черное дерево. а. красный «предок»,

Похожие презентации