РЕАЛИЗАЦИЯ ДЕРЕВА ПОИСКА

В общем случае каждый элемент дерева поиска может содержать в содержательной части 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 (ltem^A.Value<>Key) do begin if KeyA.Value

then ltem:= ltem^A.Left //спуск по левой ветви

else ltem:= ltem^A.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); ltem^A.Value := Key; ltem^A.Left:= nil; ltem^A.Right:=nil;

Result:= Item; Inc(fSize);

end

else

if KeyA.Value then lncKey(ltem^A.Left) //поиск слева

else

if Key>ltem^A.Value then lncKey(ltem^A.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 Addr^A.Right<>nil

then Del(Addr^A.Right) // поиск правого элемента

else begin

// Найден самый правый элемент левого поддерева Delltem Delltem^A.Value:= Addr^A.Value;

Delltem:= Addr;

Addr:= Addr^A.Left;

end;

end; //procedure Del

begin //procedure DelKey

if Itemonil then

if KeyA.Value

then DelKey(ltem^A.Left) // поиск слева

else

if Key>ltem^A.Value

then DelKey(ltem^A.Right) //поиск справа

else begin //элемент найден, исключение Item^A Delltem:= Item; if Delltem^A.Right=nil

then ltem:= Delltem^A.Left //ситуация 2

else

if Delltem^A.Left=nil

then ltem:= Delltem^A.Right //ситуация 2 else Del(Delltem^A.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 на соответствующее значение из самого правого элемента Addr^A левого поддерева, после чего от элемента Addr^A можно освободиться.

Построение дерева поиска заключается в считывании из входного потока (в данной реализации из текстового файла) элементов с заданными ключами и включении их в дерево с использованием операции поиска с включением 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