Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi
И, наконец, мы выяснили, как поддерживать хеш-таблицы на диске, минимизируя при этом количество обращений к диску. Мы рассмотрели алгоритм группирования и его реализацию для создания базы данных, в основе которой лежит хеширование.
Глава 8. Бинарные деревья.
Подобно массивам и связным спискам, деревья того или иного вида - это структуры данных, которые используются программистами практически повсеместно. В главе 3 были рассмотрены односвязные списки, в которых существовала единственная связь, соединяющая узлы друг с другом (двухсвязные списки имели также связь, указывающую в противоположном направлении). Обычно связные списки рассматриваются как горизонтальные структуры (в целях экономии места на бумаге!), в которых начальный узел располагается слева, а сам связный список простирается направо. Теперь представим, что этот связный список повернут на 90 градусов по часовой стрелке, чтобы начальный узел располагался вверху, а конечный внизу. Этот случай представляет собой особый пример многопутевого дерева, в котором каждый узел имеет только один дочерний узел, расположенный непосредственно под ним. Аналогично, каждый узел имеет один родительский узел, который расположен непосредственно над ним. Естественно, такая классификация охватывает целое семейство деревьев. Примем соглашение, что самый нижний узел имеет нулевую связь, т.е. не имеет дочернего узла. Поскольку каждый узел имеет максимум один дочерний узел, односвязный список можно было бы называть унарным деревом.
Многопутевое дерево является обобщением этой концепции. Оно представляет собой коллекцию узлов, организованных так, чтобы все узлы кроме корневого (мы будем называть узел в верхушке дерева корневым, а узел, который не имеет дочерних узлов - листовым, или просто листом) имели только один родительский узел и могли иметь ноль или больше дочерних узлов. Таким образом, связный список - это особое многопутевое дерево, в котором каждый узел (кроме самого нижнего) имеет только один дочерний узел. Если каждый узел может иметь максимум n дочерних узлов, такое дерево называется n-арным деревом.
Рисунок 8.1. Бинарное дерево
Теперь рассмотрим случай, когда каждый узел имеет до двух дочерних узлов. Иначе говоря, для каждого узла существует максимум две связи с узлами следующего нижнего уровня. Эта структура называется бинарным деревом. Согласно принятому соглашению, два дочерних узла данного узла называются левым и правым дочерними узлами, поскольку при рисовании дерева с расположением его корня в вершине, дочерние узлы выстраиваются горизонтально под ним, один левее от другого. Классическое представление бинарного дерева показано на рис. 8.1.
Из приведенных рассуждений ясно, что при определении используемого узла бинарного дерева в Delphi-программе нам требуются две связи (т.е. указатели) с его дочерними узлами, связь с его родительским узлом (эта связь необязательна, но, как мы увидим, ее применение упрощает некоторые алгоритмы, работающие с деревьями) и фактические данные, которые должны храниться в узле. С целью упрощения задачи примем, что данные в узле могут быть представлены указателем, подобно TList и структурам данных, которые уже были рассмотрены в этой книге. Поскольку узел имеет фиксированный размер, мы снова воспользуемся описанным в главе 3 диспетчером узлов, когда дело дойдет до создания класса бинарного дерева. Код, приведенный в листинге 8.1, определяет расположение записей узлов.
Листинг 8.1. Расположение узлов в бинарном дереве type
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. После этого узел может быть освобожден.
Второе правило удаления из бинарного дерева применяется в отношении случая, когда удаляемый узел имеет один дочерний узел. Эта задача также достаточно проста: мы просто перемещаем дочерний узел вверх по дереву, чтобы он стал тем же дочерним узлом родительского узла, каким является удаляемый узел.
Третье правило применяется к случаю, когда удаляемый узел имеет два дочерних узла. Как и можно было предположить, это правило звучит просто: узел не может быть удален. Попытка сделать это является ошибкой. Позже мы рассмотрим вариант бинарного дерева - дерево бинарного поиска, - который содержит достаточный объем дополнительной внедренной в дерево информации, чтобы можно было обойти это ограничение.
