Нетрудно видеть, что описанное выше построение обобщается для любого t > 2. В полном t-арном дереве с внутренними узлами {1,2,... ,п} родителем узла к будет узел

[{k + t-2)/t\ = r(fc-i)Al,

а детьми узла fc - узлы

t(fc-l) + 2, t(fc-l)+3, tk+l.

Это дерево имеет минимальную внутреннюю длину пути среди всех t-арных деревьев с п внутренними узлами. В упр. 8 приводится доказательство того, что его внутренняя длина пути равна

9= [log,((t-l)R + l)J.

t-lJ {t-iy

Эти результаты имеют еще одно важное обобщение, если рассмотреть их с несколько другой точки зрения. Пусть даны т действительных чисел wi, W2,

Wm- Задача заключается в поиске расширенного бинарного дерева с т внешними узлами и такого соответствия между числами tui,...,Wm и узлами этого дерева, при котором сумма Xwj/j является минимальной, где Ij-длина пути от корня, а сумма берется по всем внешним узлам. Например, если заданы числа 2, 3, 4, И, можно построить три таких расширенных бинарных дерева.

Здесь "взвешенными" длинами пути Yljh будут 34, 53 и 40 соответственно. (Как видно из данного примера, с помощью полностью сбалансированного дерева нельзя получить минимальное значение взвешенной длины пути для весов 2, 3, 4 и И, хотя, как показано выше, это возможно в особом случае, с весами wi = W2 = = Wm = 1) В разных компьютерных алгоритмах понятие взвешенной длины пути может интерпретироваться по-разном\. Например, с его помощью можно выполнять слияние упорядоченных последовательностей с длинами wi,W2,... ,Wm (см. главу 5). Одно из наиболее непосредственных приложений этого понятия заключается в том, что бинарное дерево рассматривается как некая программа поиска. Поиск начинается в корне с проверкой некоторого условия, затем в зависимости от его результата происходит переход к одной из двух ветвей, где снова проверяется некоторое условие, и т. д. Например, если необходимо выполнить проверку истинности четырех различных условий, а вероятности их истинности равны соответственно , и 55, то дерево, которое минимизирует взвешенную длину пути, и будет представлять собой оптимальную программу поиска (optimal search procedure). [Эти вероятности равны указанным в (8) весам, если умножить их на нормировочный множитель 20.]

Следующий элегантный алгоритм поиска дерева с минимальной взвешенной длиной пути был предложен Д. Хаффмэном [D. Huffman, Proc. IRE 40 (1952), 1098-1101]. Сначала нужно найти два наименьших веса гу, например гУ1 ишг. После этого задача решается для т - 1 весов wi + W2, ws, ..., Wm, причем в ее решении узел

WI+W2

заменяется узлом

(10)

В качестве примера использования метода Хаффмэна найдем оптимальное дерево для весов 2, 3, 5, 7, И, 13, 17, 19, 23, 29, 31, 37, 41. Для этого сначала объединим вершины 2 + 3 и найдем решение для 5,5, 7,..., 41, затем объединим 5 Ч- 5 и т. д. В общем, последовательность действий будет выглядеть так.

2 3

Следовательно, такому построению Хаффмэна будет соответствовать дерево

(Числа в круглых узлах показывают связь между дерево.м и этапами приведенного выше вычисления; см. также упр. 9.)

Нетрудно доказать с цомощью метода индукции по тп, что этот способ действительно позволяет минимизировать взвешенную длину пути. Допустим, что даны веса wi < < гУз < • < Wm, где m > 2, и дерево, которое минимизирует взвешенную длину пути. (Такое дерево должно существовать, так как существует то.яько конечное множество бинарных деревьев с тп концевыми узлами.) Пусть V - внутренний узел, который находится на максимальном расстоянии от корня. Если веса wi и vj-2 еще не приписаны детям узла V, то ими можно заменить величины, которые уже там находятся, не увеличивая взвешенную длину пути. Таким образом, существует дерево, которое минимизирует взвешенную длину пути и содержит поддерево (10). Теперь можно легко доказать, что взвешенная .длина пути подобного дерева будет минимальной тогда и только тогда, когда это дерево с поддеревом (10), замененным узлом (9), обладает минимальной длиной пути для весов Wi + W2, W3,...,w,n. (см. упр. 9).

Всякий раз, когда в построении объединяются два веса, они по крайней мере не меньше весов, которые объединялись на предыдущем этапе, если все - неотрицательные числа. Это значит, что существует прекрасный способ поиска дерева Хаффмэна при условии, что веса расположены в порядке неубывания. Тогда достаточно создать две очереди, одна из которых будет содержать исходные веса, а другая - объединенные веса. На каждом этапе этой процедуры наименьший неиспользованный вес будет находиться в начале одной из очередей, поэтому его не придется искать. В упр. 13 показано, как реализовать эту процедуру при работе с отрицательными весами.

Вообще, существует много деревьев, которые минимизируют YtVjlj. Если в описанном выше алгоритме при очередном объединении весов всегда используется исходный, а не комбинированный вес, то полученное с помощью этого алгоритма дерево будет иметь наименьшее значение величин max/j и Ylh среди всех деревьев, которые мини.мизируют Yuijlj. Если веса принимают положительные значения, это дерево также минимизирует YWjfilj) для любой выпуклой функции / по всем таки.м деревья.м. [См. Е. S. Schwartz, Information and Control 7 (1964), 37-44; G. Markowsky, Acta Informatica 16 (1981), 363-370.]

Метод Хаффмэна можно обобщить для t-арных, а также для бинарных деревьев (см. упр. 10). Еще одно важное обобщение метода Хаффмэна рассматривается в разделе 6.2.2. Обсуждение длины пути будет продолжено в разделах 5.3.1, 5.4.9 и 6.3.

УПРАЖНЕНИЯ

1. [12] Существуют ли какие-либо другие бинарные деревья с 12 внутренними узлами и минимальной длиной пути, кроме полного бинарного дерева (5)?

2. [17] Нарисуйте схему расширенного бинарного дерева с концевыми узлами, которые содержат веса 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, имеющие минимальную взвешенную длину пути.

► 3. [М24] Расширенное бинарное дерево с т внешними узлами определяет множество длин пути h, h, - ,1т от корня к соответствующим внешним узлам. И наоборот, если дано множество чисел h,l2, всегда ли можно построить расширенное бинарное дерево, в котором эти номера являются длинами пути, расположенными в некотором порядке? Покажите, что это возможно тогда и только тогда, когда X)JLi =1-