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
Итак, на сегодняшнем занятии мы рассмотрели
сбалансированные деревья. |
