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

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

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

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

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

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

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

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

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

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

Содержание слайда: Абстрактные структуры данных. Деревья. Двоичные деревья поиска. Двоичное дерево поиска (ДДП) – это бинарное дерево такое, что каждому узлу предписан ключ, причем в левом поддереве ключи всегда меньше, чем в узле, а в правом – не меньше.

Содержание слайда: Абстрактные структуры данных. Деревья. Двоичные деревья поиска. Операции в двоичном дереве поиска Поиск ключа FindKey(key) Найти предыдущий ключ FindPrev(key) Найти следующий ключ FindNext(key) Добавить вершину Add(key) Удалить вершину Delete(key) Найти минимальный и максимальный ключ Min(), Max()

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

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

Содержание слайда: Абстрактные структуры данных. Операции в ДДП. Min()/Max() Ищется самый левый/правый лист в дереве. Модификация операции: FindMin(key)/FindMax(key) – поиск минимального/ максимального ключа в левом/правом поддереве для заданного ключа key. Сложность алгоритма – O(h).

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

Содержание слайда: Абстрактные структуры данных. Операции в ДДП. Delete(key) в. А имеет 2 поддерева. осуществляем поиск FindNext(A); пусть это вершина В; вершина В не имеет левого поддерева; удаляем вершину А; записываем ключ В вместо А; удаляем вершину В из старого места в соответствии с п.а или п.б. Сложность алгоритма – O(h).

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

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

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

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

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

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

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