Текст книги "Фундаментальные алгоритмы и структуры данных в Delphi"
Автор книги: Джулиан Бакнелл
сообщить о нарушении
Текущая страница: 22 (всего у книги 36 страниц)
aExtraData : pointer): PtdBinTreeNode;
function btRecIn0rder(aNode : PtdBinTreeNode; aAction : TtdVisitProc;
aExtraData : pointer): PtdBinTreeNode;
function btRecPostOrder(aNode : PtdBinTreeNode; aAction : TtdVisitProc;
aExtraData : pointer): PtdBinTreeNode;
function btRecPreOrder(aNode : PtdBinTreeNode; aAction : TtdVisitProc;
aExtraData : pointer): PtdBinTreeNode;
public
constructor Create(aDisposeItem : TtdDisposeProc);
destructor Destroy; override;
procedure Clear;
procedure Delete(aNode : PtdBinTreeNode);
function InsertAt(aParentNode : PtdBinTreeNode;
aChildType : TtdChildType; aItem : pointer): PtdBinTreeNode;
function Root : PtdBinTreeNode;
function Traverse(aMode : TtdTraversalMode; aAction : TtdVisitProc;
aExtraData : pointer; aUseRecursion : boolean): PtdBinTreeNode;
property Count : integer read FCount;
property Name : TtdNameString read FName write FName;
end;
Как обычно при использовании структур данных, рассмотренных в этой книге, мы убеждаемся, что класс владеет содержащимися в нем данными и, следовательно, может их при необходимости освобождать, или же предполагаем, что обработка данных выполняется из какого-то другого места, и в этом случае дерево не будет освобождать какие-либо данные. Поэтому конструктор Create принимает параметр, определяющий процедуру удаления элемента данных. Если этот параметр является нулевым, дерево не владеет данными и, следовательно, не будет их удалять. Если параметр aDisposeItem является адресом процедуры, эта процедура будет вызываться в каждом случае, когда требуется освободить элемент.
Листинг 8.10. Методы Create и Destroy класса бинарного дерева
constructor TtdBinaryTree.Create(aDisposeItem : TtdDisposeProc);
begin
inherited Create;
FDispose := aDisposeItem;
{проверить, доступен ли диспетчер узлов}
if (BTNodeManager = nil) then
BTNodeManager := TtdNodeManager.Create(sizeof(TtdBinTreeNode));
{выделить заглавный узел; со временем корневой узел дерева станет его левым дочерним узлом}
FHead := BTNodeManager.AllocNodeClear;
end;
destructor TtdBinaryTree.Destroy;
begin
Clear;
BTNodeManager.FreeNode(FHead);
inherited Destroy;
end;
Метод Create убеждается, что диспетчер узлов бинарного дерева активен, а затем выделяет фиктивный заглавный узел. Именно на месте левого дочернего узла этого узла находится корневой узел дерева. Метод Destroy убеждается, что дерево очищено (т.е. все узлы в дереве освобождены), а затем освобождает фиктивный заглавный узел.
Следующий метод, который мы рассмотрим – метод Clear. В данном случае требуется удалить все узлы дерева. Как упоминалось ранее, это выполняется за счет применения обхода всего дерева в глубину. В данном случае мы воспользовались нерекурсивным обходом, поскольку он выполняется быстрее.
Листинг 8.11. Очистка бинарного дерева
procedure TtdBinaryTree.Clear;
var
Stack : TtdStack;
Node : PtdBinTreeNode;
begin
if (FCount = 0) then
Exit;
{создать стек}
Stack := TtdStack.Create(nil);
try
{затолкнуть корневой узел}
Stack.Push(FHead^.btChild[ctLeft]);
{продолжать процесс до тех пор, пока стек не опустеет}
while not Stack.IsEmpty do
begin
{извлечь узел в начале очереди}
Node := Stack.Pop;
{если он является нулевым, вытолкнуть из стека следующий узел и освободить его}
if (Node = nil) then begin
Node := Stack.Pop;
if Assigned(FDispose) then
FDispose(Node^.btData);
BTNodeManager.FreeNode(Node);
end
{в противном случае дочерние узлы этого узла в стек еще не заталкивались}
else begin
{затолкнуть узел, а за ним – нулевой указатель}
Stack.Push(Node);
Stack.Push(nil);
{затолкнуть правый дочерний узел, если он не нулевой}
if (Node^.btChild[ctRight]<> nil) then
Stack.Push(Node^.btChild[ctRight]);
{затолкнуть левый дочерний узел, если он не нулевой}
if (Node^.btChild[ctLeft] <> nil) then
Stack.Push(Node^.btChild[ctLeft]);
end;
end;
finally
{уничтожить стек}
Stack.Free;
end;
{внести изменения, отражающие то, что дерево пусто}
FCount := 0;
FHead^.btChild[ctLeft] nil;
end;
Если сравнить этот код с кодом общего метода нерекурсивного обхода, приведенным в листинге 8.7, то несложно заметить, что они во многом совпадают. Единственное реальное различие состоит в том, что в коде отсутствует какая-либо процедура действия – мы уже знаем, что будет делаться с каждым узлом.
Метод Traverse действует всего лишь в качестве контейнера различных внутренних методов обхода, большинство из которых мы уже рассмотрели. Остальные методы представляют собой соответствующие рекурсивные методы обхода дерева.
Листинг 8.12. Обход в классе бинарного дерева
function TtdBinaryTree.btRecInOrder(aNode : PtdBinTreeNode;
aAction : TtdVisitProc; aExtraData : pointer): PtdBinTreeNode;
var
StopNow : boolean;
begin
Result := nil;
if (aNode^.btChild[ctLeft] <> nil) then begin
Result := btRecInOrder(aNode^.btChild[ctLeft],
aAction, aExtraData);
if (Result <> nil) then
Exit;
end;
StopNow := false;
aAction(aNode^.btData, aExtraData, StopNow);
if StopNow then begin
Result := aNode;
Exit;
end;
if < aNode^.btChild[ ctRight ] <> nil) then begin
Result := btRecInOrder(aNode^.btChild[ctRight], aAction, aExtraData);
end;
end;
function TtdBinaryTree.btRecPostOrder(aNode : PtdBinTreeNode;
aAction : TtdVisitProc; aExtraData : pointer): PtdBinTreeNode;
var
StopNow : boolean;
begin
Result := nil;
if (aNode^.btChild[ctLeft] <> nil) then begin
Result :=btRecPostOrder(aNode^.btChild[ctLeft], aAction, aExtraData);
if (Result <> nil) then
Exit;
end;
if (aNode^.btChild[ctRight] <> nil) then begin
Result := btRecPostOrder(aNode^.btChild[ctRight],
aAction, aExtraData);
if (Result <> nil) then
Exit;
end;
StopNow := false;
aAction(aNode^.btData, aExtraData, StopNow);
if StopNow then
Result :=aNode;
end;
function TtdBinaryTree.btRecPreOrder(aNode : PtdBinTreeNode;
aAction : TtdVisitProc; aExtraData : pointer): PtdBinTreeNode;
var
StopNow : boolean;
begin
Result := nil;
StopNow := false;
aAction(aNode^.btData, aExtraData, StopNow);
if StopNow then begin
Result :=aNode;
Exit;
end;
if (aNode^.btChild[ctLeft] <> nil) then begin
Result := btRecPreOrder(aNode^.btChild[ctLeft], aAction, aExtraData);
if (Result <> nil) then
Exit;
end;
if (aNode^.btChild[ctRight]<> nil) then begin
Result := btRecPreOrder(aNode^.btChild[ctRight], aAction, aExtraData);
end;
end;
function TtdBinaryTree.Traverse(aMode : TtdTraversalMode;
aAction : TtdVisitProc;
aExtraData : pointer;
aUseRecursion : boolean): PtdBinTreeNode;
var
RootNode : PtdBinTreeNode;
begin
Result := nil;
RootNode := FHead^.btChild[ctLeft];
if (RootNode <> nil) then begin
case aMode of
tmPreOrder :
if aUseRecursion then
Result := btRecPreOrder(RootNode, aAction, aExtraData) else
Result := btNoRecPreOrder(aAction, aExtraData);
tmlnOrder :
if aUseRecursion then
Result :=btRecInOrder(RootNode, aAction, aExtraData) else
Result := btNoRecInOrder(aAction, aExtraData);
tmPostOrder :
if aUseRecursion then
Result := btRecPostOrder(RootNode, aAction, aExtraData) else
Result := btNoRecPostOrder(aAction, aExtraData);
tmLevelOrder : Result :=btLevelOrder(aAction, aExtraData);
end;
end;
end;
Как видно из кода внутренних рекурсивных процедур, возможность прекращения обхода в любой момент времени делает код несколько менее читабельным и более сложным.
Исходный код класса TtdBinaryTree можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDBinTre.pas.
Деревья бинарного поиска
Хотя бинарные деревья являются структурами данных, которые представляют интерес и сами по себе, на практике в основном используют бинарные деревья, содержащие элементы в сортированном виде. Такие бинарные деревья называют деревьями бинарного поиска (binary search tree).
В дереве бинарного поиска каждый узел имеет ключ. (В деревьях бинарного поиска, которые будут построены в этой главе, считается, что ключ является частью элемента, вставляемого в дерево. Для сравнения двух элементов, а, следовательно, и их ключей, мы будем использовать подпрограмму TtdConrpare.) Упорядочение применяется ко всем узлам в дереве: для каждого узла ключ левого дочернего узла меньше или равен ключу узла, а этот ключ, в свою очередь, меньше или равен ключу правого дочернего узла. Если описанное упорядочение постоянно применяется во время вставки (как именно – будет показано чуть ниже), это также означает, что для каждого узла все ключи в левом дочернем дереве меньше или равны ключу узла, а все ключи в правом дочернем дереве больше или равны ключу узла.
Какие основные операции претерпевают изменения в случае использования дерева бинарного поиска вместо обычного бинарного дерева? Что ж, все алгоритмы обхода работают так же, как и ранее (фактически, при симметричном обходе все узлы в дереве бинарного поиска посещаются в порядке ключей – отсюда и английское название этого метода "in-order"). Однако операции вставки и удаления должны быть изменены, поскольку они могут нарушить порядок ключей в дереве бинарного поиска. Поиск элемента может быть выполнен значительно быстрее.
Алгоритм поиска в дереве бинарного поиска использует упорядоченность дерева. Поиск элемента выполняется следующим образом. Поиск начинается с корневого узла, и этот узел становится текущим. Затем ключ искомого элемента сравнивается с ключом текущего узла. Если они равны, дело сделано, поскольку мы нашли требуемый элемент в дереве. В противном случае, если ключ элемента меньше ключа текущего узла, мы делаем левый дочерний узел текущим. Если он больше, мы делаем текущим правый дочерний узел и возвращаемся к шагу выполнения сравнения. Со временем мы либо найдем нужный узел, либо встретим нулевой дочерний узел, что свидетельствует об отсутствии искомого элемента в дереве.
Следует отметить одну особенность этого алгоритма в случае наличия в дереве нескольких элементов с равными ключами: не существует никаких гарантий, что мы найдем какой-то конкретный элемент с соответствующим ключом. Им может оказаться первый элемент, последний или любой промежуточный. Фактически, в основном по тем же причинам, что и при использовании списка с пропусками, желательно гарантировать, чтобы все элементы в дереве бинарного поиска имели уникальные, различающиеся между собой ключи. Присутствие дублированных ключей не допускается. На практике это правило не создает особых трудностей: если можно различить два элемента, должно быть не трудно обеспечить их различение и в дереве бинарного поиска. Обычно это достигается за счет использования младших ключей (например, фамилия служит в качестве главного ключа, а имя – в качестве контрольного значения, когда фамилии совпадают). Таким образом, деревья бинарного поиска, рассмотренные в этой главе, будут подчиняться правилу недопустимости дублированных ключей. В результате определение дерева бинарного поиска будет формулироваться следующим образом: это дерево, в котором ключ левого дочернего узла строго меньше ключа данного узла, который, в свою очередь, строго меньше ключа правого дочернего узла.
Алгоритм поиска в дереве бинарного поиска имитирует стандартный бинарный поиск в массиве или в связном списке. В каждом узле мы принимаем решение, какой дочерней связью нужно следовать. При этом можно игнорировать все узлы, находящиеся в другом дочернем дереве. Если дерево сбалансировано, алгоритм поиска является операцией типа O(log(n)). Другими словами, среднее время, затрачиваемое на поиск любого элемента, пропорционально log(_2_) от числа элементов в дереве. Под сбалансированным мы будем понимать дерево, в котором длина пути от любого листа до корневого узла приблизительно одинакова, причем дерево имеет минимальное количество уровней, необходимое для данного количества присутствующих узлов.
Листинг 8.13. Поиск в дереве бинарного поиска
function TtdBinarySearchTree.bstFindItem(aItem : pointer;
var aNode : PtdBinTreeNode;
var aChild : TtdChildType): boolean;
var
Walker : PtdBinTreeNode;
CmpResult : integer;
begin
Result := false;
{если дерево пусто, вернуть нулевой и левый узел для указания того, что новый узел, в случае его вставки, должен быть корневым}
if (FCount = 0) then begin
aNode := nil;
aChild := ctLeft;
Exit;
end;
{в противном случае перемещаться по дереву}
Walker := FBinTree.Root;
CmpResult := FCompare(aItem, Walker^.btData);
while (CmpResult <> 0) do
begin
if (CmpResult < 0) then begin
if (Walker^.btChild[ctLeft] = nil) then begin
aNode := Walker;
aChild := ctLeft;
Exit;
end;
Walker := Walker^.btChild[ctLeft];
end
else begin
if (Walker^.btChild[ctRight] =nil) then begin
aNode := Walker;
aChild := ctRight;
Exit;
end;
Walker := Walker^.btChild[ctRight];
end;
CmpResult := FCompare(aItem, Walker^.btData);
end;
Result := true;
aNode := Walker;
end;
function TtdBinarySearchTree.Find(aKeyItem : pointer): pointer;
var
Node : PtdBinTreeNode;
ChildType : TtdChildType;
begin
if bstFindItem(aKeyItem, Node, ChildType) then
Result := Node^.btData else
Result := nil;
end;
В коде, представленном в листинге 8.13, не используются отдельные ключи для каждого элемента. Вместо этого предполагается, что свойство упорядочения дерева бинарного поиска определяется функцией сравнения, подобно тому, как это делалось в отсортированных связных списках, списках с пропусками и т.п. Функция сравнения дерева бинарного поиска объявляется конструктором Create.
Метод Find использует внутренний метод bstFindItem. Этот метод должен вызываться для достижения двух различных целей. Во-первых, самим методом Find, и, во-вторых, методом, который вставляет новые узлы в дерево (этот метод мы рассмотрим несколько позже). Соответственно, если элемент не был найден, метод будет возвращать место, в которое он должен быть вставлен. Естественно, эта функция не требуется для простого поиска: нам нужно только знать, существует ли элемент, и если существует, то получить элемент целиком обратно.
В представленном коде следует также отметить, что класс используется внутренний экземпляр TtdBinaryTree, названный FBinTree, для хранения фактического бинарного дерева. Как будет показано, класс дерева бинарного поиска делегирует все операции бинарного дерева этому внутреннему бинарному дереву. Легко заметить, что от этого внутреннего объекта требуется получить только корневой узел. С этого момента остается только перемещаться по узлам.
Вставка в дереве бинарного поиска
Мы можем существенно упростить операцию вставки для пользователя дерева бинарного поиска: он должен предоставить только сам элемент. Пользователь не должен также беспокоиться о том, какой узел становится родительским, и в качестве какого дочернего узла добавляется новый узел. Все это, скрывая подробности, может выполнить дерево бинарного поиска, используя в качестве руководства к действию порядок элементов внутри дерева.
Фактически, вставить новый элемент в дерево бинарного поиска достаточно просто, и большая часть этого процесса уже была рассмотрена. Мы ищем элемент до тех пор, пока не достигаем точки, когда дальнейший спуск оказывается невозможен, поскольку дочерняя связь, которой нужно было бы следовать, является нулевой. К этому моменту мы знаем, где должен размещаться элемент, – в точке, где мы должны были остановиться. При этом известно, каким дочерним узлом должен быть элемент, и, естественно, мы останавливаемся на родительском узле нового узла. Обратите также внимание, что используемый алгоритм поиска места для вставки нового элемента гарантирует целостность порядка элементов в дереве бинарного поиска.
Тем не менее, алгоритм вставки сопряжен с одной проблемой. Хотя метод гарантирует создание допустимого дерева бинарного поиска после выполнения операции, созданное дерево может быть неоптимальным или неэффективным. Чтобы понять, о чем идет речь, вставьте элементы a, b, c, d, e и f в пустое дерево бинарного поиска. С элементом а все просто – он становится корневым узлом. Элемент b добавляется в качестве правого дочернего узла элемента a. Элемент c добавляется в качестве правого дочернего узла элемента b и т.д. Результат показан слева на рис. 8.2: он представляет собой длинное вытянутое дерево, которое можно трактовать как связного списка. В идеале желательно, чтобы дерево было более сбалансированным. Для только что созданного вырожденного дерева время поиска пропорционально числу элементов в дереве (О(n)), а не log(_2_) числа элементов (O(log(n))). Возможны также другие случаи вырождения. Например, попытайтесь выполнить следующую последовательность вставок: a, f, b, e, c и d, в результате которой создается явно вырожденное дерево, показанное справа на рис. 8.2.
Рисунок 8.2. Вырожденные деревья бинарного поиска
В связи с возникновением описанных проблем, этот простой алгоритм вставки вряд ли будет применяться на практике. Если бы можно было гарантировать случайный порядок вставки ключей и элементов, или если бы общее количество элементов было очень небольшим, описанный алгоритм вставки оказался бы вполне приемлемым. Однако в общем случае подобную гарантию просто нельзя дать, и поэтому необходимо использовать более сложный алгоритм вставки, частью которого является попытка сбалансировать дерево бинарного поиска. Эта методика балансировки будет рассмотрена в ходе ознакомления с красно-черными деревьями (RB-деревьями).
–
Важно иметь в виду следующее. Рассмотренные алгоритмы вставки и удаления гарантированно создают допустимое дерево бинарного поиска. Однако при этом весьма вероятно, что дерево будет скошенным и несбалансированным. Для небольших деревьев бинарного поиска это не имеет особого значения (в конце концов, для малых значений n log(n) и n – величины более-менее одного порядка, поэтому выигрыш в значении О большого будет небольшим), тем не менее, для больших деревьев такое различие поистине огромно.
–
Возвращаясь к простому алгоритму вставки, мы видим, что для вставки n элементов в дерево бинарного поиска в среднем требуется время, пропорциональное O(n log(n)) (другими словами, для каждой вставки используется алгоритм O(log(n)) для выяснения места, в которое должен быть помещен новый элемент, а количество вставляемых элементов равно n). В случае вырождения вставка n элементов превращается в операцию типа O(n(^2^)).
Листинг 8.14. Вставка в дерево бинарного поиска
function TtdBinarySearchTree.bstInsertPrim(aItem : pointer;
var aChildType : TtdChildType): PtdBinTreeNode;
begin
{вначале предпринять попытку найти элемент; если он найден, сгенерировать ошибку}
if bstFindItem(aItem, Result, aChildType) then
bstError(tdeBinTreeDupItem, 'bstInsertPrim');
{эта операция возвращает узел, поэтому вставку потребуется выполнить здесь}
Result := FBinTree.InsertAt(Result, aChildType, aItem);
inc(FCount);
end;
procedure TtdBinarySearchTree.Insert(aItem : pointer);
var
ChildType : TtdChildType;
begin
bstInsertPrim(aItem, ChildType);
end;
Для выполнения большей части работы мы используем внутреннюю процедуру bstInsertPrim. Это делается для того, чтобы разделить код собственно вставки и код метода Insert, что впоследствии упростит нашу задачу при создании производных деревьев от дерева бинарного поиска для выполнения операции балансировки. Как видите, процедура bstInsertPrim возвращает вставленный узел и использует метод bstFindItem, который уже встречался в листинге 8.13.
Таким образом, фактическую вставку мы делегируем объекту бинарного дерева, который использует свой метод InsertAt.
Удаление из дерева бинарного поиска
Как и при выполнении предыдущей операции, большая часть проблем может быть скрыта от пользователя дерева бинарного поиска. Однако дерево должно выполнить определенную, более сложную задачу.
Естественно, первым шагом является поиск элемента в дереве с применением стандартного алгоритма. Если найти элемент не удастся, придется как-то сообщить о неудаче. В случае обнаружения элемента, поиск может быть прерван в узле одного из трех типов, как это имеет место в стандартном бинарном дереве.
Первый тип узла – узел без дочерних узлов, обе дочерние связи которого являются нулевыми. Иначе говоря, лист. Чтобы удалить узел этого типа, мы просто разрываем его связь с родительским узлом и удаляем его. Это удаление не нарушает порядок узлов в дереве – в конце концов, узел был листом и не имел дочерних узлов.
Второй тип узла – узел только с одним дочерним узлом. В случае стандартного бинарного дерева мы просто перемещаем дочерний узел на один уровень вверх, чтобы заменить удаляемый узел. Можно ли это же сделать в данном случае? Рассмотрим родительский узел узла, который должен быть удален. Удаленный узел является либо левым дочерним узлом (в этом случае его ключ меньше ключа родительского узла), либо правым дочерним узлом (в этом случае его ключ больше ключа родительского узла). Не только этот узел, но и все дочерние, "внучатые" и так далее узлы удаленного узла обладают тем же свойством. Все они будут либо меньше родительского узла, либо больше. Таким образом, до тех пор, пока речь идет о родительском узле, при замене узла одним из его дочерних узлов свойство упорядочения будет сохраняться. Если дочерний узел имеет свои дочерние узлы, это перемещение не сказывается на них или на их порядке. Следовательно, в случае дерева бинарного поиска мы по-прежнему можем выполнить эту простую операцию.
Третий тип узла – узел с двумя дочерними узлами. В стандартном дереве бинарного поиска мы считали попытку удаления узла этого типа ошибкой. Удаление не могло быть выполнено, поскольку не существовало никакого общего способа выполнения операции удаления, который имел бы смысл. В случае дерева бинарного поиска это не так: в данном случае можно воспользоваться свойством упорядочения дерева бинарного поиска.
Ситуация выглядит следующим образом: нам нужно удалить определенный узел (т.е. элемент в этом узле), но он имеет два дочерних узла (каждый из которых имеет собственные дочерние узлы). Алгоритм удаления несколько сложен, поэтому вначале он будет описан словесно, а затем будет показано, как он работает. На практике мы ищем узел, содержащий наибольший элемент, который меньше только того, который мы пытаемся удалить. Затем мы меняем местами элементы в этих двух узлах. И, наконец, мы удаляем второй узел. Он всегда будет соответствовать одному из ранее рассмотренных случаев удаления.
Первый шаг заключается в отыскании наибольшего элемента, меньшего того элемента, который мы пытаемся удалить. Понятно, что он находится в левом дочернем дереве (все элементы этого дерева меньше удаляемого элемента). Кроме того, он является наибольшим элементом этого дерева. Иначе говоря, все остальные элементы, которые могут находиться в левом дочернем дереве, меньше этого элемента. В действительности все элементы в правом дочернем дереве больше этого выбранного элемента (поскольку он меньше элемента, который должен быть удален, а этот элемент, в свою очередь, меньше всех элементов в правом дочернем дереве). Следовательно, он вполне может заменить удаляемый элемент, и это действие не нарушит порядок элементов в дереве.
Но как насчет узла, с позиции которого он был перемещен, и который теперь нужно удалить? В отношении этого конкретного узла важно уяснить, что он не имеет никакого правого дочернего узла. Если бы он имел правый дочерний узел, элемент в дочернем узле должен был бы быть больше элемента, с которым мы поменяли его местами, и, следовательно, первоначально выбранный элемент не мог бы быть наибольшим. Он может иметь левый дочерний узел, но независимо от этого мы знаем, как удалить узел, имеющий не более одного дочернего узла.
При этом все еще остается проблема обнаружения наибольшего элемента, который меньше исходного, предназначенного для удаления. По существу, мы выполняем перемещение по дереву. Начиная с элемента, который нужно удалить, мы переходим к левой дочерней связи. С этого места мы продолжаем перемещаться по правым дочерним связям до тех пор, пока не доберемся до узла, не имеющего никакой правой дочерней связи. Этот элемент гарантированно содержит наибольший элемент, меньший только того элемента, который мы пытаемся удалить.
Обратите также внимание, что удаление, как и вставка, может приводить к созданию вырожденного дерева. Эту проблему решают алгоритмы балансировки, которые мы рассмотрим при ознакомлении с красно-черным вариантом дерева бинарного поиска.
Листинг 8.15. Удаление из дерева бинарного поиска
function TtdBinarySearchTree.bstFindNodeToDelete(aItem : pointer)
: PtdBinTreeNode;
var
Walker : PtdBinTreeNode;
Node : PtdBinTreeNode;
Temp : pointer;
ChildType : TtdChildType;
begin
{попытаться найти элемент; если элемент не найден, сгенерировать признак ошибки}
if not bstFindItem(aItem, Node, ChildType) then
bstError(tdeBinTreeItemMissing, 1bstFindNodeToDelete');
{если узел имеет два дочерних узла, найти наибольший узел, который меньше удаляемого, и поменять местами элементы}
if (Node^.btChild[ctLeft]<> nil) and (Node^.btChild[ctRight]<> nil) then begin
Walker := Node^.btChild[ctLeft];
while (Walker^.btChild[ctRight] <> nil) do
Walker := Walker^.btChild[ctRight];
Temp := Walker^.btData;
Walker^.btData := Node^.btData;
Node^.btData := Temp;
Node := Walker;
end;
{вернуть узел, который нужно удалить}
Result := Node;
end;
procedure TtdBinarySearchTree.Delete(aItem : pointer);
begin
FBinTree.Delete(bstFindNodeToDelete(aItem));
dec(FCount);
end;
Большая часть работы выполняется методом bstFindNodeToDelete. Он вызывает метод bstFindItem, чтобы найти элемент, который требуется удалить (естественно, если он не найден, генерируется ошибка), а затем проверяет, имеет ли найденный узел два дочерних узла. Если имеет, мы ищем узел с наибольшим элементом, который меньше удаляемого элемента. Мы меняем местами элементы в узлах и возвращаем второй элемент.
Реализация класса дерева бинарного поиска
Как обычно, дерево бинарного поиска будет реализовано в виде класса, хотя хотелось бы еще раз предупредить, что его следует использовать только в том случае, если есть уверенность, что вставляемые элементы являются в достаточной степени случайными или их количество достаточно мало, чтобы дерево не выродилось в длинную вытянутую структуру. Основное назначение класса дерева бинарного поиска – попытка сокрытия от пользователя внутренней структуры дерева. Это означает, что пользователь должен иметь возможность использовать класс для поддержания набора элементов в отсортированном порядке и выполнения их обхода без необходимости знания структуры внутренних узлов.
При реализации дерева бинарного поиска мы не будем использовать наследование от класса бинарного поиска, описанного в первой части этой главы. В основном, это обусловлено тем, что класс бинарного дерева открывает пользователю слишком много подробностей внутренней структуры узлов. Вместо этого мы делегируем функции вставки, удаления и обхода внутреннему объекту бинарного дерева. Просто на тот случай, если пользователю потребуется знание внутреннего объекта дерева, мы откроем его через соответствующее свойство.
Листинг 8.16. Интерфейс дерева бинарного поиска
type
TtdBinarySearchTree = class {класс дерева бинарного поиска}
private
FBinTree : TtdBinaryTree;
FCompare : TtdCompareFunc;
FCount : integer;
FName : TtdNameString;
protected
procedure bstError(aErrorCode : integer;
const aMethodName : TtdNameString);
function bstFindItem(aItem : pointer; var aNode : PtdBinTreeNode;
var aChild : TtdChildType): boolean;
function bstFindNodeToDelete(aItem : pointer): PtdBinTreeNode;
function bstInsertPrim(aItem : pointer; var aChildType : TtdChildType): PtdBinTreeNode;
public
constructor Create( aCompare : TtdCompareFunc;
aDispose : TtdDisposeProc);
destructor Destroy; override;
procedure Clear;
procedure Delete(aItem : pointer); virtual;
function Find(aKeyItem : pointer): pointer; virtual;
procedure Insert(aItem : pointer); virtual;
function Traverse( aMode : TtdTraversalMode;
aAction : TtdVisitProc; aExtraData : pointer;
aUseRecursion : boolean): pointer;
property BinaryTree : TtdBinaryTree read FBinTree;
property Count : integer read FCount;
property Name : TtdNameString read FName write FName;
end;
Глядя на определение этого класса, легко убедиться, что мы уже встречались с большинством методов.
Исходный код класса TtdBinarySearchTree можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDBinTre.pas.
Перекомпоновка дерева бинарного поиска
В ходе рассмотрения дерева бинарного поиска неоднократно упоминалось, что добавление элементов в дерево бинарного поиска может сделать его крайне несбалансированным, а иногда даже привести к его вырождению в длинное вытянутое дерево, подобное связному списку.
Проблема этого вырождения заключается не в том, что дерево перестает корректно функционировать (элементы продолжают храниться в отсортированном порядке), а в том, что в данном случае эффективности древовидной структуры наносится, по сути, смертельный удар. Для идеально сбалансированного дерева (в котором все родительские узлы имеют по два дочерних узла, а все листья размещаются на одном уровне, плюс-минус один) время поиска, время вставки и время удаления соответствуют O(log(n)). Иначе говоря, если для выполнения основной операции в дереве с 1000 узлов требуется время, равное t, для ее выполнения в дереве с 1000000 узлов потребуется время равное всего лишь 2t. С другой стороны время выполнения базовых операций в вырожденном дереве пропорционально O(n), и, следовательно, для выполнения этой же операции в дереве с 1 000 000 узлов потребовалось бы время, равное 1000t.
Так каким же образом избежать этого вырождения деревьев? Ответ заключается в создании алгоритма, который осуществляет балансировку дерева бинарного поиска во время вставки и удаления элементов. Прежде чем действительно приступить к рассмотрению алгоритмов балансировки, давайте исследуем различные методы перекомпоновки деревьев бинарного поиска, а затем ими можно будет воспользоваться для балансировки деревьев.
Вспомните, что в дереве бинарного поиска все узлы в левом дочернем дереве данного узла меньше, а узлы в правом дочернем дереве больше его. (Естественно, под тем, что один узел меньше другого, подразумевается, что ключ элемента в одном узле меньше ключа элемента в другом узле. Просто проще написать, что "один узел меньше другого", нежели постоянно ссылаться на ключи узлов.) Немного проанализируем эту аксиому.
Взгляните на левый дочерний узел в дереве бинарного поиска. Что мы знаем о нем? Что ж, естественно, он имеет собственные левое и правое дочерние деревья. Он больше всех узлов в его левом дочернем дереве и меньше всех узлов в правом дочернем дереве. Более того, поскольку он является левым дочерним узлом, его родительский узел больше всех узлов в его правом дочернем дереве. Следовательно, если повернуть левый дочерний узел в позицию его родительского узла, чтобы его правое дочернее дерево стало новым левым дочерним деревом родительского узла, результирующее бинарное дерево останется допустимым. Этот поворот показан на рис. 8.3. На этом рисунке треугольники представляют дочерние деревья, которые содержат ноль или больше узлов – для алгоритма поворота точное их количество роли не играет.
