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

Автор книги: Джулиан Бакнелл

сообщить о нарушении

Текущая страница: 23 (всего у книги 36 страниц)

Рисунок 8.3. Повышение ранга левого дочернего узла (и наоборот)

Для исходного дерева можно было бы записать следующее неравенство: (а < L < b) < P < с. Для нового дерева имеем: a< L< (b< P< c), что, конечно же, остается справедливым и при удалении круглых скобок, поскольку операция < подчиняется коммуникативному закону. (первое неравенство читается следующим образом: все узлы в дереве а меньше узла L, который меньше всех узлов в дереве b, а все это дерево в целом меньше узла P, который, в свою очередь, меньше всех узлов в дереве с. Подобным же образом можно интерпретировать и второе неравенство.)

Только что рассмотренную операцию называют поворотом вправо (right rotation). При этом говорят, что ранг левого дочернего узла L повышается, а ранг родительского узла P понижается. Иначе говоря, узел L перемещается на один уровень вверх, а узел P – на один уровень вниз. Такой поворот называется поворотом вокруг узла P.

Естественно, рассмотрев поворот вправо, легко предположить, как выполняется другой поворот, поворот влево (left rotation), который создал бы первое дерево из второго. Поворот влево повышает ранг правого дочернего узла P и понижает ранг родительского узла L. Код выполнения обеих видов поворота приведен в листинге 8.17, при этом кодирование выполняется с точки зрения того узла, ранг которого повышается.

Листинг 8.17. Повышение ранга узла

function TtdSplayTree.stPromote(aNode : PtdBinTreeNode): PtdBinTreeNode;

var

Parent : PtdBinTreeNode;

begin

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

Parent := aNode^.btParent;

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

{повысить ранг левого дочернего узла, т.е. выполнить поворот родительского узла вправо}

if (Parent^.btChild[ctLeft] = aNode) then begin

Parent^.btChild[ctLeft] := aNode^.btChild[ctRight];

if (Parent^.btChild[ctLeft] <> nil) then

Parent^.btChild[ctLeft]^.btParent := Parent;

aNode^.btParent := Parent^.btParent;

if (aNode^.btParent^.btChild[ctLeft] = Parent) then

aNode^.btParent^.btChild[ctLeft] := anode else

aNode^.btParent^.btChild[ctRight] := aNode;

aNode^.btChild[ctRight] := Parent;

Parent^.btParent := aNode;

end

{повысить ранг правого дочернего узла, т.е. выполнить поворот родительского узла влево}

else begin

Parent^.btChild[ctRight] := aNode^.btChild[ctLeft];

if (Parent^.btChild[ ctRight ] <> nil) then

Parent^.btChild[ctRight]^.btParent := Parent;

aNode^.btParent := Parent^.btParent;

if (aNode^.btParent^.btChild[ctLeft] = Parent) then

aNode^.btParent^.btChild[ctLeft] := anode else

aNode^.btParent^.btChild[ctRight] := aNode/ aNode^.btChild[ctLeft] := Parent;

Parent^.btParent := aNode;

end;

{вернуть узел, ранг которого был повышен}

Result := aNode;

end;

Этот метод заимствован из класса скошенного дерева, который будет рассматриваться несколько позже. А пока важно отметить способ разрыва и преобразования связей, используемый для выполнения обоих типов повышения ранга. Поскольку переданный методу узел может быть левым или правым дочерним узлом, имеющим различные связи, которые необходимо разорвать и перестроить, по существу, этот метод представляет собой оператор If, учитывающий две возможности.

Два рассмотренных вида поворота реорганизуют дерево на локальном уровне, но основное свойство упорядоченности узлов дерева бинарного поиска остается неизменным. В случае выполнения поворота вправо все узлы дерева а перемещаются на один уровень ближе к корневому узлу, те, которые расположены в дереве b, остаются на том же уровне, а расположенные в дереве с, перемещаются на один уровень вниз. При выполнении поворота влево все узлы дерева а перемещаются на один уровень дальше от корневого узла, узлы дерева b остаются на том же уровне, а узлы дерева с перемещаются на один уровень вверх. Несложно догадаться, что, управляя некоторым общим алгоритмом балансировки, с помощью последовательности этих двух поворотов можно было бы восстановить баланс в дереве бинарного поиска.

Часто эти два вида поворота объединяются попарно и используются в формах так называемых спаренных двухсторонних поворотов (zig-zag) и спаренных односторонних поворотов (zig-zig). Существуют две операции спаренного двустороннего поворота и две операции спаренного одностороннего поворота. Операция спаренного двустороннего поворота состоит либо из поворота вправо, за которым следует поворот влево, либо из поворота влево, за которым следует поворот вправо, причем конечным результатом обеих операций является повышение ранга узла на два уровня. И напротив, операции спаренного одностороннего поворота состоят из двух выполняемых последовательно поворотов вправо или влево. Цель выполнения всех этих спаренных операций состоит в повышении ранга узла на два уровня.

