АВЛ-деревья

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

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

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

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

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

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

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

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

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

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

RR - поворот
RL - поворот

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

Задачи при перестроении АВЛ-дерева

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

LL – поворот //RR – поворот симметричен
Т1
Т2
Т3
Т1
Т2
Т3
p
q
p
LL-поворот
q = p-->Left
p-->Bal = 0
q-->Bal = 0
p-->Left = q-->Right
q-->Right = p
p = q

LR – поворот //RL – поворот симметричен
Т1
Т2
Т3
p
q
LR-поворот
q = p-->Left
r = q-->Right
IF (r-->Bal < 0)
p-->Bal = 1
ELSE p-->Bal = 0
FI
IF (r-->Bal > 0)
q-->Bal = -1
ELSE q-->Bal = 0
FI
q-->Right = r-->Left
p-->Left = r-->Right
r-->Left = q;
r-->Right = p;
p = r;
Т4
r
Т1
Т2
Т3
Т4

Введем логическую переменную 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

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

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

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