Главная Информатика
Алгоритмы и структуры данных
|
|
|||||
РЕАЛИЗАЦИЯ ДЕРЕВА ПОИСКАВ общем случае каждый элемент дерева поиска может содержать в содержательной части 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 При реализации процедуры поиска с исключением необходимо рассмотреть три ситуации и три способа поведения процедуры после исключения элемента:
На рис. 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 |
<< | СОДЕРЖАНИЕ | >> |
---|