Сформировать односвязный список из вещественных элементов, хранящихся в файле LW2Dat.txt. Исключить из списка элементы с введенным с терминала значением, перенести оставшиеся элементы в односвязный циклический список и вывести значения его элементов в файл результатов.
// Лабораторная работа 2. Линейные односвязные и двусвязные списки.
// Выполнил Сергеев Андрей, группа 500.
// Формирование списка и исключение заданных элементов.
// Исходные данные – элементы списка – в файле LW2Dat.txt
// Результаты работы помещаются в файл LW2Res.txt
program LW2;
Uses
SysUtils,
SymplyLists in 'SymplyLists.pas', // модуль односвязных списков
DoublyLists in 'DoublyLists.pas'; // модуль двусвязных списков
function WinDOS(const s: string): string;
// Перекодировка русских символов строки s из ANSI (Windows) в ASCII (DOS)
// Текст подпрограммы приведён в примере выполнения лабор. работы № 1
end; // WinDOS
Var
List: tList; // экземпляр линейного списка
CircleList: tCircleList; // экземпляр циклического списка
Item: pItem; // указатель на элемент списка
fDat, fRes: Text; // файлы исходных данных и результатов
LstVal, DelVal: tValue; // значение текущего и исключаемого элементов
quan: Word; // количество элементов сриска
Begin
Try
Assign(fDat, 'LW1Dat.txt'); Reset(fDat);
Assign(fRes,' LW1Res.txt'); Rewrite(fRes);
WriteLn(fRes, 'Работа со списком - поиск и удаление заданного элемента');
// Создание экземпляров List и CircleList
List:= tList.Create; CircleList:= tCircleList.Create;
// Формирование линейного списка
while not eof(fDat) do begin
Read(fDat, LstVal);
List.InsertHead(LstVal);
end;
quan:= List.Size;
// Вывод элементов линейного списка в файл результатов методом WriteTo
WriteLn(fRes, 'Сформирован список из ',quan,' элементов:');
List.WriteTo(fRes);
Write(WinDos('Значение исключаемого элемента? '));
ReadLn(DelVal);
WriteLn(fRes, 'Значение исключаемого элемента = ', DelVal:5:1);
// Поиск и исключение из списка элементов со значением DelVal
Repeat
Item:= List.Search(DelVal);
if Item<> nil then List.Delete(Item);
until Item= nil;
// Вывод элементов изменённого линейного списка в файл результатов
WriteLn(fRes, 'Из списка исключено ',quan - List.Size,' элементов, осталось ',
List.Size,' элементов:');
List.WriteTo(fRes);
// Перенесение оставшихся элементов в циклический список
while not List.Empty do begin
LstVal:= List.DeleteHead;
CircleList.InsertRear(LstVal);
end;
WriteLn(fRes, 'Элементы линейного списка перенесены в циклический',
' список, состоящий из ', CircleList.Size, ' элементов:');
// Вывод элементов циклического списка в файл результатов
CircleList.WriteTo(fRes);
List.Free; CircleList.Free;
Finally
Close(fDat); Close(fRes);
end;
end.
Тема 3. Бинарные деревья
1. Основные понятия и определения
Дерево – это непустое конечное множество элементов, из которых один называется корнем, а остальные делятся на несколько непересекающихся подмножеств, каждое из которых само является деревом.
Рекурсивное определение. Дерево с базовым типом Т – это либо: пустое дерево, либо некоторый узел типа Т с некоторым конечным числом связанных с ним деревьев типа Т, называемых поддеревьями.
Существует несколько способов изображения структуры дерева: вложенные множества (1), вложенные скобки (2), отступы (3), граф (4). Ниже с помощью перечисленных способов изображено одно и то же дерево, элементами которого являются буквы латинского алфавита:
Структура, представленная в виде графа и явно отражающая разветвления, привела к появлению термина «дерево». Каждый элемент дерева называют узлом. Дерево принято изображать растущим вниз, а его верхний узел называют корнем. Все узлы дерева разбивают на уровни. Корень имеет нулевой уровень. Если узел x лежит на уровне i, а y связана с x и лежит на уровне i +1, то говорят, что y – потомок (сын) x, а x – предок (отец) y. Высота дерева равна максимальному уровню этого дерева плюс 1.
Если элемент не имеет потомков, то его называют терминальным узлом, или листом, в противном случае узел называют внутренним. Число непосредственных потомков внутреннего узла называют его степенью. Максимальная степень всех узлов есть степень дерева.
Упорядоченное дерево – это дерево, у которого ветви, исходящие из каждого узла, упорядочены. Поэтому два изображенных ниже упорядоченных дерева – это разные объекты.
Особенно важную роль играют упорядоченные деревья второй степени. Их называют двоичными (или бинарными) деревьями.
Примеры бинарного дерева: генеалогическое дерево, где у каждого человека есть потомки (!) в лице отца и матери; схема кубкового спортивного турнира, где каждая игра – это узел, в котором указан её победитель, а потомки – две предыдущие игры соперников; арифметическое выражение с бинарными операциями, где каждому оператору соответствует узел, а операнды – его поддеревья. Ниже приведены два бинарных дерева: дерево (а), элементами которого являются символы латинского алфавита, и дерево (б) выражения (a + b / c)´(d – e ´ f).
(а) (б)
Если каждый узел бинарного дерева, не являющийся листом, имеет непустые правые и левые поддеревья, то дерево называется строго бинарным. Строго бинарное дерево с n листами всегда содержит 2 n -1 узлов. Дерево выражения (б) является строго бинарным.
Строго бинарное дерево, все листья которого расположены на одном уровне, называется совершенным. Совершенное дерево высотой h содержит 2 h –1 узлов. На каждом его уровне расположено максимальное количество узлов, равное 2 i, где i – номер уровня.
2. Построение бинарного дерева
Наибольший интерес представляет задача построения дерева минимальной высоты при заданном числе узлов n. Очевидно, что минимальная высота достигается, если на всех уровнях, кроме последнего, помещается максимально возможное число узлов. Этого можно добиться, размещая очередные узлы поровну слева и справа от каждого узла. В результате будем получать деревья со следующей структурой:
n =1 n =2 n =3 n =4 n =5 n =6 n =7
Правило равномерного распределения для известного числа узлов n лучше всего сформулировать, используя рекурсию:
1) взять один узел в качестве корня;
2) построить тем же способом левое поддерево с nl = n div 2 узлами;
3) построить тем же способом правое поддерево с nr = n – nl –1 узлом.
Построенное с помощью предложенного выше алгоритма дерево будет идеально сбалансированным – для каждого его узла число узлов в правых и левых поддеревьях отличается не более чем на 1.
3. Операции над бинарным деревом
Над бинарным деревом могут быть выполнены операции:
Ø обход узлов бинарного дерева в определенном порядке;
Ø добавление некоторого поддерева в дерево;
Ø исключение некоторого поддерева из дерева;
Ø примитивные операции над узлами дерева.
Обход (прохождение) дерева используется для систематического последовательного просмотра узлов дерева. Эта операция может быть использована для контроля информации, хранящейся в древовидной структуре, а также как составная часть для выполнения других операций над деревом. Рекурсивная процедура обхода дерева включает в себя следующие шаги:
1) обработка (просмотр) корня дерева или поддерева;
2) обход левого поддерева обработанного корня;
3) обход правого поддерева обработанного корня;
Различный порядок выполнения перечисленных выше шагов определяет три процедуры обхода бинарного дерева:
1) обход сверху вниз – сначала обрабатывается корень, затем обходится его левое, затем правое поддеревья (операция UpDownRevision);
2) обход слева направо – сначала обходится левое поддерево корня, затем обрабатывается корень, затем обходится его правое поддерево (операция LeftRightRevision);
3) обход снизу вверх – обходится левое поддерево корня, затем правое, затем обрабатывается корень (операция DownUpRevision).
При обходе каждого из приведённых ниже бинарных деревьев получим по три упорядоченные последовательности:
(а) (б)
обходдерево (а)дерево (б)
сверху вниз ABDEGCFHI ´+ a / bc – d ´ ef (префиксная запись)
слева направо DBGEACHFI a + b / c ´ d – e ´ f (инфиксная без скобок)
снизу вверх DGEBHIFCA abc /+ def ´–´ (постфиксная запись)
Добавление некоторого поддерева в дерево. Для выполнения этой операции должны быть заданы: включаемое поддерево и узел исходного дерева, к которому поддерево подключается в качестве ветви. Поскольку бинарное дерево является упорядоченным, то должно быть указание на то, в качестве какой ветви (левой или правой) заданного узла должно быть подключено поддерево. Целесообразно разбить эту операцию на две: включение поддерева в качестве левой ветви заданного узла (AddLeft) и включение в качестве правой ветви заданного узла (AddRight). Ветви, в которые осуществляется включение, должны быть пустыми.
Исключение некоторого поддерева из дерева фактически представляет собой две операции: исключение поддерева из левой ветви заданного узла исходного дерева (DeleteLeft) и исключение поддерева из его правой ветви (DeleteRight). Операция возвращает адрес исключенного поддерева.
Примитивные операции над узлами бинарного дерева могут быть следующими. Addr(v) возвращает адрес узла со значением v. Если p – указатель на узел Node бинарного дерева, то операция Value(p) возвращает значение узла Node. Операции Left(p), Right(p), Father(p), Brother(p) возвращают соответственно указатели на левого сына, правого сына, отца и брата узла Node. Операции IsLeft(p) и IsRight(p) возвращают значение «истина», если Node является соответственно левым или правым сыном некоторого узла дерева, и значение «ложь» – в противном случае.
Дополнительно могут быть определены следующие операции: Create – создание пустого дерева, Clear – удаление всех узлов дерева, WriteTo (f) – вывод дерева в файл f с помощью отступов, NodesQuantity – определение числа узлов дерева.
4. Реализация бинарного дерева
При реализации дерева с помощью динамических переменных каждый элемент дерева, помимо информационной части, содержит два указателя: на левое и правое поддеревья этого элемента. Переменная ссылочного типа fRoot указывает на корневой узел дерева. Если какой-либо узел дерева не имеет левого или правого поддерева, то соответствующий указатель этого узла содержит значение nil.
Описание класса tBinaryTree:
Type
tValue = Char; // тип элемента дерева - символьный
pItem = ^tItem; // тип указателя на элемент дерева
tItem = record // элемент дерева
Value: tValue; // содержательная часть элемента дерева
Left, Right: pItem; // указатели на левое и правое поддеревья
end; // tItem
tBinaryTree= class // класс - бинарное дерево
Protected
fRoot: pItem; // поле - указатель на корень
fSize: Word; // поле - число элементов дерева
Public
// Свойство - указатель на корень дерева (доступ по чтению и записи)
property Root: pItem read fRoot write fRoot;
// Свойство - число элементов дерева (доступ по чтению и записи)
property Size: Word read fSize write fSize;
// Построение дерева из n узлов
procedure Build(n: Word; var f: Text);
// Обход дерева сверху вниз
procedure UpDownRevision(var f: Text);
// Обход дерева слева направо
procedure LeftRightRevision(var f: Text);
// Обход дерева снизу вверх
procedure DownUpRevision(var f: Text);
// Включение поддерева SubTree в левую ветвь узла Addr
procedure AddLeft(Addr: pItem; SubTree: tBinaryTree);
// Включение поддерева SubTree в правую ветвь узла Addr
procedure AddRight(Addr: pItem; SubTree: tBinaryTree);
// Исключение поддерева из левой ветви узла с адресом Addr
function DeleteLeft(Addr: pItem): tBinaryTree;
// Исключение поддерева из правой ветви узла с адресом Addr
function DeleteRight(Addr: pItem): tBinaryTree;
function Addr(v: tValue): pItem; // адрес узла со значением v
function Value(Addr: pItem): tValue; // значение узла Addr
function LeftSon(Addr: pItem): pItem; // левый сын узла Addr
function RightSon(Addr: pItem): pItem; // правый сын Addr
function Father(Addr: pItem): pItem; // отец Addr
function Brother(Addr: pItem): pItem; // брат Addr
function IsLeft(Addr: pItem): Boolean; // Addr - левый сын узла
function IsRight(Addr: pItem): Boolean; // Addr - правый сын узла
// Вывод дерева в файл f с помощью отсту пов
procedure WriteTo(var f: Text);
// Возвращение числа узлов поддерева с корнем Addr
function NodesQuantity(var Addr:PItem): Word;
function Empty: Boolean; // возвращение true, если дерево пусто
procedure Clear; // удаление всех узлов из дерева
constructor Create; // конструктор дерева
destructor Destroy; override; // деструктор дерева
end; // tBinaryTree
5. Реализация основных операций над бинарным деревом
Операции над бинарным деревом могут быть реализованы с помощью как итерационных, так и рекурсивных процедур. Поскольку дерево по своей природе является рекурсивной структурой, реализация операций обработки дерева в виде рекурсивных процедур является более наглядной и простой, поэтому там, где возможно использование рекурсии, итерационные методы рассматриваться не будут.
Особенностью реализации операции над деревом в виде метода класса является отсутствие указателя на корень обрабатываемого дерева в списке параметров метода, т.к. этот указатель является полем класса-дерева и доступен всем его методам изнутри. В то же время для реализации операции с помощью рекурсии необходимо передавать значение указателя на корень текущего поддерева обрабатываемого дерева в тело рекурсивной процедуры. Это может быть выполнено с помощью внутренней рекурсивной подпрограммы для всех процедур-операций, реализуемых рекурсивно. Сам метод при этом остается нерекурсивным и фактически содержит в своем теле лишь вызов внутренней рекурсивной процедуры.
Построение бинарного дерева минимальной высоты с числом узлов n предусматривает, что из входного потока (в данном случае – из текстового файла) считываются значения, размещаемые в узлах строящегося дерева.
procedure tBinaryTree.Build(n: Word; var f: Text);
// Построение дерева минимальной высоты из n узлов из файла f
function BuildTree(n: Word): pItem; // рекурсивная функция построения
Var
Item: pItem;
NLeft, NRight: Word;
v: tValue;
Begin
if n <> 0
Then begin
NLeft:= n div 2; NRight:= n - NLeft-1;
Item:= New(pItem);
Read(f, v);
if Eoln(f) then ReadLn(f);
Item^.Value:= v;
Item^.Left:= BuildTree(NLeft);
Item^.Right:= BuildTree(NRight);
BuildTree:= Item; end
else BuildTree:= nil;
end; // function BuildTree
Begin
fRoot:= BuildTree(n); fSize:=n;
end; // procedure tBinaryTree.Build
Обход дерева сверху вниз выполняется с помощью процедуры:
procedure tBinaryTree.UpDownRevision(var f: Text);
// Обход бинарного дерева сверху вниз и вывод результатов в файл f
procedure UpDown(Item: pItem); // рекурсивная процедура обхода
Begin
if Item <> nil
Then begin
Write(f,Item^.Value); // 1. Обработка узла - вывод в файл f
UpDown(Item^.Left); // 2. Обход левого поддерева
UpDown(Item^.Right); // 3. Обход правого поддерева
end;
end; // procedure UpDown
Begin
UpDown(fRoot);
Writeln(f);
end; // procedure tBinaryTree.UpDownRevision
В процедурах обхода слева направо (LeftRightRevision) и снизу вверх (DownUpRevision) изменится только последовательность выполнения основных операций (1, 2 и 3) в соответствии со способом обхода.
Включение поддерева в левую ветвь узла с адресом Addr может быть выполнено с помощью следующего метода:
procedure tBinaryTree.AddLeft(Addr: pItem; SubTree: tBinaryTree);
// Включение поддерева SubTree в левую ветвь узла с адресом Addr
Begin
if Addr^.Left <> nil
then WriteLn('Левая ветвь узла не пуста. Включение невозможно')
Else begin
Addr^.Left:= SubTree.Root;
// увеличение числа узлов базового дерева на число узлов поддерева
Inc(fSize,SubTree.Size);
// поддерево становится пустым
SubTree.Root:= nil; SubTree.Size:= 0;
end;
end; // procedure tBinaryTree.AddLeft
Метод исключения поддерева из левой ветви узла с адресом Addr возвращает новое (исключенное) поддерево:
function tBinaryTree.DeleteLeft(Addr:pItem):tBinaryTree;
// Исключение и возвращение поддерева из левой ветви узла с адресом Addr
Begin
Result:= tBinaryTree.Create;
Result.Root:= Addr^.Left;
Result.Size:= NodesQuantity(Addr^.Left);
Dec(fSize,Result.Size);
Addr^.Left:= nil;
end; // function tBinaryTree.DeleteLeft
Включение и исключение для правой ветви узла выполняются аналогично. Узел с адресом Addr должен присутствовать в дереве.
Вывод дерева. Дерево изображается с помощью отступов: для каждого узла поддерева k-го уровня сначала печатается его правое поддерево, затем значение самого узла, выделенное отступом в k пробелов, затем печатается его левое поддерево. Пустое дерево не выводится. Вывод дерева выполняется с помощью внутренней рекурсивной процедуры вывода в текстовый файл, имя которого передается через список параметров процедуры.
procedure tBinaryTree.WriteTo(var f: Text);
// Вывод дерева в файл f c помощью отступов
procedure WriteTree(Item: pItem; Step: Byte);
// Рекурсивная процедура вывода элемента Item со Step пробелами
Begin
if Item <> nil
Then begin
WriteTree(Item^.Right, Step+2);
WriteLn(f,' ':Step, Item^.Value);
WriteTree(Item^.Left, Step+2);
end;
end; // procedure WriteTree
Begin
WriteTree(fRoot, 5);
end; // procedure tBinaryTree.WriteTo
Остальные операции над бинарным деревом могут быть реализованы на основе уже рассмотренных методов исследования дерева.
Функция Father(Addr), возвращающая указатель на отца узла с адресом Addr, может быть реализована с использованием рекурсивной процедуры обхода дерева сверху вниз, причем обработка узла при этом заключается в сравнении указателей сыновей этого узла с заданным адресом Addr. Если ни один из узлов дерева не имеет сыновей с адресом Addr, то узел с адресом Addr – корень дерева, и функция Father(Addr) должна возвращать значение nil. Напомним, что при выполнении этой и подобных операций предполагается, что узел с указателем Addr присутствует в дереве. При реализации операций эту ситуацию можно анализировать дополнительно.
Функция Brother(Addr), возвращающая указатель на брата узла Addr, может сначала вызывать метод Father(Addr) для определения адреса отца этого узла, а затем сравнивать адреса сыновей найденного предка с адресом Addr и выдавать не совпадающий с Addr адрес сына в качестве результата операции.
Функции IsLeft(Addr) и IsRight(Addr), возвращающие значение «истина», если узел с адресом Addr является соответственно левым или правым сыном некоторого узла дерева, также реализуются путем вызова метода Father(Addr) и последующего анализа адресов его сыновей.
В конструкторе Create указателю на корень дерева fRoot присваивается значение nil и полю fSize – значение 0.
Процедура удаления всех узлов дерева Clear может быть реализована с использованием рекурсивной процедуры обхода дерева снизу вверх, обработка текущего узла с указателем Item при этом заключается в удалении его из памяти ЭВМ процедурой Dispose(Item). После вызова рекурсивной процедуры обхода указатель корня дерева должен получить значение nil, а поле fSize – значение 0
Деструктор Destroy класса tBinaryTree содержит вызов метода Clear.
Функция NodesQuantity(Addr) вычисления количества узлов поддерева с корнем Addr может быть реализована на основе любой процедуры обхода поддерева, начиная от узла с адресом Addr, обработка узла будет заключаться в увеличении на единицу числа вершин поддерева.
6. Дерево выражения
Часто информация, содержащаяся в узлах бинарного дерева, имеет отличающиеся атрибуты либо различное назначение. Такие деревья называются разнородными. Примером разнородного дерева является дерево, используемое для вычисления арифметических выражений.
Дерево выражения можно строить по инфиксной записи, но при этом алгоритм построения должен учитывать приоритеты выполнения операций и наличие скобок. Более простым путем является предварительное преобразование арифметического выражения из инфиксной записи в префиксную с использованием стека.
При построении дерева префиксная запись сканируется слева направо и дерево строится также слева направо.
Рекурсивный алгоритм построения дерева выражения может быть описан следующим образом:
1) получить очередной символ префиксной записи выражения и поместить его в узел дерева;
2) если этот символ – операция,
то построить таким же способом его левое поддерево,
построить таким же способом его правое поддерево,
иначе конец алгоритма.
Дерево выражения может строиться и по постфиксной записи, в этом случае запись выражения сканируется справа налево и дерево строится также справа налево.
Дерево выражения может быть реализовано как наследник бинарного дерева с символьным или строковым значением содержательного поля Value элемента дерева. Метод Build дерева выражения перекрывает одноименный метод бинарного дерева, так как реализуется иначе; все остальные методы бинарного дерева наследуются.
Type
tOperatorSet = set of '*'.. '/'; // тип - множество операторов
tExprTree = class (tBinaryTree) // класс - дерево выражения
Private
fOperators: tOperatorSet; // поле - множество операторов
Public
function IsOperator(ExprEl: tValue):Boolean; // элемент выражения - оператор?
procedure Build(var f: Text); // построение дерева выражения
constructor Create; // создание пустого дерева
end; // tExprTree
Метод IsOperator проверяет, принадлежит ли очередной элемент выражения к множеству допустимых операторов fOperators. Метод Build дерева выражения перекрывает одноименный метод бинарного дерева, так как реализуется иначе. Конструктор Create помимо создания пустого дерева задает множество Operators разрешенных в данном выражении операторов. Все остальные методы бинарного дерева наследуются.
В простейшем случае – для операндов и операторов, представляемых одним символом, – процедура построения дерева выражения по его префиксной записи, хранящейся в текстовом файле, имеет вид:
procedure TExprTree.Build(var f: Text);
// Построение дерева выражения по его префиксной записи в файле f
function BuildTree: pItem; // рекурсивная функция построения
Var
Item: pItem; // элемент дерева выражения
Symbol: tValue; // символ выражения
Begin
if not Eof(f)
Then begin
Read(f, Symbol); if Eoln(f) then ReadLn(f);
Item:= New(pItem); Item^.Value:= Symbol;
if IsOperator(Symbol)
then begin // cимвол - оператор
Item^.Left:= BuildTree; Item^.Right:= BuildTree; end
else begin // cимвол - операнд
Item^.Left:= Nil; Item^.Right:= nil;
end;
BuildTree:= Item;
end;
end; // function BuildTree
Begin
fRoot:= BuildTree;
end; // procedure TExprTree.Build
7. Дерево поиска
Бинарные деревья часто используются для представления множества данных, среди которых идет поиск элементов по уникальному ключу. Если дерево организовано так, что для каждого узла t все ключи его левого поддерева меньше ключа t, а все ключи правого поддерева t больше ключа t, то такое дерево будем называть деревом поиска. В нем легко найти элемент с нужным ключом – достаточно, начав с корня, двигаться в левое или правое поддерево на основании сравнения заданного ключа с ключом текущего узла. Известно, что из n элементов можно построить бинарное дерево с высотой не более log2 n, поэтому, если дерево идеально сбалансировано, поиск среди его n элементов выполняется максимум за log2 n сравнений. Подобные деревья широко используются и для сортировки больших массивов данных, так как обход дерева поиска слева направо дает отсортированную в порядке возрастания последовательность ключей.
При обходе слева направо дерева поиска, приведенного ниже, получается последовательность: 1, 4, 8, 9, 11, 15, 20.
8. Операции над деревом поиска
Над деревом поиска могут быть выполнены все операции, определенные для бинарного дерева. Но в основном к дереву поиска применяются операции, определяемые особенностями его организации:
Ø поиск элемента с заданным ключом Key в дереве и возвращение адреса элемента, если он найден, в противном случае возвращается значение nil – операция Addr(Key);
Ø поиск по дереву с включением – поиск элемента с ключом Key в дереве, подключение узла с этим ключом, если поиск был неудачным, и возвращение адреса элемента с заданным ключом – операция Search(Key);
Ø поиск по дереву с исключением – поиск элемента с заданным ключом в дереве и исключение этого элемента, если он найден, – операция Delete(Key); после исключения дерево должно остаться деревом поиска.
Для построения дерево поиска, можно использовать операцию поиска по дереву с включением Search(Key), считывая из входного потока элементы с заданными ключами и включая их в дерево поиска. Операция Search(Key) может быть построена таким образом, что она будет включать в дерево элемент и в том случае, если он уже существует в дереве. Использование такой операции для построения дерева поиска позволяет построить дерево с повторяющимися ключами.
9. Реализация дерева поиска
В общем случае каждый элемент дерева поиска может содержать в содержательной части Value специальное поле, называемое ключом этого элемента. Для упрощения описания будем считать, что поле Value является ключом элемента дерева. В этом случае класс tSearchTree может быть описан как наследник класса tBinaryTree:
Type
tSearchTree = class (tBinaryTree) // класс - дерево поиска
function Addr(Key: tValue): pItem; // поиск элемента с ключом Key
function Search(Key: tValue): pItem; // поиск с включением
procedure Delete(Key: tValue); // поиск с исключением
procedure Build(var f: Text); // построение дерева поиска
end; // tSearchTree
Метод Build дерева поиска перекрывает одноименный метод бинарного дерева, поскольку реализуется иначе. Поле fRoot и все остальные методы бинарного дерева наследуются деревом поиска. Методы Locate, Search и Delete являются новыми, расширяющими возможности дерева поиска по сравнению с обычным бинарным деревом.
10. Реализация операций над деревом поиска
Поиск элемента с ключом Key может быть выполнен с помощью итерации, так как поиск идет по единственному пути от корня к искомому узлу:
function tSearchTree.Addr(Key: tValue): pItem; // адрес элемента с ключом Key
Var
Item: pItem;
Begin
if Empty
then Addr:= nil
Else begin
Item:= fRoot;
while (Item<> nil) and (Item^.Value<>Key) do
if Key<Item^.Value
then Item:= Item^.Left // спуск по левой ветви
else Item:= Item^.Right; // спуск по правой ветви
Addr:= Item;
end;
end; // function tSearchTree.Addr
Метод, реализующий поиск по дереву с включением:
function tSearchTree.Search(Key: tValue):pItem;
// Поиск элемента с заданным ключом Key с включением
procedure IncKey(var Item: pItem); // рекурсивная процедура поиска
Begin
if Item= nil
then begin // элемента с ключом Key нет: включение его в качестве листа
Item:= New(pItem); Item^.Value:= Key;
Item^.Left:= nil; Item^.Right:= nil;
Result:= Item; Inc(fSize);
End
Else
if Key<Item^.Value then IncKey(Item^.Left) // поиск слева
Else
if Key>Item^.Value then IncKey(Item^.Right) // поиск справа
else Result:= Item; // элемент найден
end; // procedure IncKey
Begin
IncKey(fRoot);
end; // function tSearchTree.Search
При реализации процедуры поиска с исключением необходимо рассмотреть три ситуации и три способа поведения процедуры после исключения элемента:
ситуация 1: элемента с ключом Key нет в дереве, в этом случае дерево остается неизменным;
ситуация 2: элемент с ключом Key имеет не более одного потомка – после исключения ближайший потомок поднимается на его место;
ситуация 3: элемент с ключом Key имеет двух потомков, в этом случае исключаемый элемент нужно заменить самым правым элементом его левого поддерева, имеющим не более одного потомка. Этому условию соответствует элемент, предшествующий исключаемому в обходе слева направо. После исключения узла с двумя потомками дерево останется деревом поиска и в том случае, если заменить исключаемый элемент самым левым элементом его правого поддерева, имеющим не более одного потомка. Этому условию соответствует элемент, следующий за исключаемым в обходе слева направо.
Ниже приведено исходное дерево поиска (а). Дерево (б) получается из дерева (а) после исключения элемента 15 и замены его элементом 11 – самым правым элементом левого поддерева узла 15 (в процедуре обхода слева направо он предшествует узлу 15). Дерево (в) получается из дерева (а) после исключения элемента 15 и замены его элементом 18 – самым левым элементом правого поддерева узла 15 (в процедуре обхода следует за узлом 15).
(а) (б) (в)
procedure tSearchTree.Delete(Key: tValue);
// Поиск элемента с заданным ключом Key с исключением
procedure DelKey(var Item: pItem); // основная рекурсивная процедура
Var
DelItem: pItem; // указатель на исключаемый элемент
procedure Del(var Addr: pItem);
// Вспомогательная рекурсивная процедура. Возвращает адрес самого
// правого элемента левого поддерева удаляемого узла DelItem
Begin
if Addr^.Right<> nil
then Del(Addr^.Right) // поиск правого элемента
Else begin
// Найден самый правый элемент левого поддерева DelItem
DelItem^.Value:= Addr^.Value; DelItem:= Addr; Addr:= Addr^.Left;
end;
end; //procedure Del
Begin
if Item= nil
then WriteLn('Узел с ключом',Key,'не найден.') // ситуация 1
Else
if Key<Item^.Value
then DelKey(Item^.Left) // поиск слева
Else
if Key>Item^.Value
then DelKey(Item^.Right) // поиск справа
Else begin
// э лемент найден, исключение Item^
DelItem:= Item;
if DelItem^.Right= nil
then Item:= DelItem^.Left // ситуация 2
Else
if DelItem^.Left= nil
then Item:= DelItem^.Right // ситуация 2
else Del(DelItem^.Left); // ситуация 3 – поиск предшественника
Dispose(DelItem); Dec(fSize); // удаление перемещенного элемента
end; // конец исключения Item^
end; // procedure DelKey
Begin
DelKey(fRoot);
end; // procedure tSearchTree.Delete
В методе tSearchTree.Delete используется основная рекурсивная процедура DelKey, которая собственно и выполняет поиск в дереве с удалением. Вспомогательная рекурсивная процедура Del начинает работать только в ситуации 3. Она «спускается» вдоль правой ветви левого поддерева элемента с указателем DelItem, который нужно исключить, и заменяет поле Value элемента DelItem^ на соответствующее значение из самого правого элемента Addr^ левого поддерева, после чего от элемента Addr ^ можно освободиться.
Построение дерева поиска заключается в считывании из входного потока (в данной реализации из текстового файла) элементов с заданными ключами и включении их в дерево поиска с использованием операции поиска по дереву с включением Search(Key).
procedure tSearchTree.Build(var f: Text); // построение дерева поиска
Var
Key: tValue;
Begin
while not Eof(f) do begin
Read(f, Key); if Eoln(f) then ReadLn(f);
Search(Key); // функция Search вызывается как процедура
end;
end; //procedure tSearchTree.Build
11. Сбалансированные деревья
Поиск по дереву является эффективным только в том случае, если дерево будет идеально сбалансированным, так как среднее число сравнений, необходимых для обнаружения ключа, в идеально сбалансированном дереве равно log2 n. Если дерево вырождается в список, то эта величина примерно равна n /2. Анализ показывает, что процедура балансировки, восстанавливающая после каждого случайного включения идеально сбалансированное дерево, не всегда является выгодной, так как реализуется довольно сложно.
Возможным выходом из положения является введение менее строгого понятия сбалансированности. Это может привести к более простой процедуре балансировки за счет незначительного увеличения времени поиска. Одно из таких определений сбалансированного дерева было предложено Г.М. Адельсон-Вельским и Е.М. Ландисом. Их критерий сбалансированности сформулирован следующим образом.
Дерево называется сбалансированным, если высоты двух поддеревьев каждого из его узлов отличаются не более чем на единицу.
Деревья, удовлетворяющие такому условию, часто называют АВЛ-деревьями (по имени их открывателей). Мы их будем называть сбалансированными деревьями. В таких деревьях, как доказали их авторы, операция поиска выполняется за время, пропорциональное log2 n.
12. Включение в сбалансированное дерево
Есть корень r, левое (L) и правое (R) поддеревья с высотами hL и hR соответственно. Что может произойти при включении в сбалансированное дерево нового узла?
Предположим, включение в L нового узла приведет к увеличению на 1 его высоты; тогда возможны три ситуации:
1) hL = hR: после включения L и R станут разной высоты, но критерий сбалансированности не будет нарушен;
2) hL < hR: после включения L и R станут равной высоты, т.е. сбалансированность улучшится;
3) hL > hR: после включения критерий сбалансированности нарушится и дерево необходимо перестраивать.
Например, в сбалансированное дерево, приведенное ниже, узлы с ключами 9 и 11 можно включить, не нарушая его сбалансированности. Включение узлов 1, 3, 5 или 7 потребует последующей балансировки.
Существуют лишь 2 различные возможности устранения несбалансированности, возникшей из-за включения, требующие индивидуального подхода (оставшиеся могут быть выведены из них на основе симметрии). Эти случаи показаны ниже. Прямоугольниками обозначены поддеревья, причем «добавленная» при включении высота заштрихована.
Первый случай возникает, когда в дерево на числовом примере включаются узлы с ключами 1 или 3. Ситуация, характерная для второго случая