Рис. 13.1 Двоичные деревья поиска. Левое поддерево произвольной вершины х содержит ключи, не превосходящие кеу[х], правое - не меньшие кеу[х]. Разные двоичные деревья поиска могут представлять одно и то же множество. Время выполнения (в худшем случае) большинства операций пропорционально высоте дерева, (а) Двоичное дерево поиска высоты 2 с 6 вершинами, (б) Менее эффективное дерево высоты 4, содержащее те же ключи.

13.1. Что такое двоичное дерево поиска?

В двоичном дереве поиска (binary search tree; пример приведён на рис. 13.1) каждая вершина может иметь (или не иметь) левого и правого ребёнка; каждая вершина, кроме корня, имеет родителя. При представлении с использованием указателей мы храним для каждой вершины дерева, помимо значения ключа key и дополнительных данных, также и указатели left, right и р (левый ребёнок, правый ребёнок, родитель). Если ребёнка (или родителя - для корня) нет, соответствующее поле содержит NIL.

Ключи в двоичном дереве поиска хранятся с соблюдением свойства упорядоченности (binary-search-tree property):

Пусть х - произвольная вершина двоичного дерева поиска. Если вершина у находится в левом поддереве вершины х, то кеу[у] кеу[х]. Если у находится в правом поддереве х, то кеу[у] кеу[х].

Так, на рис. 13.1(a) в корне дерева хранится ключ 5, ключи 2, 3 и 5 левом поддереве корня не превосходят 5, а ключи 7 и 8 в правом - не меньше 5. То же самое верно для всех вершин дерева. Например, ключ 3 на рис. 13.1(a) не меньше ключа 2 в левом поддереве и не больше ключа 5 в правом.

Свойство упорядоченности позволяет напечатать все ключи в неубывающем порядке с помощью простого рекурсивного алгоритма (называемого по-английски inorder tree walk). Этот алгоритм печатает ключ корня поддерева после всех ключей его левого поддерева, но перед ключами правого поддерева. (Заметим в скобках,

что порядок, при котором корень предшествует обоим поддеревьям, называется preorder; порядок, в котором корень следует за ними, называется postorder.)

Вызов Inorder-Tree-Walk [root[T]) печатает (в указанном порядке) все ключи, входящие в дерево Г с корнем root[T].

Inorder-Tree-Walk (ж)

1if ж ф nil

2then Inorder-Tree-Walk (left[x\)

3напечатать key[x]

4Inorder-Tree-Walk (right[x])

К примеру, для обоих деревьев рис. 13.1 будет напечатано 2,3,5,5,7,8. Свойство упорядоченности гарантирует правильность алгоритма (индукция по высоте поддерева). Время работы на дереве с га вершинами есть в (га): на каждую вершину тратится ограниченное время (помимо рекурсивных вызовов) и каждая вершина обрабатывается один раз.

Упражнения

13.1-1 Нарисуйте двоичные деревья поиска высоты 2, 3, 4, 5 и 6 для одного и того же множества ключей {1, 4, 5,10,16,17, 21}.

13.1-2 Кучи из раздела 7.1 также были двоичными деревьями, и требование упорядоченности там тоже было. В чём разница между тем требованием и теперешним? Как вы думаете, можно ли напечатать элементы двоичной кучи в неубывающем порядке за время О(га)? Объясните ваш ответ.

13.1-3 Напишите нерекурсивный алгоритм, печатающий ключи в двоичном дереве поиска в неубывающем порядке. (Указание: Простое решение использует в качестве дополнительной структуры стек; более изящное решение не требует стека, но предполагает, что можно проверять равенство указателей.)

13.1-4 Напишите рекурсивные алгоритмы для обхода деревьев в различных порядках (preorder, postorder). Как и раньше, время работы должно быть О (га) (где га - число вершин).

13.1-5 Покажите, что любой алгоритм построения двоичного дерева поиска, содержащего заданные га элементов, требует (в худшем случае) времени fi(ralgra). Воспользуйтесь тем, что сортировка га чисел требует fi(ralgra) действий.

Рис. 13.2 Поиск в двоичном дереве. Ища ключ 13, мы идём от корня по пути 15 -> 6 -г> 7 -г> 13. Чтобы найти минимальный ключ 2, мы всё время идём налево; чтобы найти максимальный ключ 20 - направо. Для вершины с ключом 15 следующей будет вершина с ключом 17 (это минимальный ключ в правом поддереве вершины с ключом 15). У вершины с ключом 13 нет правого поддерева; поэтому, чтобы найти следующую за ней вершину, мы поднимаемся вверх, пока не пройдём по ребру, ведущему вправо-вверх; в данном случае следующая вершина имеет ключ 15.

13.2. Поиск в двоичном дереве

В этом разделе мы покажем, что двоичные деревья поиска позволяют выполнять операции Search, Minimum, Maximum, Successor и Predecessor за время 0(h), где h - высота дерева.

Поиск

Процедура поиска получает на вход искомый ключ к и указатель ж на корень поддерева, в котором производится поиск. Она возвращает указатель на вершину с ключом к (если такая есть) или специальное значение nil (если такой вершины нет).

Tree-Search (ж, к)

1if ж = nil или к = кеу[х]

2then return ж

3if к < кеу[х]

4then return Tree-Search(left[x], к)

5else return Tree-Search(right[x], k)

В процессе поиска мы двигаемся от корня, сравнивая ключ к с ключом, хранящимся в текущей вершине ж. Если они равны, поиск завершается. Если к < кеу[х], то поиск продолжается в левом поддереве ж (ключ к может быть только там, согласно свойству упорядоченности). Если к > кеу[х], то поиск продолжается в правом поддереве. Длина пути поиска не превосходит высоты дерева,