п элементов можно организовать в бинарное дерево с высот не более чем log п. Поэтому для поиска среди п элемец может потребоваться не более logn сравнений, если дер!** идеально сбалансировано. Очевидно, что дерево - HamL более подходящая форма организации такого множества д/° ных, чем линейный список, который рассматривался в пред дущем разделе.

Рис. 4.25. Дерево поиска с барьером.

Так как этот поиск проходит по единственному пути зн корня к искомому узлу, его можно запрограммировать с помощью итерации (4.46):

function 1ос{х: integer; t. ref): ref;

ywcfound: boolean; begin found := false;

while (t Ф nil) Л -founduo

begin

if t].key = X then found := true else if t.key > X then t := t\.left else t := t\.right end;

loc := t

Функция loc {x, t) имеет значение nil, если в дереве с К^Р^ нем t не найдено ключа со значением х. Так же как в поиска по списку, сложность условия окончания цикла

(4.46)

пяет искать лучшее решение. При поиске по списку <;1дце его помещается барьер. Этот прием можно применить случае поиска по дереву. Использование ссылок позво- L связать все терминальные узлы дерева с одним и тем же л gpOM. Полученная структура - это уже не просто дерево, скор Д^Р^во, все листья которого прицеплены внизу к од- якорю (см. рис. 4.25). Барьер можно также считать тИМ представлением- -всех внешних (специальных) узлов, оторыми дополняется исходное дерево (см. рис. 4.19). Порученная в результате упрощенная процедура поиска описана

Ьжт.1ос{х\ integer, t: ref). ref-, 1 begin s\.l<:ey :== л; {барьер]

while t\.key Ф x do ,

iix < t\.key<U!im t :== ft-e/felse t := t].right, loc := t

Отметим, что если в дереве с корнем t не найдено ключа со значением х, то в этом случае-/ос (ж, f) принимает значение S, т. е. ссьшки на барьер. Ссылка на s просто принимает на себя роль ссылки nil.

4.4.3. Поиск по дереву с включением

Возможности техники динамического размещения переменных с доступом к ним через ссылки вряд ли полностью проявляются в тех примерах, где построенная структура данных остается неизменной. Более подходящими примерами служат задачи, в которых сама структура дерева изменяется,

е. дерево растет и/или уменьшается во время выполнения программы. Это также случай, когда другие представления Данных, такие, как массив, не подходят и когда дерево с эле-чВДтами, связанными ссылками, как раз и есть подходящая структура.

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

нужно установить число появлений каждого слова. Это значает, что, начиная с пустого дерева, каждое слово ищется и^,Реве. Если оно найдено, увеличивается его счетчик появле-

если нет - в дерево вставляется новое слово (с началь-

значением счетчика, равным 1), Мы называем эту задачу.

поиском по дереву с включением. Предполагаются следу описания типов:

type rtf =3 \word; word = record

key. integer; count: integer; left, right: ref

(4.48)

Считая, кроме того, что у нас есть исходный файл ключей f г переменная root указывает на корень дерева поиска, мы можем записать программу следующим образом:

rcsct{f);-

while -Tcofif) do

begin readif, x); search{x,rooi) end

(4.49)

Определение пути поиска здесь вновь очевидно. Но если он приводит в тупик , т. е. к пустому поддереву, обозначен-

Рис. 4.26. Включение в упорядоченное бинарное дерево.

ному ссылочным значением nil, то данное слово нужно встз вить в дерево на место пустого поддерева. Рассмотрим, в^ пример, бинарное дерево, показанное на рис. 4.26, и вклК ние в него слова РаиЬ>. Результат показан пунктирными ниями на том же рисунке.

Целиком работа алгоритма приведена в программе * Дроцесс поиска представлен в виде рекурсивной процеДУР *