3.2.3 Двоичные деревья поиска Основные операции

Обычные деревья не дают выигрыша при хранении множества значений. При поиске элемента все равно необходимо просмотреть все дерево. Однако можно организовать хранение элементов в дереве так, чтобы при поиске элемента достаточно было просмотреть лишь часть дерева. Для этого надо ввести следующее требование упорядоченности дерева:

Двоичное дерево упорядочено, если для любой вершины x справедливо такое свойство: все элементы, хранимые в левом поддереве, меньше элемента, хранимого в x, а все элементы, хранимые в правом поддереве, больше элемента, хранимого в x.

Важное свойство упорядоченного дерева: все элементы его различны. Если в дереве встречаются одинаковые элементы, то такое дерево является частично упорядоченным.

В дальнейшем будет идти речь только о двоичных упорядоченных деревьях, слово «упорядоченный» будет опускаться.

Деревья поиска (search trees) позволяют выполнять следующие операции с дина- мическими множествами: Search (поиск), Minimum (минимум), Maximum (мак- симум), Predecessor (предыдущий), Successor (следующий), Insert (вста- вить) и Delete (удалить). Таким образом, дерево поиска может быть исполь- зовано и как словарь, и как очередь с приоритетами.

Время выполнения основных операций пропорционально высоте дерева. Если двоичное дерево «плотно заполнено» (все его уровни имеют максимально возмож- ное число вершин), то его высота (и тем самым время выполнения операций) пропорциональна логарифму числа вершин. Напротив, если дерево представля- ет собой линейную цепочку из n вершин, это время вырастает до .

Конечно, возникающие на практике двоичные деревья поиска могут быть далеки от случайных. Однако, приняв специальные меры по балансировке де- ревьев, можно гарантировать, что высота дерева с n вершинами будет O(log n).

Реализация операций будет рассматриваться для двоичных деревьев, представленных как динамическая структура.

Реализацию этих операций приведем в виде соответствующих процедур.

Поиск

Алгоритм поиска можно записать в рекурсивном виде. Если искомое значение Item меньше Tree^.Data, то поиск продолжается в левом поддереве, если равен – поиск считается успешным, если больше – поиск продолжается в правом поддереве; поиск считается неудачным, если достигли пустого поддерева, а элемент найден не был.

function TreeSearch(Item: TypeElement; Tree: PTree): boolean;

{Поиск вершины дерева, содержащую значение Item}

var

Current: PTree;

begin

TreeSearch := False;

if Tree <> nil then begin {Дерево не пустое}

Current := Tree;

if Current^.Data = Item then {Вершина найдена}

TreeSearch := True

else

if Current^.Data > Item then {Ищем в левом поддереве}

TreeSearch := TreeSearch(Item, Current^.Left)

else {Ищем в правом поддереве}

TreeSearch := TreeSearch(Item, Current^.Right);

end;

end;

Листинг 3.15 – Процедура поиска в двоичном дереве на языке Pascal

Листинг 3.24 – Рекурсивная процедура поиска в двоичном дереве поиска

Можно написать аналогичную нерекурсивную функцию. Она позволит избежать избыточного хранения информации. Каждый рекурсивный вызов размещает в стеке локальные переменные Item и Tree, а также адрес точки возврата из подпрограммы. В нерекурсивном варианте можно обойтись одной переменной Item и одной переменной Tree.

Листинг 3.25 – Нерекурсивная (итеративная) процедура поиска в двоичном дереве поиска