Avl - деревья
Цель: изучить Avl - деревья
На прошлом занятии мы изучили упорядоченные бинарные деревья(УБД). Однако при некоторых данных дерево может оказаться вырожденным. Тогда его высота будет n и доступ к данным существенно замедлится.
 |
В этом разделе мы рассмотрим модифицированный класс деревьев, обладающий всеми преимуществами упорядоченных бинарных деревьев и никогда не вырождающихся. Они называются сбалансированными или AVL - деревьями. AVL - деревьями они названы в честь их изобретателей Адельсона - Вельского и Ландиса.
Высотой некоторого бинарного дерева является максимальный уровень его листьев.
Баланс некоторого узла определяется как высота его левого поддерева минус высота его правого поддерева.
Дерево называется сбалансированным тогда и только тогда, когда для каждого узла высота его двух поддеревьев различается не более чем на 1.
|
АVL - дерево с такими же значениями, как и в узлах предыдущего дерева можно представить так.
Следует заметить, что сбалансированные деревья очень эффективны для поиска. Предположим у нас сбалансированное дерево и упорядоченное бинарное дерево, которое вырождено, оба эти дерева содержат 10000 узлов. Так, например, упорядоченном бинарном дереве следует просмотреть 9999 уровней дерева прежде, чем он найдет самый крайний правый узел, а сбалансированном дереве 8 уровней.
Давайте расставим балансы для каждого узла для следующего дерева.
|
Все идет хорошо до тех пор пока мы ищем узлы в дереве, но как только мы захотим вставить узел в это дерево или удалить узел из такого дерева, как его сбалансированность нарушится. Давайте при вставке и удалении будет модифицировать дерево, так чтобы сбалансированность его сохранялась.
Мы рассмотрим только вставку в сбалансированное дерево, удаление очень сложное и поэтому его мы рассматривать не будем.
Включение в сбалансированное дерево
|
Возможны 3 случая:
- hL = hR: L и R становятся неравной высоты, но критерий сбалансированности не нарушается
- hL < hR: L и R приобретают равную высоту, т.е. сбалансированность даже улучшается
- hL > hR: критерий сбалансированности нарушается, и дерево нужно трансформировать, такая перестройка называется поворотом.
 |
 |
 |
Поворот должен удовлетворять следующим требованиям:
- Прохождение трансформированного дерева в симметричном порядке должно быть таким же, как и для первоначального дерева (т.е. трансформированное дерево должно оставаться деревом бинарного поиска)
- Трансформированное дерево должно быть сбалансированным
|
Одинарный поворот вправо происходит тогда, когда родительский узел Р и его левый сын LC начинают перевешивать влево после включения узла в позицию X. В результате такого поворота LC замещает своего родителя, который становится правым сыном. Бывая правое поддерево узла LC (ST) присоединяется к Р в качестве левого поддерева. Это сохраняет упорядоченность, так как узлы в ST больше или равны узлу LC, но меньше узла Р. Поворот уравновешивает как родителя, так и его левого сына.
|
|
| ъ |
 |
 |
Двойной поворот вправо происходит тогда, когда родительский узел (Р) становится перевешивающим влево, а его левый сын (LC) - перевешивающим вправо. NP - корень правого перевешивающего дерева узла LC. Тогда в результате поворота узел NP замещает родительский узел.
 |
 |
 |
 |
 |
 |
Процесс включения узла состоит из последовательности таких 3 этапов:
- Следовать по пути поиска, пока не окажется, что ключа нет в дереве
- Включить новый узел и определить новый показатель сбалансированности
- Пройти обратно по пути поиска и проверить показатель сбалансированности у каждого узла
Принцип работы алгоритма показан на рисунках.
Рассмотрим бинарное дерево (а), которое состоит только из двух узлов.
Включение ключа 7 вначале дает несбалансированное дерево (т. е. линейный список). Его балансировка требует однократного - левого поворота, давая в результате идеально сбалансированное дерево (b).
 |
Последующее включение узлов 2 и 1 дает несбалансированное поддерево с корнем 4. Это поддерево балансируется однократным правым поворотом (d).
 |
 |
Далее включение ключа 3 сразу нарушает критерий сбалансированности в корневом узле 5. Сбалансированность теперь восстанавливается с помощью более сложного двукратного поворота направо и налево; результатом является дерево (е).
|
|
Теперь при следующем включении потерять сбалансированность может лишь узел 5. Включение узла 6 должно привести двукратному повороту налево и направо.
Давайте напишем программу поиска и вставки узла.
Тип узла будет
Type node = record
Key: integer;
Left, right: ref;
Bal: -1..1;
End;
procedure search(x: integer; var p: ref;
var h: boolean);
var
p1, p2: ref; {h = false}
begin
if p = nil then
begin {узла нет в дереве; включить его}
new(p);
h := true;
with p^ do
begin
key := x;
count := 1;
left := nil;
right := nil;
bal := 0;
end
end
else
if x < p^.key then
begin
search(x, p^.left, h);
if h then {выросла левая ветвь}
case p^.bal of
1: begin p^.bal := 0; h := false end ;
0: p^.bal := -1;
-1: begin {балансировка}
p1:= p^.left;
if p1^.bal = -1 then
begin {однократный правый поворот}
p^.left := p1^.right;
p1^.right := p;
p^.bal := 0;
p := p1
end
else
begin {двукратный правый - левый поворот}
p2 := p1^.right;
p1^.right := p2^.left;
p2^.left :=p1;
p^.left := p2^.right;
p2^. right := p;
if p2^.bal =-1 then p^.bal:=1 else p^.bal := 0;
it p2^.bal = 1 then p1^.bal := -1 else p1.^bal :=0;
p :=p2;
end;
p^.bal := 0;
h := false;
end
end
end
else
if x > p^.key then
begin
search(x, p^.right, h);
if h then {выросла правая ветвь}
case p^.bal of
-1: begin p^.bal := 0; h :=false; end ;
0: p^.bal := 1;
1: begin {балансировка}
p1 := p^.right;
if р1^.bal =1 then
begin {однократный левый поворот}
p^.right := p1^.left;
p1^.left := p;
p^.bal := 0;
p := p1;
end
else
begin {двукратный левый - правый поворот}
p2 := p1^.left;
p1^.left := p2^.right;
p2^.right := p1;
p^.right := p2^.left;
p2^.left := p;
if p2^.bal = 1 then p^.bal := -1 else p^.bal:=0;
if p2^.bal = -1 then p1^.bal := 1 else p1^.bal: = 0;
p :=p2;
end ;
p^.bal := 0; h:= false;
end
end
end
else
begin
p^.count := p^.count + 1; h :=false;
end
end
Итак, на сегодняшнем занятии мы рассмотрели сбалансированные деревья.
