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

TtdChildType = ( {типы дочерних узлов}

ctLeft, {.. левый дочерний узел}

ctRight);

{.. правый дочерний узел}

TtdRBColor = ( {цвета для красно-черного дерева}

rbBlack, {..черный}

rbRed);

{..красный}

PtdBinTreeNode = ^TtdBinTreeNode;

TtdBinTreeNode = packed record btParent : PtdBinTreeNode;

btChild : array [TtdChildType] of PtdBinTreeNode;

btData : pointer;

case boolean of

false : (btExtra : longint);

true : (btColor : TtdRBColor);

end;

Обратите внимание, что две дочерние связи мы определили в виде двухэлементного массива. На первый взгляд, это может показаться излишним, но когда дело дойдет до реализации операций с бинарным деревом, такое определение существенно упростит нашу задачу. Кроме того, узел бинарного дерева объявляет дополнительное поле, которое не требуется для обычных бинарных деревьев, однако упрощает задачу для красно-черного варианта дерева бинарного поиска.

Само по себе создание бинарного дерева тривиально. В простейшем случае корневой узел бинарного дерева определяет все бинарное дерево.

var

MyBinaryTree : PtBinTreeNode;

Если MyBinaryTree равен nil, никакого бинарного дерева не существует, поэтому это значение служит начальным значением бинарного дерева.

{инициализировать бинарное дерево}

MyBinaryTree :=nil;

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

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

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

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

Листинг 8.2. Вставка в бинарное дерево

function TtdBinaryTree.InsertAt(aParentNode : PtdBinTreeNode;

aChildType : TtdChildType; aItem : pointer): PtdBinTreeNode;

begin

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

if (aParentNode = nil) then begin

aParentNode := FHead;

aChildType :=ctLeft;

end;

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

if (aParentNode^.btChild[aChildType]<> nil) then

btError(tdeBinTreeHasChild, 'InsertAt');

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

Result := BTNodeManager.AllocNode;

Result^.btParent := aParentNode;

Result^.btChild[ctLeft] :=nil;

Result^.btChild[ctRight] := nil;

Result^.btData := aItem;

Result^.btExtra := 0;

aParentNode^.btChild[aChildType] := Result;

inc(FCount);

end;

Обратите внимание, что приведенный в листинге 8.2 код вначале проверяет, является ли добавляемый узел корневым. Если да, то переданный родительский узел равен nil. В этом случае метод инициализирует родительский узел значением внутреннего заглавного узла.

Кроме этой проверки метод InsertAt убеждается, что дочерняя связь, которую предполагается использовать для нового узла, действительно не используется. В противном случае это будет грубой ошибкой.

Обратите внимание, что класс бинарного дерева (составной частью которого является этот метод) использует диспетчер узлов для распределения и освобождения узлов. Поскольку все узлы имеют одинаковый размер, в этом, как было сказано в главе 3, заложен глубокий смысл.

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

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

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

Листинг 8.3. Удаление из бинарного дерева

procedure TtdBinaryTree.Delete(aNode : PtdBinTreeNode);

var

OurChildsType : TtdChildType;

OurType : TtdChildType;

begin

if (aNode = nil) then

Exit;

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

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

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

btError(tdeBinTree2Children, 'Delete');

OurChildsType :=ctLeft;

end

else

OurChildsType :=ctRight;

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

OurType := GetChildType(aNode);

{установить дочернюю связь данного родительского узла равной данной дочерней связи}

aNode^.btParent^.btChild[OurType] := aNode^.btChild[OurChildsType];

if (aNode^.btChild[OurChildsType] <> nil) then

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

{освободить узел}

if Assigned(FDispose) then

FDispose(aNode^.btData);

BTNodeManager.FreeNode(aNode);

dec(FCount);

end;

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