15.3. Оптимальные деревья бинарного поиска

Упорядоченным деревом называется ориентированное дерево, для которого определен порядок сыновей любой вершины дерева. Обычно мы изображаем упорядоченное дерево так, что корень размещается вверху, а сыновья каждой вершины расположены в соответствии с порядком слева направо. Для бинарного упорядоченного дерева поддерево, корень которого является левым сыном вершины v, называется левым поддеревом вершины v. Аналогично определяется правое поддерево вершины v. Пусть — множество элементов, упорядоченных следующим образом: Бинарным деревом поиска для множества А является упорядоченное бинарное дерево, в котором каждая вершина v так помечена элементом множества А, что 1) для каждого и в левом поддереве вершины для каждого и в правом поддереве вершины для каждого элемента множества А существует точно одна такая вершина v, что . Предположим, А является подмножеством универсума S. Тогда пусть — такое множество, что 1) представляет множество всех элементов для которых

2) представляет собой множество всех элементов для которых

3) представляет множество всех элементов для которых

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

Например, деревья, представленные на рис. 15.7, являются двумя различными расширенными деревьями бинарного поиска над множеством Отметим, что в расширенном дереве бинарного поиска листья появляются слева направо в порядке . В дальнейшем мы будем называть расширенное дерево бинарного поиска для множества А просто деревом бинарного поиска для А.

Пусть дано подмножество А универсума и дерево Т бинарного поиска для А. Множество может быть множеством всех слов над английским алфавитом, а упорядочение может быть лексикографическим порядком. Предположим, что нам необходимо определить, принадлежит ли элемент множеству А. Сравним с элементом, который соответствует корню дерева Т.

Рис. 15.7. Примеры деревьев бинарного поиска.

При этом могут возникнуть четыре случая, в соответствии с которыми мы продолжаем:

Случай 1. Корень отсутствует (дерево Т бинарного поиска пусто). Следовательно, не принадлежит А, и поиск завершается безуспешно.

Случай равен элементу, соответствующему корню. Следовательно, поиск завершается успешно.

Случай меньше элемента, соответствующего корню. Поиск продолжается ниже в левом поддереве корня.

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

Определим глубину вершины v как длину пути из корня до v. Тогда можно отметить, что число сравнений, выполняемых до того, как поиск завершается успешно во внутренней вершине v дерева Т, на единицу больше глубины v. С другой стороны, если поиск завершается безуспешно в листе, то число выполненных сравнений равно глубине листа.

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

Например, если , то стоимость дерева, изображенного на рис. 15.7, а, составит . Стоимость дерева, изображенного на рис. 15.7, б, составит

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

Пусть Т — оптимальное дерево бинарного поиска для весов Если — элемент, соответствующий корню дерева Т, то левое поддерево корня дерева Т является оптимальным деревом бинарного поиска для весов а правое поддерево корня дерева Т — оптимальным деревом бинарного поиска для весов Пусть для 0 является оптимальным деревом бинарного поиска для множества Пусть — корень дерева — стоимость дерева . Вес дерева определяется как будет деревом, состоящим из листа Поэтому

Рис. 15.8. Поддерево с корнем

Предположим, что — корень дерева . Тогда, как мы уже видели, левое поддерево с корнем является деревом которое в свою очередь является оптимальным деревом бинарного поиска для множества а правое поддерево с корнем является деревом которое в свою очередь является оптимальным деревом бинарного поиска для множества (Рис. 15.8). Так как глубина вершины в дереве Ту на единицу больше ее глубины в дереве или то отсюда следует, что

    (15.27)

Ясно, что мы можем найти корень дерева определив величину которая минимизирует сумму (15.27). Это рассуждение образует основу алгоритма 15.4, который позволяет рассчитать в порядке возрастания величин Этот алгоритм предложен Гильбертом и Муром [15.19].

Алгоритм 15.4. Оптимальное дерево бинарного поиска (Гильберт и Мур).

S1. Даны неотрицательные веса Для положить

S2. Для выполнить шаг

S3. Для выполнить шаг

S4. Положить

Пусть для которого сумма минимальна.

Положить

Вычислив с помощью приведенного выше алгоритма, мы можем легко построить дерево используя следующую процедуру:

1. — корень дерева , Если , то имеет в качестве левого сына , а в качестве правого —

2. Рассмотрим внутреннюю вершину . Если , то имеет в качестве левого сына, а — в качестве правого. Проиллюстрируем алгоритмы 15.4 и приведенную выше процедуру для построения оптимального дерева бинарного поиска.

Тавлица 15.1

Рассмотрим четыре элемента с весами а также В табл. 15.1 указаны значения вычисленные на основе алгоритма 15.4. В этой таблице элементы в строке вычисляются слева направо. Вычисления в какой-либо строке начинаются только после вычислений всех элементов предыдущей строки. На рис. 15.9 представлено соответствующее оптимальное дерево бинарного поиска.

Рис. 15.9. Построение оптимального дерева бинарного поиска.

Легко показать, что алгоритм 15.4 имеет сложность, равную а процедура построения дерева по таблице — сложность Таким образом, оптимальное дерево бинарного поиска можно построить за время

Кнут [15.20] показал, что корень дерева лежит между корнями Другими словами, Поэтому на шаге поиск величины m можно производить в пределах Сложность алгоритма 15.4 с такой модификацией становится равной Несколько обобщений алгоритма Кнута обсуждаются в работе [15.21].

Авторы работы [15.22] предложили О -алгоритм для построения оптимального дерева бинарного поиска в частном случае, когда Кнут [15.24] показал, что этот алгоритм можно выполнить за время . Другой алгоритм, тесно связанный с алгоритмом — Такера со сложностью для этой же задачи, предложен в работе [15.25]. Этот алгоритм легче проверить: он основан на использовании вариационных методов.

Проведены обширные исследования методов поиска с рассмотрением некоторых вопросов, касающихся оптимальных деревьев бинарного поиска. Детальное обсуждение этих тем и связанная с ними библиография приведены в работах [15.24, 15.26, 15.27].