Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
22 слайда
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
275.62 kB
Просмотров:
62
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![ИСДП ИСДП Обеспечивает](/documents_6/7cc21b5506040b71448cfbb9d3147d85/img0.jpg)
Содержание слайда: ИСДП
ИСДП
+ Обеспечивает минимальное среднее время поиска.
- Перестройка дерева после случайного включения вершины – довольно сложная операция.
СДП
+ Процедура построения достаточно проста.
- Среднее время поиска на 39% больше, чем у ИСДП
(в худшем случае может выродиться в список).
№2 слайд![АВЛ-деревья Возможное](/documents_6/7cc21b5506040b71448cfbb9d3147d85/img1.jpg)
Содержание слайда: АВЛ-деревья
Возможное промежуточное решение - ввести менее строгий критерий сбалансированности.
Определение предложено в 1962 году
Г.М. Адельсон-Вельским и Е.М. Ландисом.
Они предложили балансировать дерево по высоте, а не по размеру.
№3 слайд![Определение. Дерево поиска](/documents_6/7cc21b5506040b71448cfbb9d3147d85/img2.jpg)
Содержание слайда: Определение. Дерево поиска называется
Определение. Дерево поиска называется
АВЛ-деревом, если для каждой его вершины высоты левого и правого поддеревьев отличается не больше, чем на единицу.
Замечание:
1) ИСДП является также и АВЛ-деревом
верно
2) АВЛ-дерево является также и ИСДП
не верно
Преимущества:
1) Определение сбалансированности простое;
2) Приводит к простой процедуре перестройки дерева;
3) Среднее время поиска близко к ИСДП.
№4 слайд![Какое дерево является](/documents_6/7cc21b5506040b71448cfbb9d3147d85/img3.jpg)
Содержание слайда: Какое дерево является АВЛ-деревом?
№5 слайд![Плохие АВЛ-деревья](/documents_6/7cc21b5506040b71448cfbb9d3147d85/img4.jpg)
Содержание слайда: «Плохие» АВЛ-деревья
Адельсон-Вельский и Ландис доказали теорему которая, гарантирует, что
АВЛ-дерево никогда не будет по высоте превышать ИСДП больше, чем на 45% независимо от количества вершин:
log(n+1) ≤ hАВЛ(n) < 1,44 log(n+2) – 0,328
Лучший случай ИСДП Плохие АВЛ-деревья
№6 слайд![Определение. Определение.](/documents_6/7cc21b5506040b71448cfbb9d3147d85/img5.jpg)
Содержание слайда: Определение.
Определение.
«Плохим» будем называть АВЛ-дерево, которое имеет наименьшее чисто вершин при фиксированной высоте.
Какова структура «плохого» АВЛ-дерева?
Построение: возьмем фиксированную высоту h и построим АВЛ-дерево с минимальным количеством вершин.
Обозначим такое дерева через Th
Тогда T0 – пустое дерево, T1 - дерево с одной вершиной и т.д.
№7 слайд![h h h h h h h h](/documents_6/7cc21b5506040b71448cfbb9d3147d85/img6.jpg)
Содержание слайда: h=1 h=2 h=3
h=1 h=2 h=3
h=4 h=5
№8 слайд![Заметим, что Заметим, что Т Т](/documents_6/7cc21b5506040b71448cfbb9d3147d85/img7.jpg)
Содержание слайда: Заметим, что
Заметим, что
Т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 слайд![Построение АВЛ-дерева](/documents_6/7cc21b5506040b71448cfbb9d3147d85/img8.jpg)
Содержание слайда: Построение АВЛ-дерева
Рассмотрим, что может произойти при включении в сбалансированное по высоте дерево новой вершины.
Пусть добавляется вершина в левое поддерево.
Возможны три случая:
Если hL < hR , то hL = hR
Если hL = hR , то hL > hR
Если hL > hR , то hL > hR - нарушение баланса и
дерево необходимо перестроить.
№10 слайд![Построение АВЛ-дерева Пусть](/documents_6/7cc21b5506040b71448cfbb9d3147d85/img9.jpg)
Содержание слайда: Построение АВЛ-дерева
Пусть добавляется вершина в правое поддерево.
Возможны три случая:
Если hL > hR , то hL = hR
Если hL = hR , то hL < hR
Если hL < hR , то hL < hR - нарушение
баланса и дерево необходимо
перестроить.
№11 слайд![Рассмотрим перестроение](/documents_6/7cc21b5506040b71448cfbb9d3147d85/img10.jpg)
Содержание слайда: Рассмотрим перестроение АВЛ-дерева
на простых примерах
№12 слайд![](/documents_6/7cc21b5506040b71448cfbb9d3147d85/img11.jpg)
№13 слайд![Идея алгоритма построения](/documents_6/7cc21b5506040b71448cfbb9d3147d85/img12.jpg)
Содержание слайда: Идея алгоритма построения АВЛ-дерева
Идея алгоритма построения АВЛ-дерева
Вначале добавим новую вершину в дерево так же как в случайное, т.е. проходим по пути поиска до нужного места включения в качестве листовой вершины.
Двигаясь назад по пути поиска будем искать вершину, в которой нарушился баланс, т.е. высота левого и правого поддерева стала отличаться больше, чем на единицу.
Если такая вершина найдена, то изменим структуру дерева для восстановления баланса.
№14 слайд![Задачи при перестроении](/documents_6/7cc21b5506040b71448cfbb9d3147d85/img13.jpg)
Содержание слайда: Задачи при перестроении АВЛ-дерева
1) Как осуществить движение назад по пути поиска?
2) Как определить нарушение баланса?
3) Как восстанавливать баланс?
Решение:
а) Использовать рекурсию, которая позволит хранить адреса всех пройденных вершин по пути поиска и автоматически в них возвращаться на обратном пути рекурсии.
б) введем в каждую вершину дополнительный показатель баланса Balance:
№15 слайд![При включении новой вершины](/documents_6/7cc21b5506040b71448cfbb9d3147d85/img14.jpg)
Содержание слайда: При включении новой вершины её баланс равен нулю. При движении назад по пути поиска показатель баланса для всех вершин пересчитывается, причем не нужно просматривать все поддеревья, только путь поиска.
При включении новой вершины её баланс равен нулю. При движении назад по пути поиска показатель баланса для всех вершин пересчитывается, причем не нужно просматривать все поддеревья, только путь поиска.
Нарушение баланса возможно только в одной вершине и один поворот полностью восстанавливает структуру АВЛ-дерева.
Балансировка выполняется с помощью поворотов дерева: LL, LR, RL, RR.
№16 слайд![](/documents_6/7cc21b5506040b71448cfbb9d3147d85/img15.jpg)
№17 слайд![](/documents_6/7cc21b5506040b71448cfbb9d3147d85/img16.jpg)
№18 слайд![Введем логическую переменную](/documents_6/7cc21b5506040b71448cfbb9d3147d85/img17.jpg)
Содержание слайда: Введем логическую переменную 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) <LL-поворот> Rost=нет
ELSE <LR-поворот> Rost=нет
FI
FI
FI
FI
№19 слайд![ELSE IF p-- gt Data lt D](/documents_6/7cc21b5506040b71448cfbb9d3147d85/img18.jpg)
Содержание слайда: 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) <RR-поворот> Rost = нет
ELSE <RL-поворот> Rost = нет
FI
FI
FI
FI
ELSE < Вершина есть в дереве >
FI
FI
№20 слайд![B E F A D C](/documents_6/7cc21b5506040b71448cfbb9d3147d85/img19.jpg)
Содержание слайда: B 9 2 4 1 7 E F A D C 3 5 8 6
№21 слайд![B E F A D C](/documents_6/7cc21b5506040b71448cfbb9d3147d85/img20.jpg)
Содержание слайда: B 9 2 4 1 7 E F A D C 3 5 8 6
№22 слайд![B E F A D C](/documents_6/7cc21b5506040b71448cfbb9d3147d85/img21.jpg)
Содержание слайда: B 9 2 4 1 7 E F A D C 3 5 8 6