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;