На рис. 8.4 показана операция спаренного двустороннего поворота, которая начинается с поворота влево вокруг узла P. В результате ранг узла R повышается, а ранг узла P понижается. На следующем шаге выполняется вращение вправо вокруг узла G, в результате которого ранг узла R снова повышается, а ранг узла G понижается. Общим результатом операции спаренного двустороннего поворота будет локальная балансировка дерева.

Рисунок 8.4. Операция спаренного двустороннего поворота

На рис. 8.5 изображены обе операции спаренного одностороннего поворота, поскольку они дополняют друг друга. Обратите взимание, что операция спаренного одностороннего поворота всегда начинается с поворота вокруг верхнего узла.

Рисунок 8.5. Операция спаренного одностороннего поворота

Скошенные деревья

Как бы то ни было, ознакомившись с этими операциями простых и спаренных двухсторонних и односторонних поворотов, мы может их использовать в структуре данных, называемой скошенным деревом. Скошенное дерево (splay tree) – это дерево бинарного поиска, сконструированное таким образом, что любое обращение к узлу приводит к его скосу в сторону корневого узла. Скос заключается в применении операций спаренного двустороннего или одностороннего поворота до тех пор, пока скашиваемый узел не окажется в позиции корневого узла дерева или на один уровень ниже него. В последнем случае его ранг можно повысить до корневого узла, выполнив одиночный поворот. Концепция скошенного дерева была изобретена Д. Д. Слеатором (D. D. Sleator) и Р. Е. Таръяном (R. E. Tarjan) в 1985 году [22].

Вначале рассмотрим операцию поиска, т.е. нахождение конкретного узла. Мы начнем с применения стандартного алгоритма поиска в дереве бинарного поиска. Обнаружив искомый узел, мы выполняем его скос к корневому узлу.

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

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

Вставку также легко описать: необходимо применить обычный алгоритм вставки в дерево бинарного поиска, а затем выполнить скос добавленного узла.

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

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

Реализация класса скошенного дерева

Класс TtdSplayTree представляет собой простой производный класс класса TtdBinarySearchTree, в котором перекрыты методы Delete, Find и Insert и объявлены новые внутренние методы скоса и повышения ранга узла. Код интерфейса этого класса приведен в листинге 8.18.

Листинг 8.18. Интерфейс класса TtdSplayTree

type

TtdSplayTree = class (TtdBinarySearchTree) private protected

function stPromote(aNode : PtdBinTreeNode): PtdBinTreeNode;

procedure stSplay(aNode : PtdBinTreeNode);

public

procedure Delete(aItem : pointer); override;

function Find(aKeyItem : pointer): pointer; override;

procedure Insert(aItem : pointer); override;

end;

Перекрытый метод Find (см. листинг 8.19) реализует обычную операцию поиска в дереве бинарного поиска и, если узел найден, выполняет его скос к корневому узлу.

Листинг 8.19. Метод TtdSplayTree.Find

function TtdSplayTree.Find(aKeyItem : pointer): pointer;

var

Node : PtdBinTreeNode;

ChildType : TtdChildType;

begin

if bstFindItem (aKeyItem, Node, ChildType) then begin

Result := Node^.btData;

stSplay(Node);

end else

Result := nil;

end;

Перекрытый метод Insert(см. листинг 8.20) реализует обычную операцию вставки в дерево бинарного поиска и выполняет скос нового узла к корневому узлу.

Листинг 8.20. Метод TtdSplayTree.Insert

procedure TtdSplayTree.Insert(aItem : pointer);

var

ChildType : TtdChildType;

begin

stSplay(bstInsertPrim(aItem, ChildType));

end;

Перекрытый метод Delete (см. листинг 8.21) реализует обычную операцию удаления из дерева бинарного поиска и выполняет скос родительского узла удаленного узла к корневому узлу.

Листинг 8.21. Метод TtdSplayTree.Delete

procedure TtdSplayTree.Delete(aItem : pointer);

var

Node : PtdBinTreeNode;

Dad : PtdBinTreeNode;

begin

Node := bstFindNodeToDelete(aItem);

Dad := Node^.btParent;

FBinTree.Delete(Node);

dec(FCount);

if (Count <> 0) then

stSplay(Dad);

end;

Эти три перекрытых метода достаточно просты для понимания, поскольку реальная обработка передается методу stSplay. Код реализации этого метода приведен в листинге 8.22.

Листинг 8.22. Метод TtdSplayTree.stSplay

