Процедура RemoveFromNode/ удаляет элемент из дерева. Она рекурсивно об-
ращается к дереву и когда находит искомый узел, удаляет его. Если у него нет до-
черних узлов, то процедура заканчивается. Если имеется один дочерний узел, то
удаляемый узел заменяется его потомком.
Если узел имеет двух потомков, то процедура RemoveFromNode вызывает про-
цедуру ReplaceRightmost, чтобы заменить удаляемый узел крайним правым уз-
лом в его левой ветви. Выполнение процедуры ReplaceRightmost описано ранее, где
.
Основное отличие возникает при возврате из процедуры и рекурсивном
проходе вверх по дереву. При этом процедура ReplaceRightmost использует
восходящую рекурсию, чтобы проверить баланс в каждом узле дерева.
Когда вызов процедуры завершается, вызывающая ReplaceRightmost под-
программа использует процедуру RebalanceRightShrunk для проверки балан-
са во всех точках дерева. Так как ReplaceRightmost исследует правые ветви де-
рева, она всегда использует процедуру RebalanceRightShrunk.
Процедура RemoveFromNode первый раз вызывает ReplaceRightmost, зас-
тавляя ее двигаться влево вниз от удаляемого узла. Когда первый вызов процеду-
ры ReplaceRightmost завершается, RemoveFromNode вызывает процедуру
RebalanceLef tShrunk, чтобы проверить баланс во всех точках дерева.
После этого рекурсивные обращения к RemoveFromNode завершаются и про-
цедура выполняется обычным способом снизу вверх. Как и ReplaceRightmost,
RemoveFromNode использует восходящую рекурсию для проверки баланса дерева.
После каждого вызова этой процедуры следует вызов процедуры Rebalance-
RightShrunk или RebalanceLefShrunk в зависимости от того, по какому пути
происходит спуск по дереву.
Процедура RebalanceLef tShrunk аналогична RebalanceRightShrunk,
поэтому она не приведена в следующем коде.
// Удаление значения ниже выделенного узла.
procedure TAVLTree.RemoveFromNode(var node : TAVLNode;
target_id : Integer; var shrunk : Boolean);
var
target : TAVLNode;
begin
//X Если мы у основания дерева, то искомый узел находится не здесь.
if (node = nil) then
begin
shrunk := False;
expend;
if (target_id
begin
// Поиск левого поддерева.
RemoveFromNode(node.LeftChiId,target_id,shrunk);
if (shrunk) then RebalanceLeftShrunk(node,shrunk) ;
end else if (target_id>node.Id) then
begin
// Поиск правого поддерева.
RemoveFromNode(node.RightChild,target_id,shrunk);
if (shrunk) then RebalanceRightShrunk(node,shrunk);
end else begin
// Это искомый узел.
target : = node ;
if (node.RightChild = nil) then
begin
// Узел или не имеет дочерних, или имеет только левый.
node := node.LeftChild;
shrunk := True;
end else if (node. Lef tChild=ii) then
begin
// Узел имеет только правый дочерний.
node := node.RightChild;
shrunk := True;
end else begin
// Узел имеет два дочерних.
ReplaceRightmost(node,node.LeftChiId,shrunk);
if (shrunk) then RebalanceLeftShrunk(node,shrunk);
end; // Завершение удаления искомого узла.
// Удаление искомого узла.
target.LeftChild := nil;
target.Rightchild := nil;
target.Free;
end;
end;
// Замена искомого узла крайним правым потомком слева.
procedure TAVLTree.ReplaceRightmost(var target, repi : TAVLNode;
var shrunk : Boolean);
var
old_repl : TAVLNode;
begin
if (repl.RightChild = nil) then
begin
// repl - это узел, которым заменят искомый.
// Запоминание положения узла.
old_repl := repl;
// Замена repl его левым дочерним узлом.
repl := repl.LeftChild;
// Заменить искомый узел переменной old_repl.
old_repl.LeftChild := target.LeftChild;
old_repl.RightChild := target.RightChild;
old_repl.Balance := target.Balance;
target := old_repl;
shrunk := True;
end else begin
// Рассмотрение правых ветвей.
ReplaceRightmost(target,repl.RightChild,shrunk) ;
if (shrunk) then RebalanceRightShrunk(repl,shrunk);
end;
end;
// Выполнение вращения вправо или влево-вправо после сокращения
// правой ветви.
procedure TAVLTree.RebalanceRightShrunk(var node : TAVLNode;
var shrunk : Boolean);
var
child, grandchild :T AVLNode;
child_bal, grandchild_bal : TBalance;
begin
if (node.Balance = RightHeavy) then
begin
// Правое поддерево было длиннее. Теперь сбалансировано.
node.Balance := Balanced;
end else if (node.Balance=Balanced) then
begin
// Был баланс. Теперь левое поддерево длиннее.
node.Balance := LeftHeavy;
shrunk := False;
end else begin
// Левое поддерево было длиннее. Теперь разбалансировано.
Child := node.LeftChild;
child_bal := child.Balance;
if (child_bal<>RightHeavy) then
begin
// Вращение вправо.
node.LeftChild := child.RightChild;
child.RightChild := node;
if (child_bal = Balanced) then
begin
node.Balance := LeftHeavy;
child.Balance := RightHeavy;
shrunk := False;
end else begin
node.Balance := Balanced;
child.Balance := Balanced;
end;
node := child;
end else begin
// Вращение влево-вправо.
grandchild := child. RightChild;
grandchild_bal := grandchild.Balance;
child.RightChild := grandchild.LeftChild;
grandchild.LeftChild := child;
node.LeftChild := grandchild.RightChild;
grandchild.RightChild := node;
if (grandchild_bal = LeftHeavy) then
node.Balance := RightHeavy
else
node.Balance := Balanced;
if (grandchild_bal = RightHeavy) then
child.Balance := LeftHeavy
else
child.Balance := Balanced;
node := grandchild;
grandchild.Balance := Balanced;
end; // Конец if ... else .. .
end; // Конец if balanced/left heavy/left unbalanced
end;
http://ugabuga.ru/myphology.php славится своими богами, такими как Посейдон и Зевс
|
Главная
Каталог файлов
