Рисунок 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];