Перед рассмотрением способов в этом разде-
ле обсуждаются некоторые детали добавления узлов к AVL-дереву с помощью
Delphi.
Кроме обычных полей Lef tChild и RightChild класс TAVLNode содержит
также поле Balance, которое указывает, какое поддерево в узле длиннее. Пере-
менная Balance принимает значение Lef tHeavy, если левое поддерево длиннее,
RightHeavy, если правое поддерево длиннее, и Balanced, если оба поддерева
имеют одинаковую глубину.
type
TBalance = (LeftHeavy, Balanced, RightHeavy) ;
TAVLNode = class(TObject)
private
public
Id : Integer;
LeftChild, RightChild : TAVLNode;
Balance : TBalance;
Position : TPoint;
// Код опущен...
end;
Процедура AddNode, показанная ниже, рекурсивно обращается к дереву в по-
исках места для нового элемента. Дойдя до нижнего уровня дерева, процедура со-
здает новый узел и добавляет его к дереву.
Затем AddNode использует восходящую рекурсию, чтобы перебалансировать
дерево. Когда заканчивается рекурсивное обращение, процедура перемещается на-
зад по дереву. При каждом возврате она устанавливает параметр grew в значение
True, если поддерево, которое она покидает, стало глубже. Процедура использует
этот параметр, чтобы определить, сбалансировано ли рассматриваемое поддерево.
Если это не так, применяется соответствующее вращение, чтобы перебалансировать
поддерево.
Рис. 7.11. Различные виды вращения в AVL-деревьях
Предположим, процедура в настоящее время исследует узел X. Допустим, что
она только что возвратилась из правого поддерева ниже узла X и параметр grew
установлен в True, указывая на то, что правое поддерево стало глубже. Если подде-
ревья ниже узла X до этого имели одинаковую глубину, то правое поддерево теперь
длиннее левого. Дерево сбалансировано в этой точке, но поддерево с корнем в узле
X также выросло, так как его правое поддерево стало длиннее.
Если левое поддерево ниже узла X было длиннее правого, то сейчас левое и пра-
вое поддеревья имеют одинаковую глубину. Глубина поддерева с корнем в узле X
не изменилась - она также равна глубине левого поддерева плюс единица. В этом
случае процедура AddNode установит переменную grew в значение False, указы-
вая, что дерево сбалансировано.
И наконец, если правое поддерево ниже узла X было до этого длиннее левого,
новый узел разбалансирует дерево в узле X. Процедура AddNode вызывает проце-
дуру RebalanceRightGrew, чтобы перебалансировать дерево. Данная процедура
выполняет левое вращение или вращение вправо-влево, в зависимости от конкрет-
ной ситуации.
Процедура AddNode работает по такому же сценарию, если новый элемент до-
бавляется в левое поддерево. Следующий код показывает выполнение процедур
AddNode и RebalanceRightGrew. Процедура RebalanceLef tGrew аналогич-
на процедуре RebalanceRightGrew.
procedure TAVLTree.AddNode(var parent : TAVLNode; new_id : Integer;
var grew : Boolean);
begin
// Если это основание дерева, то создаем новый узел и заставляем
// родительский_узел указывать на новый.
if (parent = nil) then
begin
parent := TAVLNode.Create;
parent.Id := new_id;
parent.Balance := Balanced;
grew := True;
expend;
// Продолжаем двигаться вниз по соответствующему поддереву.
if (new_id<=parent.Id) then
begin
// Вставка дочернего узла в левое поддерево.
AddNode(parent.LeftChiId,new_id,grew);
// Нужна ли перебалансировка?
if (not grew) then exit;
if (parent.Balance = RightHeavy) then
begin
// Правое поддерево было длиннее. Левое поддерево выросло,
// поэтому дерево сбалансировано.
parent.Balance := Balanced;
grew := False;
end else if (parent.Balance = Balanced) then
begin
// Был баланс. Левое поддерево выросло,
// поэтому левое поддерево длиннее. Дерево все еще
// сбалансировано, но оно выросло, поэтому необходимо
// продолжить проверку баланса еще выше.
parent.Balance := LeftHeavy;
end else begin
// Левое поддерево длиннее. Оно выросло, поэтому имеем
// разбалансированное дерево слева. Необходимо выполнить
// соответствующее вращение для перебалансирования.
RebalanceLeftGrew(parent);
grew := False;
end; // Конец проверки баланса родительского узла.
end else begin
// Вставка дочернего узла в правое поддерево.
AddNode(parent.RightChild,new_id,grew);
// Нужна ли перебалансировка?
if (not grew) then exit;
if (parent.Balance = LeftHeavy) then
begin
// Левое поддерево было длиннее. Правое поддерево выросло,
// поэтому дерево сбалансировано.
parent.Balance := Balanced;
grew := False;
end else if (parent.Balance = Balanced) then
begin
// Был баланс. Правое поддерево выросло,
// поэтому оно длиннее. Дерево все еще сбалансировано,
// но оно выросло, поэтому необходимо продолжить проверку
// баланса еще выше.
parent.Balance := RightHeavy;
end else begin
// Правое поддерево длиннее. Оно выросло, поэтому имеем
// разбалансированное дерево справа. Необходимо выполнить
// соответствующий сдвиг для перебалансирования.
RebalanceRightGrew(parent);
grew := false;
end; // Конец проверки баланса родительского узла.
end; // Конец if (левое поддерево) ... else (правое поддерево) ..
end;
// Выполнение левого вращения или вращения вправо-влево
// для перебалансирования дерева в данном узле.
/procedure TAVLTree.RebalanceRightGrew(var parent : TAVLNode);
var
child, grandchild : TAVLNode;
begin
child := parent.RightChild;
if (child.Balance= RightHeavy) then
begin
// Вращение влево.
parent.RightChild := child.LeftChild;
child.LeftChild := parent;
parent.Balance := Balanced;
parent := child;
end else begin
// Вращение вправо-влево.
Grandchild := child.LeftChild;
child.LeftChild := grandchild.RightChild;
grandchild.RightChild := child;
parent.RightChild := grandchild.LeftChild;
grandchild.LeftChild := parent;
if (grandchild.Balance=RightHeavy) then
parent.Balance := LeftHeavy
else ,
parent.Balance := Balanced;
if (grandchild.Balance=LeftHeavy) then
child.Balance := RightHeavy
else
child.Balance := Balanced;
parent := grandchild;
end; // Конец if ... else ...
parent.Balance := Balanced;
end;
|
Главная
Каталог файлов
