12.3.2. Удаление из сбалансированного дерева
Удаление из сбалансированного дерева происходит более сложным образом, чем включение, хотя операция балансировки остается в основном такой же, как и при включении. Балансировка состоит из однократного или двукратного поворота узлов.
Простыми случаями являются удаление листов и узлов с одним потомком. Если же удаляемый узел имеет два поддерева, то он опять будет заменяться самым правым узлом его левого поддерева. Как и в случае включения, добавляется булевский параметр‑переменная shorter, означающий, что высота поддерева уменьшилась. Вопрос о перебалансировке рассматривается только при shorter=true. Значение true присваивается shorter в двух случаях: во‑первых, при нахождении и удалении узла и во‑вторых, когда балансировка уменьшает высоту поддерева. Процедура удаления узла имеет еще один булевский параметр‑переменную — success, свидетельствующий о том, был ли найден и удален узел. Этот параметр необходим для выдачи сообщения, что требуемый узел не найден. Процедура удаления узла из АВЛ‑дерева приведена в листинге 12.10.
Листинг 12.10. Процедура удаления узла из АВЛ‑дерева
procedure DeleteBalance(var t: TNode; i: TKey; var shorter: Boolean;
var success: Boolean);
var q: TNode;
procedure BalanceLeft(var t: TNode; var shorter: Boolean);
var p1,p2: TNode; bal1, bal2: Balance;
begin // BalanceLeft; левая ветвь стала короче
case t^.bal of
LongLeft: t^.bal:=Long0;
Long0: begin t^.bal:=LongRight; shorter:=false; end;
LongRight: begin // балансировка
p1:=t^.right; bal1:=p1^.bal;
if bal1 <> LongLeft then begin // однократный R-поворот
t^.right:=p1^.left; p1^.left:=t;
if bal1=Long0 then begin
t^.bal:=LongRight; p1^.bal:=LongLeft;
shorter:=false; end
else begin
t^.bal:=Long0; p1^.bal:=Long0; end;
t:=p1;
end
else begin // двукратный RL-поворот
p2:=p1^.left; bal2:=p2^.bal;
p1^.left:=p2^.right; p2^.right:=p1;
t^.right:=p2^.left; p2^.left:=t;
if bal2=LongRight then t^.bal:=LongLeft
else t^.bal:=Long0;
if bal2=LongLeft then p1^.bal:=LongRight
else p1^.bal:=Long0;
t:=p2; p2^.bal:=Long0;
end
end;
end;
end; // BalanceLeft
procedure BalanceRight(var t: TNode; var shorter: Boolean);
var p1,p2: TNode; bal1, bal2: Balance;
begin // BalanceRight; правая ветвь стала короче
case t^.bal of
LongRight: t^.bal:=Long0;
Long0: begin t^.bal:=LongLeft; shorter:=false; end;
LongLeft: begin // балансировка
p1:=t^.left; bal1:=p1^.bal;
if bal1 <> LongRight then begin // однократный L-поворот
t^.left:=p1^.right; p1^.right:=t;
if bal1=Long0 then begin
t^.bal:=LongLeft; p1^.bal:=LongRight;
shorter:=false; end
else begin
t^.bal:=Long0; p1^.bal:=Long0; end;
t:=p1;
end
else begin // двукратный LR-поворот
p2:=p1^.right; bal2:=p2^.bal;
p1^.right:=p2^.left; p2^.left:=p1;
t^.left:=p2^.right; p2^.right:=t;
if bal2=LongLeft then t^.bal:=LongRight
else t^.bal:=Long0;
if bal2=LongRight then p1^.bal:=LongLeft
else p1^.bal:=Long0;
t:=p2; p2^.bal:=Long0;
end
end;
end;
end; // BalanceRight
procedure Del(var r: TNode; var shorter: Boolean);
begin // shorter=false
if r^.right <> Nil then begin
Del(r^.right, shorter);
if shorter then BalanceRight(r,shorter);
end
else begin
q^.key:=r^.key;
r:=r^.left; shorter:=true
end;
end;
begin // DeleteBalance
if t=Nil then begin
success:=false; shorter:=false;
end
else begin
if i<t^.key then begin
DeleteBalance(t^.left, i, shorter, success);
if shorter then BalanceLeft(t, shorter)
end
else
if i>t^.key then begin
DeleteBalance(t^.right, i, shorter, success);
if shorter then BalanceRight(t, shorter);
end
else begin // удаление t^
q:=t;
if q^.right=Nil then begin
t:=q^.left; shorter:=true;
end
else
if q^.left=Nil then begin
t:=q^.right; shorter:=true;
end
else begin
Del(q^.left, shorter);
if shorter then BalanceLeft(t, shorter)
end;
end;
end
end; // DeleteBalance
Работа процедуры иллюстрируется на рис. 12.12.
Рис. 12.12. Удаление из АВЛ-дерева
Из АВЛ‑дерева на рис. 12.12(а) последовательно удаляются узлы с ключами 4, 8, 6, 5, 2, 1 и 7. В результате получаются деревья (б)…(з).
Удаление ключа 4 само по себе просто, так как этот узел — лист. Однако при этом появляется несбалансированность в узле 3. Его балансировка требует однократного поворота налево. Балансировка вновь становится необходимой после удаления узла 6. На этот раз правое поддерево корня балансируется однократным поворотом направо. Удаление узла 2, хотя само по себе просто, так как он имеет только одного потомка, вызывает сложный двукратный поворот направо и налево. И четвертый случай: двукратный поворот налево и направо вызывается удалением узла 7, который прежде заменяется самым правым узлом левого поддерева — узлом 7.
Следует отметить существенную разницу в выполнении двух процедур — вставки и удаления. В то время как включение одного узла может вызвать самое большее один поворот двух или трех узлов, то удаление может потребовать поворота в каждом узле вдоль пути поиска. Но насколько вероятны повороты при удалении? Эмпирические проверки показали удивительный результат: в то время как один поворот вызывается примерно двумя включениями, то при удалении один поворот приходится на пять удалений.