Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Но как насчет узла, с позиции которого он был перемещен, и который теперь нужно удалить? В отношении этого конкретного узла важно уяснить, что он не имеет никакого правого дочернего узла. Если бы он имел правый дочерний узел, элемент в дочернем узле должен был бы быть больше элемента, с которым мы поменяли его местами, и, следовательно, первоначально выбранный элемент не мог бы быть наибольшим. Он может иметь левый дочерний узел, но независимо от этого мы знаем, как удалить узел, имеющий не более одного дочернего узла.
При этом все еще остается проблема обнаружения наибольшего элемента, который меньше исходного, предназначенного для удаления. По
Обратите также внимание, что удаление, как и вставка, может приводить к созданию вырожденного дерева. Эту проблему решают алгоритмы балансировки, которые мы рассмотрим при ознакомлении с красно-черным вариантом дерева бинарного поиска.
Листинг 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.