Фундаментальные алгоритмы и структуры данных в Delphi

Этот случай был простым. Теперь рассмотрим более сложный. Предположим, что узел и, дядя нового узла, также окрашен в красный цвет. Первый шаг прост: мы перекрашиваем узлы d и u в черный цвет, а g в красный. Условие для черных узлов по-прежнему выполняется, но, похоже, мы ухудшили общую ситуацию, поскольку условие, определенное для красных узлов, перестало выполняться. Вместо того чтобы признать, что узел s нарушает условие, определенное для красных узлов, мы предположили, каким мог бы быть узел g. В конце концов, родительский узел узла g мог бы быть и красным. Иначе говоря, в действительности эта операция перекрашивания не решает никаких проблем. Мы просто отложили решение проблемы на неопределенный срок. Но действительно ли ситуация ухудшилась? Посмотрите, что мы сделали: мы переместили проблемный узел вверх по дереву. Перемещение вверх ограничено в пространстве, поскольку со временем мы натолкнемся на корневой узел.

Итак, перенесем свое внимание двумя уровнями выше, примем, что узел g является новым узлом и посмотрим, нарушили ли мы какие-либо правила. Иначе говоря, снова применим рассмотренный алгоритм, но на этот раз начнем рассмотрение с узла g. Два возможных случая показаны на рис. 8.9 (естественно, могут существовать и два случая, являющиеся зеркальными отражениями представленных, но они не показаны). В обоих результирующих деревьях узел g помечен тремя восклицательными знаками, указывающими, что он может нарушать одно из двух правил, и что необходимо продолжать процесс, снова повторяя действия алгоритма.

Не прибегая к подробным математическим выкладкам, отметим, что подобно случаю применения простого бинарного дерева, алгоритм вставки в красно-черное дерево является алгоритмом типа O(log(n)), хотя в этом случае постоянный коэффициент имеет большее значение, поскольку приходится учитывать возможные повороты и повышение ранга узлов.

Рисунок 8.9. Балансировка после вставки: два рекурсивных случая

Код реализации этого алгоритма вставки и балансировки приведен в листинге 8.23. Метод содержит внутренний цикл, выход из которого выполняется, когда баланс дерева восстановлен. В начале цикла предполагается, что балансировка дерева должна быть выполнена в данном цикле, и что перемещение по дереву вверх должно выполняться только в том случае, если мы уверены, что снова будем выполнять цикл. В остальном приведенный код служит достаточно точным представлением алгоритма вставки в красно-черное дерево. Единственный неприятный момент - необходимость поддержания информации о том, являются ли определенные узлы левыми или правыми дочерними узлами своих родительских узлов.

Листинг 8.23. Вставка в красно-черное дерево

procedure TtdRedBlackTree.Insert(aItem : pointer);

var

Node : PtdBinTreeNode;

Dad : PtdBinTreeNode;

Grandad : PtdBinTreeNode;

Uncle : PtdBinTreeNode;

OurType : TtdChildType;

DadsType : TtdChildType;

IsBalanced : boolean;

begin

{вставить новый элемент, вернуться к вставленному узлу и его связям с родительским узлом}

Node := bstInsertPrim(aItem, OurType);

{окрасить его в красный цвет}

Node^.btColor := rbRed;

{продолжать применение в цикле алгоритмов балансировки при вставке в красно-черное дерево до тех пор, пока дерево не окажется сбалансированным}

repeat

{предположим, что дерево сбалансировано}

IsBalanced :=true;

{если узел является корневым, задача выполнена и дерево сбалансировано, поэтому будем считать, что мы находимся не в корневом узле}

if (Node <> FBinTree.Root) then begin

{поскольку мы находимся не в корневом узле, необходимо получить родительский узел данного узла}

Dad := Node^.btParent;

{если родительский узел черный, задача выполнена и дерево сбалансировано, поэтому будем считать, что родительский узел красный}

if (Dad^.btColor = rbRed) then begin

{если родительский узел является корневым, достаточно перекрасить его в черный цвет, и задача будет выполнена}

if (Dad = FBinTree.Root) then

Dad^.btColor := rbBlack {в противном случае родительский узел, в свою очередь, имеет родительский узел}

else begin

{получить прародительский узел (он должен быть черным) и перекрасить его в красный цвет}

Grandad := Dad^.btParent;

Grandad^.btColor := rbRed;

{получить узел, соответствующий понятию дяди}

if (Grandad^.btChild[ctLeft] = Dad) then begin

DadsType := ctLeft;

Uncle := Grandad^.btChild[ ctRight ];

end

else begin

DadsType := ctRight;

Uncle := Grandad^.btChild[ ctLeft ];

end;

{если дядя тоже имеет красный цвет (обратите внимание, что он может быть нулевым!), окрасить родительский узел в черный цвет, дядю в черный цвет и повторить процесс, начиная с прародительского узла}

if IsRed(Uncle) then begin

Dad^.btColor :=rbBlack;

Uncle^.btColor := rbBlack;

Node := Grandad;

IsBalanced := false;

end

{в противном случае дядя окрашен в черный цвет?}

else begin

{если текущий узел имеет такие же отношения со своим родительским узлом, какие его родительский узел имеет с прародительским (т.е. они оба являются либо левыми, либо правыми дочерними узлами), нужно окрасить родительский узел в черный цвет и повысить его ранг. Задача выполнена}

OurType := GetChildType(Node);