procedure TtdSplayTree.stSplay(aNode : PtdBinTreeNode);

var

Dad : PtdBinTreeNode;

Grandad : PtdBinTreeNode;

RootNode : PtdBinTreeNode;

begin

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

RootNode := FBinTree.Root;

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

if (aNode = RootNode) then

Exit;

{получить родительский и прародительский узлы}

Dad := aNode^.btParent;

if (Dad = RootNode) then

Grandad := nil else

Grandad := Dad^.btParent;

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

while (Grandad <> nil) do

begin

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

if ((Grandad^.btChild[ctLeft] = Dad) and (Dad^.btChild[ctLeft] = aNode)) or ( (Grandad^.btChild[ctRight] = Dad) and (Dad^.btChild[ctRight] ? aNode)) then begin

{выполнить повышение ранга посредством спаренного одностороннего поворота}

stPromote(Dad);

stPromote(aNode);

end

else begin

{выполнить повышение ранга посредством спаренного двустороннего поворота}

stPromote(stPromote(aNode));

end;

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

RootNode := FBinTree.Root;

if (aNode = RootNode) then begin

Dad := nil;

Grandad := nil;

end

else begin

Dad := aNode^.btParent;

if (Dad = RootNode) then

Grandad := nil else

Grandad := Dad^.btParent;

end;

end;

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

if (Dad <> nil) then

stPromote(aNode);

end;

Хотя эта подпрограмма выглядит сложной, она всего лишь повышает ранг переданного в нее узла до ранга корневого узла. Это делается с помощью ряда повышений ранга посредством спаренных односторонних или двусторонних поворотов: если узел, его родительский и прародительский узлы расположены на одной линии, выполняется повышение ранга за счет спаренного одностороннего поворота. В противном случае применяется повышение ранга за счет спаренного двустороннего поворота. Это процесс выполняется в цикле до тех пор, пока либо ранг узла не будет повышен до корневого, либо родительский узел данного узла не станет корневым. В последнем случае необходимо выполнить еще одно повышение ранга.

Код реорганизации при помощи повышения ранга представлен в методе stPromote, который показан в листинге 8.17.

Красно-черные деревья

Рассмотрев простые и спаренные двусторонние и односторонние повороты и ознакомившись с реорганизацией деревьев бинарного поиска за счет использования скошенных деревьев, пора приступить к исследованию соответствующего алгоритма балансировки.

Что должен делать алгоритм балансировки? В идеале он должен обеспечивать, чтобы длина пути от любого из листьев до корневого узла была одинаковой с точностью до единицы. На практике удовлетворить это строгое требование несколько затруднительно (AVL-деревья соответствуют этому определению, и их алгоритм балансировки удовлетворяет данному правилу). Поэтому мы определим какой-то алгоритм, который обеспечивает удовлетворение "менее строгого" требования, но не до такой степени "менее строгого", чтобы мы вернулись к тому, с чего начали.

В 1978 году Гюиба (Guibas) и Седжвик (Sedgewick) изобрели концепцию красно-черного дерева, удовлетворяющего такому умеренно нестрогому требованию. Красно-черные деревья (RB-деревья) – это структуры данных, используемые для реализации карт преобразования данных в библиотеке стандартных шаблонов С++ (С++ Standard Template Library). Красно-черный алгоритм предоставляет быстрый и эффективный метод балансировки дерева бинарного поиска, требующий для каждого узла не слишком много дополнительного объема памяти для хранения информации, необходимой для балансировки (в действительности для этого достаточно единственного дополнительного разряда).

Так что же собой представляют красно-черные деревья? Прежде всего, это дерево бинарного поиска, обладающее обычным простым алгоритмом поиска. Однако в красно-черном дереве каждый узел содержит определенную дополнительную информацию: каждый из них помечается как находящийся в одном из двух состояний. Эти два состояния называются красным (red) и черным (black).

Понятно, что этот подход применяется не просто для раскрашивания узлов, и в действительности необходимо выполнить еще три правила:

1. Считается, что нулевые дочерние связи на периферии дерева указывают на другие узлы (естественно, несуществующие). Эти невидимые нулевые узлы называются внешними узлами и всегда окрашены в черный цвет.

2. Условие для черных узлов: все пути от корневого узла до каждого из внешних узлов содержат одинаковое количество черных узлов.

3. Условие для красных узлов: каждый красный узел, не являющийся корневым, имеет черный родительский узел.

Учитывая, что до сих пор при создании деревьев мы вполне спокойно игнорировали эти нулевые связи, правило 1 кажется несколько усложненным. Тем не менее, его выполнение требуется, чтобы легче было выполнить правило 2. Следовательно, дерево с единственным узлом содержит также два внешних узла, являющиеся двумя нулевыми связями, исходящими из единственного реального узла (который называется внутренним). Второе правило – правило балансировки. Оно пытается поддерживать примерно одинаковую длину всех путей от корневого узла до каждого из внешних узлов. Эти пути будут различаться только количеством расположенных вдоль них красных узлов.

