Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi
Естественно, возможны еще два случая, представляющие собой зеркальное отражение рассмотренных, однако мы не будем их рассматривать. На рисунке 8.8 легко видеть, что теперь условие, определенное для красных узлов, удовлетворено, и что операции поворота и перекрашивания не нарушают условие, определенное для черных узлов.
Рисунок 8.8. Балансировка после вставки: два простых случая
Этот случай был простым. Теперь рассмотрим более сложный. Предположим, что узел и, дядя нового узла, также окрашен в красный цвет. Первый шаг прост: мы перекрашиваем узлы 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);
if (OurType = DadsType) then begin
Dad^.btColor := rbBlack;
rbtPromote(Dad);
end
{в противном случае необходимо окрасить узел в черный цвет и повысить его ранг посредством применения спаренного двустороннего поворота; задача выполнена}
else begin
Node^.btColor :=rbBlack;
rbtPromote(rbtPromote(Node));
end;
end;
end;
end;
end;
until IsBalanced;
end;
Необходимо принимать во внимание один небольшой нюанс: следует проверять цвета узлов. Некоторые из узлов, которые мы будем проверять, будут внешними, т.е. нулевыми. Для повышения читабельности кода я написал небольшую подпрограмму IsRed, которая выполняет проверку на наличие нулевого узла (возвращая значение false), прежде чем выполнять проверку поля цвета узла.
Листинг 8.24. Интеллектуальная подпрограмма IsRed
function IsRed(aNode : PtdBinTreeNode): boolean;
begin
if (aNode = nil) then
Result := false else
Result := aNode^.btColor = rbRed;
end;
Удаление из красно-черного дерева
По сравнению со вставкой, удаление из красно-черного дерева сопряжено с множеством особых случаев и его может быть трудно отследить.
Как обычно, при использовании деревьев бинарного поиска, начнем с поиска узла, который требуется удалить. Как и ранее, возможны три начальных случая: узел не имеет дочерних узлов (или, применяя терминологию, принятую в красно-черных деревьях, оба его дочерних узла являются внешними);
узел имеет один реальный дочерний узел и один внешний дочерний узел;
и, наконец, узел имеет два реальных дочерних узла. Удаление узла выполняется так же, как это делалось в стандартном неокрашенном дереве бинарного поиска.
Теперь рассмотрим эти три случая с точки зрения красно-черных деревьев. Первый случай - узел с двумя внешними дочерними узлами (т.е. с нулевыми связями). В соответствии с правилом 1, эти два дочерних узла считаются черными. Однако узел, который нужно удалить, может быть красным или черным. Предположим, что он красный. Удаляя его, мы заменяем дочернюю связь родительского узла нулевым указателем - иначе говоря, внешним черным узлом. Однако мы не изменили количество черных узлов от нового внешнего узла до корневого узла, по сравнению с существовавшими до этого двумя путями. Следовательно, правило 2 по-прежнему выполняется. Очевидно, что правило 3 также не нарушается (мы удаляем красный узел, поэтому никакие проблемы в отношении соблюдения этого правила не возникают). Таким образом, после удаления бинарное дерево остается красно-черным. Эта возможность представлена первым преобразованием на рис. 8.10.
А как насчет второй возможности (когда удаляемый узел окрашен в черный цвет)? Что ж, в этом случае правило 2, сформулированное для черных узлов, неизбежно нарушается. Количество черных узлов в пути до корневого узла уменьшается на 1. Возникающая в результате такого преобразования проблема проиллюстрирована на нижней части рисунка 8.10. Мысленно заложим в этом месте закладку и рассмотрим другие случаи.
Рисунок 8.10. Удаление узла, имеющего два внешних дочерних узла
Второй случай удаления - удаление узла, который имеет один реальный дочерний узел и один внешний дочерний узел. Предположим, что удаляемый узел является красным. Его единственный реальный дочерний узел будет черным. Можно удалить узел и заменить его единственным дочерним узлом. Это не приведет к нарушению правила 2, - в конечном счете, мы удаляем красный узел, - а правило 3 в данном случае не затрагивается, следовательно, дерево остается красно-черным. Этот случай представлен первым преобразованием на рис. 8.11.
