Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Рисунок 8.14. Балансировка после удаления: третий случай
Теперь рассмотрим последний случай. Предположим, что противоположный узел-племянник окрашен в черный цвет, но второй узел этой же степени родства является красным. На этот раз нужно выполнить спаренный двусторонний поворот. Вначале мы окрашиваем узел-племянник в цвет родительского узла (как и в предыдущем случае, первоначальный цвет родительского узла значения не имеет), а затем
Если нарушающий узел удается переместить до позиции корневого узла, создается предельная ситуация. В этом случае нарушающий узел не имеет родительского узла и, следовательно, не может иметь братский узел. При этом нарушающий узел больше не представляет проблемы.
Конечно, все рассмотренные случаи имеют аналоги, представляющие их зеркальные отражения, но при этом анализ каждого из случаев удаления остается тем же. При написании кода подпрограммы удаления нужно будет убедиться, что мы правильно отразили как левые, так и правые варианты расположения узлов.
Рисунок 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
{ в противном случае братский узел является черным}