Набор простых красно-черных деревьев показан на рис. 8.6, при этом красные узлы изображены серыми квадратами (возможности одноцветной печати довольно-таки ограничены!), а внешние узлы – маленькими черными квадратами. Первое дерево (рисунок а) представляет пустое дерево – оно состоит всего из одного внешнего узла, который является черным – и, следовательно, по определению является красно-черным деревом. На примере второго и третьего деревьев (b и c) видно, что независимо от окрашивания корневого узла в красный или черный цвет, мы получаем красно-черное дерево. Эти деревья явно удовлетворяют всем трем правилам.

Рисунок 8.6. Набор простых красно-черных деревьев

Прежде чем продолжить, попытайтесь построить красно-черное дерево, содержащее два узла, корневой и левый дочерний, и три внешних узла (d). Выяснится, что в любом случае корневой узел должен быть окрашен в черный цвет, а его левый дочерний узел – в красный. Только такое окрашивание узлов позволяет удовлетворить все три правила.

Взглянем на это под другим углом. Посмотрите на рис. 8.7. Внутренние узлы этого дерева еще не окрашены. Можно ли их окрасить так, чтобы дерево удовлетворяло правилам 2 и 3? Никакого реального решения не существует. Невозможно окрасить внутренние узлы так, чтобы одновременно удовлетворить условия и для черных, и для красных узлов. Дерево, изображенное на рис. 8.7, не может быть красно-черным ни при каких условиях – и это хорошо, поскольку оно представляет начальную стадию вырождения дерева. Итак, важно усвоить следующий принцип: не все деревья могут быть окрашены в красный и черный цвета.

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

Рисунок 8.7. Дерево, которое не может быть окрашено в красный и черный цвета

Вставка в красно-черное дерево

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

Начнем с того, что окрасим его в красный цвет. Как это сказывается на соблюдении правил, определенных для красно-черных деревьев? Во-первых, условие для черных узлов по-прежнему выполняется: мы заменяем черный внешний узел красным узлом и двумя черными внешними узлами. Путь от каждого из двух новых внешних узлов до корневого узла по-прежнему содержит столько же черных узлов, сколько и путь от замещенного внешнего узла до корневого узла. А как насчет условия, определенного для красных узлов? Продолжает ли оно выполняться? Возможно, да, а, возможно, и нет. Если новый узел является корневым, и, следовательно, не имеет родительского узла, созданное дерево остается красно-черным (в действительности, при желании новый узел можно было бы перекрасить в черный цвет, и при этом дерево осталось бы красно-черным). Если же новый узел не является корневым, он будет иметь родительский узел. Если этот родительский узел черный, правило 3, определенное для красных узлов, остается применимым, и дерево по-прежнему является красно-черным. Если родительский узел нового узла является корневым, то, чтобы дерево осталось красно-черным, достаточно при необходимости перекрасить родительский узел в черный цвет. (Фактически, в красно-черном дереве, если оба дочерних узла корневого узла являются черными, корневой узел может быть как красным, так и черным – это никак не сказывается на соблюдении правил.)

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

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

Назовем новый узел s (от son – сын), его родительский узел d (от dad – отец), родительский узел родительского узла g (granddad – дед), а родственный с родительским узлом – и (uncle – дядя). Непосредственно после добавления узла s возникает следующая ситуация: узлы s и d являются красными (что является нарушением правила 2), узел g должен быть черным (согласно правилу 2), а узел и может быть либо красным, либо черным.

Вначале предположим, что узел и является черным. Для достижения поставленной цели достаточно выполнить либо одиночный поворот, либо спаренный двусторонний поворот, а затем перекрасить некоторые узлы. В первом случае, который на рис. 8.8 представлен первым преобразованием, мы выполняем поворот узла d вправо на место узла g, чтобы g стал дочерним узлом узла d. Затем мы перекрашиваем узел d в черный цвет, a g – в красный. Во втором случае (нижнее преобразование на рис. 8.8) мы выполняем спаренный двусторонний поворот, чтобы поместить узел s на место g, а затем перекрашиваем узел s в черный цвет, a g – в красный. Обратите внимание, что абсолютно не важно, является ли узел и внешним или внутренним; достаточно, чтобы он был черным.

Естественно, возможны еще два случая, представляющие собой зеркальное отражение рассмотренных, однако мы не будем их рассматривать. На рисунке 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. Мысленно заложим в этом месте закладку и рассмотрим другие случаи.