НОВОСТИ
Новости сайта
О САЙТЕ
Содержание сайта
БИБЛИОТЕКА
Структуры и алгоритмы
ОБРАТНАЯ СВЯЗЬ
Связь с автором
Структуры и алгоритмы

Avl - деревья

Цель: изучить Avl - деревья

На прошлом занятии мы изучили упорядоченные бинарные деревья(УБД). Однако при некоторых данных дерево может оказаться вырожденным. Тогда его высота будет n и доступ к данным существенно замедлится.

avl__001.gif (1222 bytes)

В этом разделе мы рассмотрим модифицированный класс деревьев, обладающий всеми преимуществами упорядоченных бинарных деревьев и никогда не вырождающихся. Они называются сбалансированными или AVL - деревьями. AVL - деревьями они названы в честь их изобретателей Адельсона - Вельского и Ландиса.

Высотой некоторого бинарного дерева является максимальный уровень его листьев.

Баланс некоторого узла определяется как высота его левого поддерева минус высота его правого поддерева.

Дерево называется сбалансированным тогда и только тогда, когда для каждого узла высота его двух поддеревьев различается не более чем на 1.

avl__002.gif (1038 bytes)

АVL - дерево с такими же значениями, как и в узлах предыдущего дерева можно представить так.

Следует заметить, что сбалансированные деревья очень эффективны для поиска. Предположим у нас сбалансированное дерево и упорядоченное бинарное дерево, которое вырождено, оба эти дерева содержат 10000 узлов. Так, например, упорядоченном бинарном дереве следует просмотреть 9999 уровней дерева прежде, чем он найдет самый крайний правый узел, а сбалансированном дереве 8 уровней.

Давайте расставим балансы для каждого узла для следующего дерева.

avl__003.gif (7578 bytes)

Все идет хорошо до тех пор пока мы ищем узлы в дереве, но как только мы захотим вставить узел в это дерево или удалить узел из такого дерева, как его сбалансированность нарушится. Давайте при вставке и удалении будет модифицировать дерево, так чтобы сбалансированность его сохранялась.

Мы рассмотрим только вставку в сбалансированное дерево, удаление очень сложное и поэтому его мы рассматривать не будем.

Включение в сбалансированное дерево

avl__005.gif (1727 bytes)

Возможны 3 случая:

  1. hL = hR: L и R становятся неравной высоты, но критерий сбалансированности не нарушается
  2. hL < hR: L и R приобретают равную высоту, т.е. сбалансированность даже улучшается
  3. hL > hR: критерий сбалансированности нарушается, и дерево нужно трансформировать, такая перестройка называется поворотом.
avl__006.gif (2061 bytes)
avl__007.gif (2442 bytes)
avl__008.gif (2647 bytes)

Поворот должен удовлетворять следующим требованиям:

  1. Прохождение трансформированного дерева в симметричном порядке должно быть таким же, как и для первоначального дерева (т.е. трансформированное дерево должно оставаться деревом бинарного поиска)
  2. Трансформированное дерево должно быть сбалансированным
avl__009.gif (10656 bytes)

Одинарный поворот вправо происходит тогда, когда родительский узел Р и его левый сын LC начинают перевешивать влево после включения узла в позицию X. В результате такого поворота LC замещает своего родителя, который становится правым сыном. Бывая правое поддерево узла LC (ST) присоединяется к Р в качестве левого поддерева. Это сохраняет упорядоченность, так как узлы в ST больше или равны узлу LC, но меньше узла Р. Поворот уравновешивает как родителя, так и его левого сына.

avl__011.gif (5446 bytes)
avl__013.gif (5371 bytes)
avl__015.gif (1587 bytes)
avl__016.gif (2101 bytes)
avl__017.gif (1861 bytes)

Двойной поворот вправо происходит тогда, когда родительский узел (Р) становится перевешивающим влево, а его левый сын (LC) - перевешивающим вправо. NP - корень правого перевешивающего дерева узла LC. Тогда в результате поворота узел NP замещает родительский узел.

avl__018.gif (6015 bytes)
avl__020.gif (6432 bytes)
avl__022.gif (2559 bytes)
avl__023.gif (2687 bytes)
avl__024.gif (6195 bytes)
avl__026.gif (6374 bytes)

Процесс включения узла состоит из последовательности таких 3 этапов:

  1. Следовать по пути поиска, пока не окажется, что ключа нет в дереве
  2. Включить новый узел и определить новый показатель сбалансированности
  3. Пройти обратно по пути поиска и проверить показатель сбалансированности у каждого узла

Принцип работы алгоритма показан на рисунках.

Рассмотрим бинарное дерево (а), которое состоит только из двух узлов.

avl__028.gif (1473 bytes)

Включение ключа 7 вначале дает несбалансированное дерево (т. е. линейный список). Его балансировка требует однократного - левого поворота, давая в результате идеально сбалансированное дерево (b).

avl__030.gif (1942 bytes)

Последующее включение узлов 2 и 1 дает несбалансированное поддерево с корнем 4. Это поддерево балансируется однократным правым поворотом (d).

avl__032.gif (2483 bytes)
avl__034.gif (2928 bytes)

Далее включение ключа 3 сразу нарушает критерий сбалансированности в корневом узле 5. Сбалансированность теперь восстанавливается с помощью более сложного двукратного поворота направо и налево; результатом является дерево (е).

avl__034.gif (2928 bytes)
avl__036.gif (3397 bytes)

Теперь при следующем включении потерять сбалансированность может лишь узел 5. Включение узла 6 должно привести двукратному повороту налево и направо.

avl__038.gif (3963 bytes)

Давайте напишем программу поиска и вставки узла.

Тип узла будет

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

Итак, на сегодняшнем занятии мы рассмотрели сбалансированные деревья.

Почта /// Структуры и алгоритмы