В качестве примера рассмотрим множество ключей 1 о с вероятностями обращения pi = 1/7, /52 = 2/7 и Эти три ключа можно расположить в виде деревьев пои пятью различными способами (см. рис. 4.36).

Взвещенные длины пути этих деревьев вычисляются в ответствии с (4.66):

р( ) = 1(1.3-{-2.2 + 4. 1) = -, ==f (1 .2 + 2.3 + 4. 1) = -, Pf = y(l.2 + 2.1+4-2) = -,

-\-,рМЬ= (4 1 4

1(1.1+2

Итак, в этом примере оптимальным оказывается не идеально сбалансированное дерево, а вырожденное.

Пример сканера в трансляторе сразу наводит на мысль, что эту проблему следует рассматривать при несколько более общем условии: слова, встречающиеся в исходном тексте, не всегда являются зарезервированными словами; в действительности это скорее исключение, чем правило. Выяснение того, что данное слово не является ключом в дереве поиска, можно рассматривать как обращение к гипотетическому специальному узлу , вставленному между меньшим и большим ключами (см. рис. 4.19) и имеющему соответствующую длину внешнего пути. Если известна также вероятность qi того, что аргумент поиска х лежит между двумя ключами ki и ki+u г это может существенно повлиять на структуру оптимального дерева поиска. Поэтому мы обобщим задачу, учитывая и неудачные поиски.

Общая взвешенная длина имеет теперь следующий вид:

п т

где

п т

hi - уровень внутреннего узла i, h - уровень внешнего уз /. Среднюю взвешенную длину пути можно назвать цено дерева поиска, так как она является мерой ожидаемого личества затрат на поиск. Дерево поиска, структура которог ],ает минимальную цену для всех деревьев с заданным

gcTBOM ключей ki и вероятностями pi и д/ обращений, назы-ется оптимальным деревом.

Для нахождения оптимального дерева не обязательно,

тобы сумма всех рад равнялась I. На самом деле значения роятностей обычно находятся с помощью экспериментов, * которых подсчитываются обращения к узлам. Вместо вероятностей pi и gi мы в дальнейщем будем использовать пока-ззтели частоты обращений, которые обозначим как

СИ = число поисков с аргументом х, равным ki,

bj = число поисков, когда аргумент х лежит между kf и

kj+U

j]o соглащению bo есть число поисков, когда х меньше ku £ Ьп - частота поисков, когда х больше kn (см. рис. 4.37),

Рис. 4.37. Дерево поиска с указанием частоты обращений.

В дальнейшем мы будем через Р обозначать общую взвешен-йую длину пути вместо средней длины пути:

(4.68)

Итак, благодаря использованию экспериментально измеренных Частот мы не только избавились от необходимости вычислять вероятность, но и получили возмох. ость иметь дело Только с целыми числами при нашем поиске оптимального Дерева.

Если учесть, что число возможных конфигураций из п узлов растет экспоненциально вместе с п, задача нахождения тимума при больших п кажется совершенно безнадежной. Днако оптимальные деревья имеют одно важное свойство, которое помогает их находить: все их поддеревья тоже яв-Пяются оптимальными. Например, если дерево на рис. 4.37 Оптимально для данных а и 6, то поддерево с ключами

re п

H=Z i+ZV (4.70)

Мы называем W весом дерева. Тогда его средняя длина пути будет P/W.

Из этих рассуждений видно, что необходимо обозначить веса и длины пути поддеревьев, состоящих из какого-то числа ключей. Пусть хюц обозначает вес, а р,/ -длину пути оптимального поддерева Тц, состоящего из узлов с ключами i+i, й(+2, ..., kj. Эти величины определяются рекуррентными соотношениями (4.71) и (4.72):

wii = bi (0<i<n),

Wil = Wi, i-i+-a,-\-bj (0<i<;<n),

Pu = mi (0<i<n),

Pii=Wii+ min (pi,k-\+Pki) {0i<jn).

Последнее равенство непосредственно следует из (4.69) и определения оптимальности.

Поскольку существует приблизительно (1/2)п2 значений рц и так как (4.72) требует выбора среди 0<; / - in значений, поиск минимума займет приблизительно (1/6)п^ операций. Кнут показал, что при помощи следующих рассуждений можно избавиться от множителя п и таким образоч сохранить практическую ценность этого алгоритма.

Пусть г,/ - значение k, при котором достигается минимум* в (4.72). Можно ограничить поиск г;/ намного меньшим интервалом, т. е. уменьшить число оценочных шагов / - i-основано на следующем наблюдении: если мы нашли кореВ^ rij оптимального поддерева Тц, то ни добавление к дере* справа какого-либо узла, ни удаление его самого левого уз-

и ki, как известно, также оптимально. Эта особенность пп полагает алгоритм, который систематически находит все бб шие и большие деревья, начиная с отдельных узлов как на* меньших возможных поддеревьев. Таким образом, дере* растет от листьев к корню , что является, поскольку\ привыкли рисовать деревья сверху вниз, направлением сни вверх [4.6]. -

Основой нашего алгоритма служит уравнение (4б9\ Пусть Р - взвешенная длина пути дерева, а Pt и Pr -взве щенные длины левого и правого поддеревьев его корня. Понятно, что Р -это сумма Рь, Pr и числа случаев, когда поис проходит по единственному пути к корню, что является просто общим числом W случаев поиска.

P = Pl+W + Pr, (4.69)