АВЛ-деревья

Здесь вы можете просмотреть и скачать доклад по теме «АВЛ-деревья», размещенный в категории «Устройства и комплектующие», который поможет вам успешно провести свое мероприятие или подготовиться к занятию.

Информация о презентации

АВЛ-деревья
Раздел:Устройства и комплектующие
Слайдов:22
Слов:728
Символов:4935
Просмотров:37
Скачиваний:2
Загрузка:онлайн
Размер:275.62 kB
Тип:ppt / pptx для PowerPoint/Impress
Теги:#дерев, #вершин, #rost, #поиск, #баланс, #else, #построен, #высот, #исдп, #поддерев

Похожие презентации об устройстве и комплектующих

Готовые презентации об устройстве и комплектующих

Содержание слайда №1 (283 знака, 38 слов)

ИСДП ИСДП + Обеспечивает минимальное среднее время поиска. - Перестройка дерева после случайного включения вершины – довольно сложная операция. СДП + Процедура построения достаточно проста. - Среднее время поиска на 39% больше, чем у ИСДП (в худшем случае может выродиться в список).

Содержание слайда №2 (236 знаков, 31 слово)

АВЛ-деревья Возможное промежуточное решение - ввести менее строгий критерий сбалансированности. Определение предложено в 1962 году Г. М. Адельсон-Вельским и Е. М. Ландисом. Они предложили балансировать дерево по высоте, а не по размеру.

Содержание слайда №3 (437 знаков, 55 слов)

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

Содержание слайда №4 (34 знака, 4 слова)

Какое дерево является АВЛ-деревом?

Содержание слайда №5 (278 знаков, 36 слов)

«Плохие» АВЛ-деревья Адельсон-Вельский и Ландис доказали теорему которая, гарантирует, что АВЛ-дерево никогда не будет по высоте превышать ИСДП больше, чем на 45% независимо от количества вершин: log(n+1) ≤ hАВЛ(n) < 1, 44 log(n+2) – 0, 328 Лучший случай ИСДП Плохие АВЛ-деревья

Содержание слайда №6 (358 знаков, 48 слов)

Определение. Определение. «Плохим» будем называть АВЛ-дерево, которое имеет наименьшее чисто вершин при фиксированной высоте. Какова структура «плохого» АВЛ-дерева? Построение: возьмем фиксированную высоту h и построим АВЛ-дерево с минимальным количеством вершин. Обозначим такое дерева через Th Тогда T0 – пустое дерево, T1 - дерево с одной вершиной и т. д.

Содержание слайда №7 (31 знак, 8 слов)

h=1 h=2 h=3 h=1 h=2 h=3 h=4 h=5

Содержание слайда №8 (329 знаков, 50 слов)

Заметим, что Заметим, что Т3 = Т2+Т1 +1; Т4 = Т2+Т3 +1; Т5 = Т3+Т4+1. Для построения Тh для h>1 берем корень и два поддерева с минимальным количеством вершин - высотой Тh-1 и Тh-2 Тh = < Тh-1, х, Тh-2 > Алгоритм построения «плохих» АВЛ-деревьев напоминает построение чисел Фибоначчи, поэтому иногда их называют деревья Фибоначчи.

Содержание слайда №9 (312 знаков, 49 слов)

Построение АВЛ-дерева Рассмотрим, что может произойти при включении в сбалансированное по высоте дерево новой вершины. Пусть добавляется вершина в левое поддерево. Возможны три случая: Если hL < hR, то hL = hR Если hL = hR, то hL > hR Если hL > hR, то hL > hR - нарушение баланса и дерево необходимо перестроить.

Содержание слайда №10 (216 знаков, 36 слов)

Построение АВЛ-дерева Пусть добавляется вершина в правое поддерево. Возможны три случая: Если hL > hR, то hL = hR Если hL = hR, то hL < hR Если hL < hR, то hL < hR - нарушение баланса и дерево необходимо перестроить.

Содержание слайда №11 (54 знака, 6 слов)

Рассмотрим перестроение АВЛ-дерева на простых примерах

Содержание слайда №13 (467 знаков, 69 слов)

Идея алгоритма построения АВЛ-дерева Идея алгоритма построения АВЛ-дерева Вначале добавим новую вершину в дерево так же как в случайное, т. е. проходим по пути поиска до нужного места включения в качестве листовой вершины. Двигаясь назад по пути поиска будем искать вершину, в которой нарушился баланс, т. е. высота левого и правого поддерева стала отличаться больше, чем на единицу. Если такая вершина найдена, то изменим структуру дерева для восстановления баланса.

Содержание слайда №14 (389 знаков, 50 слов)

Задачи при перестроении АВЛ-дерева 1) Как осуществить движение назад по пути поиска? 2) Как определить нарушение баланса? 3) Как восстанавливать баланс? Решение: а) Использовать рекурсию, которая позволит хранить адреса всех пройденных вершин по пути поиска и автоматически в них возвращаться на обратном пути рекурсии. б) введем в каждую вершину дополнительный показатель баланса Balance:

Содержание слайда №15 (585 знаков, 82 слова)

При включении новой вершины её баланс равен нулю. При движении назад по пути поиска показатель баланса для всех вершин пересчитывается, причем не нужно просматривать все поддеревья, только путь поиска. При включении новой вершины её баланс равен нулю. При движении назад по пути поиска показатель баланса для всех вершин пересчитывается, причем не нужно просматривать все поддеревья, только путь поиска. Нарушение баланса возможно только в одной вершине и один поворот полностью восстанавливает структуру АВЛ-дерева. Балансировка выполняется с помощью поворотов дерева: LL, LR, RL, RR.

Содержание слайда №18 (531 знак, 89 слов)

Введем логическую переменную Rost которая будет показывать, что дерево увеличилось ( Rost =да) Введем логическую переменную Rost которая будет показывать, что дерево увеличилось ( Rost =да) Добавить АВЛ ( D - данные, vertex*&p ) IF (p = NULL) память (p); p-->Data = D; p-->Left = NULL; p-->Right = NULL; p-->Bal = 0; Rost = да; ELSE IF (p-->Data > D) Добавить АВЛ (D, p-->Left) IF (Rost = да) IF (p-->Bal > 0) p-->Bal = 0; Rost = нет ELSE IF (p-->Bal = 0) p-->Bal = 1 ELSE IF (p-->Left-->Bal < 0) Rost=нет ELSE Rost=нет FI FI FI FI

Содержание слайда №19 (308 знаков, 59 слов)

ELSE IF (p-->Data < D) Добавить АВЛ (D, p-->Right) ELSE IF (p-->Data < D) Добавить АВЛ (D, p-->Right) IF (Rost = да) IF (p-->Bal < 0) p-->Bal = 0; Rost = нет ELSE IF (p-->Bal = 0) p-->Bal = 1; Rost = да ELSE IF (p-->Right-->Bal > 0) Rost = нет ELSE Rost = нет FI FI FI FI ELSE < Вершина есть в дереве > FI FI

Содержание слайда №20 (29 знаков, 6 слов)

B 9 2 4 1 7 E F A D C 3 5 8 6

Содержание слайда №21 (29 знаков, 6 слов)

B 9 2 4 1 7 E F A D C 3 5 8 6

Содержание слайда №22 (29 знаков, 6 слов)

B 9 2 4 1 7 E F A D C 3 5 8 6