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

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.