(1,0,0)

•(0,0,1)

Рис. 14. На этой диаграмме показано, какое из пяти деревьев (13) является наилучшим в случае относительных частот (р, д, г) ключей {Ki,K2, Кз). Тот факт, что р + q + r = 1, делает диаграмму двумерной несмотря на наличие трех координат.

(Пусть qo представляет собой вероятность того, что аргумент поиска меньше, чем Ki, а qn - вероятность того, что аргумент поиска больше, чем Кп.) Таким образом, Pi + Р2 + • + Рп + 9о + 91 + • + 9п = 1 и мы хотим найти бинарное дерево, минимизирующее ожидаемое количество сравнений при поиске, а именно

(уровень(0) + l)+Y,qk уровень([1]), (14)

j=l к=0

где 0 -J-й внутренний узел при симметричном обходе, а [к] - (А;--1)-й внешний узел; корень дерева находится на нулевом уровне. Так, ожидаемое количество сравнений для бинарного дерева

(15)

равно 2go + 2pi-l-3gi-b3p2 +32+Рз+9з- Назовем это значение гиеной дерева, а дерево с минимальной ценой - оптимальным. При таком определении требование, чтобы сумма всех р и g была равна 1, излишне - мы можем искать дерево с минимальной ценой с любой данной последовательностью весов (pi,..., р„; до, • • •, 9п)•

В разделе 2.3.4.5 мы изучали процедуру Хаффмана (Huffman) для построения деревьев с минимальной взвешенной длиной пути, однако этот метод требовал, чтобы все р были нулевыми, и, кроме того, в построенном этим методом дереве внешние узлы с весами {qo, - ,qn) обычно не располагались в правильном порядке с точки зрения симметричного обхода. Следовательно, нам надо поискать другие подходы к решению этой задачи.

Нас спасет то, что все поддеревья оптимального дерева оптимальны. Например, если (15) представляет собой оптимальное дерево для весов (р1,Р2,Рз; 9о,9i,9з), то его левое поддерево должно быть оптимально для (pi,P2i 9oi9ii92); любое улучшение поддерева должно приводить к улучшению дерева в целом.

Данный принцип предлагает вычислительную процедуру, которая систематично ишет все большие и большие оптимальные поддеревья. Мы использовали эту же идею в разделе 5.4.9 для построения схем оптимального слияния; обший подход, известный как "динамическое программирование" будет рассмотрен в разделе 7.7*.

Пусть с(г, j) - цена оптимального поддерева с весами (pi+i,pj\ qi, - ..,qj) и пусть w{i,j) = pi+i ++ Pj + qi + + qj - сумма этих весов (очевидно, что c{i,j) и w{i,j) определены для О < г < j < п). Поскольку минимально возможная цена дерева с корнем (к) равна w{i,j) + ф, к-1) + c{k,j), получим

с(г,г) =0,

c{i, j) = w{i,j) + min {c{i, к-1) + c{k,j)) при г < j. (16)

Через R{i,j) при i < j обозначим множество всех к, для которых достигается минимум в (16); это множество определяет корни оптимальных поддеревьев.

С помощью уравнений (16) можно вычислить c{i,j) для j -i = 1,2,... ,п; имеется примерно п таких значений, а операция минимизации выполняется примерно для значений к. Это означает, что мы в состоянии определить оптимальное дерево за 0{п) единиц времени с использованием 0{п) ячеек памяти.

При оценке времени работы свойство монотонности позволяет уменьшить степень при п. Пусть r{i,j) означает элемент множества R{i,j); нет необходимости в вычислении всего множества i?(«,j) - достаточно одного его представителя. Найдя г(г, j-1) и r{i + l,j) и используя результат упр. 27, мы всегда можем полагать, что

r{i,j-l)<r{i,j)<r{i + l,j) (17)

при неотрицательных весах. Это ограничивает поиск минимума всего лишь r{i+l, j) - r{i,j-l) + 1 проверяемыми в (16) значениями к вместо j - i. Общий объем работы при j - i = d оценивается как

{r{i + l,j) - r{i, j-1) + 1) = r{n-d-+l, n) - r(0, d-1) +n-d+l<2n,

d<j<n i=j-d

так что общее время работы уменьшается до (9(п).

Детально эта процедура рассматривается в описании алгоритма К.

Алгоритм К {Поиск оптимальных бинарных деревьев поиска). Даны 2п-ь1 неотрицательных веса (pi,... ,рп; qo, - - - ,qn)- Алгоритм строит бинарные деревья t{i,j), имеющие минимальную цену (в определенном ранее смысле) для весов {pi+i, - - - ,Pj, qi,... ,qj). Вычисляются три массива, а именно

с[г,Я, 0<i<j<n, цена t{i,j); r[i,j], О <г< j <п, корень t{i,j);

О < г < j < n, общий вес i(j,j).

* Имеется в виду раздел из планируемого автором тома 4. - Прим. перев.

Результаты работы алгоритма определяются массивом г: при i = j t(i,j) пуст; в противном случае левое поддерево - t{i, r[i,j]-l), а правое поддерево - t{r[i,j], j).

KI. [Инициализация.] Для О < г < п установить c[i,i] <- О, w[i,i] <- и iti[j,j] <- w[i, J -l]+Pj+gj при j = i + ..., n. Затем для I < j <n установить c[j-1, j] f-w[j - l,j] и r[j - l,j] <- j. (Эти действия определяют все оптимальные деревья из одного узла.)

К2. [Цикл по d.] Выполнить шаг КЗ для d = 2,3,... ,п, затем остановить работу алгоритма.

КЗ. [Цикл по j.] (К этому моменту уже определены оптимальные деревья с менее чем d узлами. На данном шаге определяются все оптимальные деревья с d узлами). Выполнить шаг К4 для j = d, d + 1, ..., п.

К4. [Поиск c[i,j], r[i,j].] Установить i j - d, затем -

c[i,j] <- w[i, j] + mmr[ij-i]<k<r[i+i,j]{c[i, к-1] + c[k, j])

и присвоить r[i,j] значение к, для которого достигается минимум. (В упр. 22 доказывается, что r[i,j - l] < r[i+l,j].)

Рис. 15. Оптимальное бинарное дерево поиска для указателя KWIC.

В качестве примера алгоритма К рассмотрим рис. 15, основанный на приложении индексирования "key-word-in-context" (ключевое слово в контексте - KWIC). Заглавия всех статей в первых десяти томах Journal of the АСМ были рассортированы таким образом, чтобы каждому слову каждого заголовка соответствовала одна строка. Впрочем, некоторые слова наподобие THE и EQUATION были признаны неинформативными и не вошли в указатель. Эти специальные слова и частота их появления обозначены внутренними узлами на рис. 15. Обратите внимание на то, что заглавие наподобие "On the solution of an equation for a certain new problem" ("O решении уравнения для некоторой новой задачи") оказывается настолько неинформативным, что вовсе не попадает в указатель! Идея указателя KWIC описана