Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Рисунок 8.15. Балансировка после удаления: заключительный случай
Итак, мы рассмотрели все возможности. При этом использовались два рекурсивных шага или, точнее, два шага, которые требовали дальнейших усилий по балансировке. Первый - когда братский узел был красным, и его нужно было сделать
братский узел был черным, а дальний узел-племянник красным (цвет родительского узла и ближайшего узла-племянника "не имели значения");
и, наконец, случай, когда братский узел был черным, дальний узел-племянник черным, а ближайший узел-племянник красным. Если вы еще раз взглянете на рисунки 8.12, 8.13, 8.14 и 8.15, то убедитесь, что мы рассмотрели все варианты.
Опуская математические выкладки, отметим, что алгоритм удаления из красно-черного дерева является алгоритмом типа O(log(n)), хотя постоянный коэффициент времени больше, чем в случае простого бинарного дерева.
Операция удаления узла из красно-черного дерева реализуется с помощью кода, представленного в листинге 8.25.
Листинг 8.25. Удаление из красно-черного дерева
procedure TtdRedBlackTree.Delete(aItem : pointer);
var
Node : PtdBinTreeNode;
Dad : PtdBinTreeNode;
Child : PtdBinTreeNode;
Brother : PtdBinTreeNode;
FarNephew : PtdBinTreeNode;
NearNephew : PtdBinTreeNode;
IsBalanced : boolean;
ChildType : TtdChildType;
begin
{выполнить поиск узла, который нужно удалить; этот узел будет иметь единственный дочерний узел}
Node := bstFindNodeToDelete(aItem);
{если узел красный или является корневым, его можно безнаказанно удалить}
if (Node^.btColor = rbRed) or (Node = FBinTree.Root) then begin
FBinTree.Delete(Node);
dec(FCount);
Exit;
end;
{если единственный дочерний узел является красным, перекрасить его в черный цвет и удалить узел}
if (Node^.btChild[ctLeft] =nil) then
Child := Node^.btChild[ctRight] else
Child :=Node^.btChild[ctLeft];
if IsRed(Child) then begin
Child^.btColor :=rbBlack;
FBinTree.Delete(Node);
dec(FCount);
Exit;
end;
{на этом этапе узел, который нужно удалить, - узел Node; он является черным и известно, что дочерний узел Child, который его заменит, является черным (а также может быть нулевым!) и что существует родительский узел узла Node (который вскоре станет родительским узлом узла Child); братский узел узла Node также существует в соответствии с правилом, сформулированным
{если узел Child является нулевым, необходимо несколько упростить выполнение цикла и определить родительский и братский узлы и определить, является ли узел Node левым дочерним узлом}
if (Child = nil) then begin
Dad := Node^.btParent;
if (Node = Dad^.btChild[ctLeft]) then begin
ChildType :=ctLeft;
Brother := Dad^.btChild[ctRight];
end
else begin
ChildType :=ctRight;
Brother := Dad^.btChild[ctLeft];
end;
end
else begin
{следующие три строки предназначены просто для введения в заблуждение компилятора и предотвращения вывода ряда ложных предупреждений}
Dad := nil;
Brother := nil;
ChildType :=ctLeft;
end;
{удалить узел — он больше не нужен}
FBinTree.Delete(Node);
dec(FCount);
Node := Child;
{циклически применять алгоритмы балансировки при удалении из красно-черного дерева до тех пор, пока дерево не окажется сбалансированным}
repeat
{предположим, что дерево сбалансировано}
IsBalanced := true;
{если узел является корневым, балансировка выполнена, поэтому предположим, что это не так}
if (Node <> FBinTree.Root) then begin
{получить родительский и братский узлы}
if (Node <> nil) then begin
Dad := Node^.btParent;
if (Node = Dad^.btChild[ctLeft]) then begin
ChildType := ctLeft;
Brother := Dad^.btChild[ctRight];
end
else begin
ChildType := ctRight;
Brother := Dad^.btChild[ctLeft];
end;
end;
{нам требуется наличие черного братского узла, поэтому если в настоящий момент братский узел окрашен в красный цвет, окрасить родительский узел в красный цвет, братский узел в черный цвет и повысить ранг братского узла; затем снова повторить цикл}
if (Brother^.btColor = rbRed) then begin
Dad^.btColor := rbRed;
Brother^.btColor :=rbBlack;
rbtPromote(Brother);
IsBalanced := false;
end
{ в противном случае братский узел является черным}
else begin
{получить узлы-племянники, помеченные как дальний и ближний}
if (ChildType = ctLeft) then begin
FarNephew := Brother^.btChild[ctRight];
NearNephew := Brother^.btChild[ctLeft];
end
else begin
FarNephew := Brother^.btChild[ctLeft];
NearNephew := Brother^.btChild[ctRight];
end;
{если дальний узел-племянник является красным (обратите внимание, что он может быть нулевым), окрасить его в черный цвет, братский узел в цвет родительского узла, а родительский узел в красный цвет, а затем повысить ранг братского узла; задача выполнена}