РЕАЛИЗАЦИЯ ДЕРЕВА ПОИСКА
В общем случае каждый элемент дерева поиска может содержать в содержательной части Value специальное поле, называемое ключом этого элемента. Для упрощения описания будем считать, что поле Value является ключом элемента дерева.
В этом случае класс tSearchTree может быть описан как наследник класса tBinaryTree: type
tSearchTree = class(tBinaryTree) //класс - дерево поиска function Addr(Key: tValue): pltem; //адрес элемента с ключом Key function Search(Key: tValue): pltem;//поиск с включением procedure Delete(Key: tValue); //поиск с исключением procedure Build(var f: Text); //построение дерева поиска
end; //tSearchTree
Метод Build дерева поиска перекрывает одноименный метод бинарного дерева, поскольку реализуется иначе.
Поле fRoot и все остальные методы бинарного дерева наследуются деревом поиска.
Методы Addr, Search и Delete являются новыми, расширяющими возможности дерева поиска по сравнению с обычным бинарным деревом.
РЕАЛИЗАЦИЯ ОПЕРАЦИЙ НАД ДЕРЕВОМ ПОИСКА
Поиск элемента с ключом Key может быть выполнен с помощью итерации, так как поиск идет по единственному пути от корня к искомому узлу:
function tSearchTree.Addr(Key: tValue): pltem;
// Возвращение адреса элемента с ключом Key // или nil, если элемент не найден
var
Item: pltem; begin if Empty then Addr:= nil else begin ltem:= fRoot;
while (ltem<>nil) and (ltemA.Value<>Key) do begin if Key
then ltem:= ltemA.Left //спуск по левой ветви
else ltem:= ltemA.Right; //спуск по правой ветви
end;
Addr:= Item;
end;
end; //function tSearchTree.Addr
Метод, реализующий поиск no дереву с включением:
function tSearchTree.Search(Key: tValue):pltem;
// Поиск элемента с заданным ключом Key с включением procedure lncKey(var Item: pltem); //рекурсивная процедура поиска
begin if ltem=nil then begin
// элемента с ключом Key нет: включение его в качестве листа ltem:= New(pltem); ltemA.Value := Key; ltemA.Left:= nil; ltemA.Right:=nil;
Result:= Item; Inc(fSize);
end
else
if Key
else
if Key>ltemA.Value then lncKey(ltemA.Right) //поиск справа else Result:= Item; //элемент найден
end; //procedure IncKey
begin
IncKey(fRoot);
end; //function tSearchTree.Search
При реализации процедуры поиска с исключением необходимо рассмотреть три ситуации и три способа поведения процедуры после исключения элемента:
- • ситуация 1: элемента с ключом Key нет в дереве, в этом случае дерево остается неизменным;
- • ситуация 2: элемент с ключом Key имеет не более одного потомка — после исключения ближайший потомок поднимается на его место;
- • ситуация 3: элемент с ключом Key имеет двух потомков, в этом случае исключаемый элемент нужно заменить самым правым элементом его левого поддерева, имеющим не более одного потомка. Этому условию соответствует элемент, предшествующий исключаемому в обходе слева направо. После исключения узла с двумя потомками дерево останется деревом поиска и в том случае, если заменить исключаемый элемент самым левым элементом его правого поддерева, имеющим не более одного потомка. Этому условию соответствует элемент, следующий за исключаемым в обходе слева направо.
На рис. 3.7 приведено исходное дерево поиска (а). Дерево (б) получается из дерева (а) после исключения элемента 15 и замены его элементом 11 — самым правым элементом левого поддерева узла 15 (в процедуре обхода слева направо он предшествует узлу 15). Дерево (в) получается из дерева (а) после исключения элемента 15 и замены его элементом 18 — самым левым элементом правого поддерева узла 15 (в процедуре обхода следует за узлом 15).

Рис. 3.7. Исключения в дереве поиска
procedure tSearchTree.Delete(Key: tValue);
// Поиск элемента с заданным ключом Key с исключением
procedure DelKey(var Item: pltem);
// Основная рекурсивная процедура
var Delltem: pltem; //указатель на исключаемый элемент
procedure Del(var Addr: pltem);
// Вспомогательная рекурсивная процедура.
// Возвращает адрес самого правого элемента //левого поддерева удаляемого узла Delltem begin //procedure Del
if AddrA.Right<>nil
then Del(AddrA.Right) // поиск правого элемента
else begin
// Найден самый правый элемент левого поддерева Delltem DelltemA.Value:= AddrA.Value;
Delltem:= Addr;
Addr:= AddrA.Left;
end;
end; //procedure Del
begin //procedure DelKey
if Itemonil then
if Key
then DelKey(ltemA.Left) // поиск слева
else
if Key>ltemA.Value
then DelKey(ltemA.Right) //поиск справа
else begin //элемент найден, исключение ItemA Delltem:= Item; if DelltemA.Right=nil
then ltem:= DelltemA.Left //ситуация 2
else
if DelltemA.Left=nil
then ltem:= DelltemA.Right //ситуация 2 else Del(DelltemA.Left); //ситуация 3 - поиск предшественника // Удаление перемещенного элемента:
Dispose(Delltem); Dec(fSize); end; //конец исключения Item*
end; //procedure DelKey
begin
DelKey(fRoot);
end; //procedure tSearchTree.Delete
В методе tSearchTree. Delete используется основная рекурсивная процедура DelKey, которая собственно и выполняет поиск в дереве с удалением. Вспомогательная рекурсивная процедура Del начинает работать только в ситуации 3. Она «спускается» вдоль правой ветви левого поддерева элемента с указателем Delltem, который нужно исключить, и заменяет поле Value элемента DellterrK на соответствующее значение из самого правого элемента AddrA левого поддерева, после чего от элемента AddrA можно освободиться.
Построение дерева поиска заключается в считывании из входного потока (в данной реализации из текстового файла) элементов с заданными ключами и включении их в дерево с использованием операции поиска с включением Search(Key).
procedure tSearchTree.Build(var f: Text);
// Построение дерева поиска из элементов из файла f
var Key : tValue;
begin
while not SeekEof(f) do begin
Read(f, Key);
if SeekEoln(f) then ReadLn(f);
Search(Key); // функция Search вызывается как процедура
end;
end; //procedure tSearchTree.Build