4.5. ОПТИМАЛЬНЫЕ ДЕРЕВЬЯ ДВОИЧНОГО ПОИСКА

В разд. 4.3 по данному множеству являющемуся подмножеством некоторого большого универсального множества строилась структура данных, позволяющая эффективно выполнить последовательность а, составленную только из операций ПРИНАДЛЕЖАТЬ. Рассмотрим снова эту задачу, но теперь предположим, что кроме множества задается для каждого вероятность появления в а операции ПРИНАДЛЕЖАТЬ . Теперь нам хотелось бы построить дерево двоичного поиска для так, чтобы последовательность а операций ПРИНАДЛЕЖАТЬ можно было выполнить в префиксном режиме с наименьшим средним числом сравнений.

Пусть элементы множества в порядке возрастания и вероятность появления в о операции ПРИНАДЛЕЖАТЬ . Пусть вероятность появления в а операции ПРИНАДЛЕЖАТЬ для некоторого а -вероятность появления в а операции ПРИНАДЛЕЖАТЬ для некоторого Наконец, пусть вероятность появления в операции ПРИНАДЛЕЖАТЬ для некоторого Для определения стоимости дерева двоичного поиска удобно добавить к нему фиктивных листьев, чтобы отразить элементы из Мы будем обозначать эти листья числами

На рис. 4.7 показано дерево двоичного поиска, изображенное на рис. 4.4, с добавленными фиктивными листьями. Например, лист с меткой 3 представляет те элементы а, для которых

Рис. 4.7. Дерево двоичного поиска с добавленными листьями.

Нам надо определить стоимость дерева двоичного поиска. Если элемент а равен метке некоторого узла то число узлов, посещенных во время выполнения операции ПРИНАДЛЕЖАТЬ , на единицу больше глубины узла Если то число узлов, посещенных при выполнении операции ПРИНАДЛЕЖАТЬ , равно глубине фиктивного листа Поэтому стоимость дерева двоичного поиска можно определить как

Теперь, если у нас есть дерево двоичного поиска обладающее наименьшей стоимостью, мы можем выполнить последовательность операций ПРИНАДЛЕЖАТЬ с наименьшим средним числом посещений узлов, просто применив для выполнения каждой операции ПРИНАДЛЕЖАТЬ алгоритм 4.1 на

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

Для обозначим через дерево наименьшей стоимости для подмножества Пусть стоимость дерева его корень. Вес дерева определяется как

Дерево состоит из корня левого поддерева (т. е. дерева наименьшей стоимости для и правого поддерева (т. е. дерева наименьшей стоимости для см. рис. 4.8. Если то нет левого поддерева, а при нет правого поддерева. Для удобства мы будем трактовать Та как пустое дерево. Вес дерева равен а его стоимость равна 0.

Рис. 4.8. Поддерево

В глубина каждого узла в левом и правом поддеревьях на единицу больше глубины того же узла в или Поэтому стоимость дерева можно выразить так:

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

Алгоритм 4.2. Построение оптимального дерева двоичного поиска

Вход. Множество вида где Известны также вероятности где вероятность выполнения операции ПРИНАДЛЕЖАТЬ для -вероятность выполнения операции ПРИНАДЛЕЖАТЬ для вероятность выполнения операции вероятность выполнения операции

Выход. Дерево двоичного поиска для обладающее наименьшей стоимостью.

Рис. 4.9. Алгоритм для нахождения корней оптимальных поддеревьев.

Рис. 4.10. Процедура для построения оптимального дерева двоичного поиска.

Метод.

1. Для вычисляются в порядке возрастания разности с помощью алгоритма динамического программирования, приведенного на рис. 4.9.

2. После вычисления всех Гц вызывается процедура для рекурсивного построения оптимального дерева для Процедура ПОСТРДЕРЕВА приведена на рис. 4.10.

Рис. 4.11. Значения

Рис. 4.12. Дерево наименьшей стоимости.

Пример 4.5. Рассмотрим четыре элемента На рис. 4.11 даны значения вычисленные алгоритмом, приведенным на рис. 4.9. Для удобства записи значения в этой таблице были умножены на 16.

Например, чтобы вычислить надо сравнить значения равные (после умножения на 16) соответственно 8, 9 и 11. Таким образом, в строке 8 рис. дает минимум, так что

Вычислив таблицу рис. 4.11, строим дерево вызывая На рис. 4.12 изображено полученное в результате дерево двоичного поиска. Его стоимость равна

Теорема 4.2. Алгоритм 4.2 строит оптимальное дерево двоичного поиска за время

Доказательство. Вычислив таблицу значений Гц, мы строим по ней оптимальное дерево за время вызывая процедуру ПОСТРДЕРЕВА. Эта процедура вызывается только раз, и каждый вызов занимает постоянное время.

Наиболее дорого стоит алгоритм динамического программирования (рис. 4.9). Строка 8 находит значение минимизирующее за время Остальные шаги цикла в строках 5—10 занимают постоянное время. Внешний цикл в строке 4 выполняется раз, внутренний — не более раз для каждой итерации внешнего цикла. Таким образом, суммарная сложность составляет

Что касается корректности алгоритма, то простой индукцией по можно показать, что правильно вычисляются в строках 9 и 10.

Чтобы показать, что оптимальное дерево правильно строится процедурой ПОСТРДЕРЕВА, заметим, что если корень поддерева для то его левый сын будет корнем оптимального дерева для где а правый будет корнем оптимального дерева для

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

В алгоритме 4.2 можно ограничить поиск в строке 8 рис. 4.9 областью между положениями корней деревьев и при этом гарантируется нахождение минимума. Тогда алгоритм 4.2 сможет находить оптимальное дерево за время