Если j = к - 1, доказывать нечего. В противном случае мы имеем ql > д для j < i < к-1, поскольку qj-i > qk-i +qk > Qj- Следовательно, согласно лемме W х < < • • < h-2, где /х - уровень (х) к U - уровень [Т] для j < i < к -1. Если же 1х = 1к-2, мы просто смещаем узел (х) вправо, замещая последовательность (х) [7] • • • \к-2\ последовательностью [7] ... А:-2 (х); это расположит листья в требуемом порядке.

В противном случае предположим, что Ig ~ 1х и /s+i > х- Сначала заменим © [7] • • Н на [J] j [i] ©; получим / < Is+i < < lk-2, где / = /х + 1 -

общий уровень узлов А:-11 и А; . И, наконец, заменим узлы

А:-1 [к] \s+l I ... .А:-2

узлами

\s+l I ... А,-2 А:-1 [Г]

при помощи циклической перестановки. В упр. 40 доказывается, что эти действия приведут к уменьшению цены (за исключением случая 1-2 - О- Однако поскольку согласно лемме Y цена не может уменьшаться, следовательно, 1к-2 = ! и лемма доказана.

Эти леммы показывают, что задача для п + 1 весов qo, qi, ..., q„ может быть сведена к задаче для п весов: сначала находим наименьший индекс к, такой, что Як-1 < Як+1, а затем - наибольшее j < к, для которого qji > qk-i + qk- После этого мы удаляем qk~i и gj. и вставляем сумму g-i +Чк непосредственно после qj-\. В специальном случае j = 0 или к = п, как вытекает из доказательства, мы должны действовать так, как если бы у нас были бесконечные веса qi и qn+i слева и справа. Доказательства также показывают, что любое оптимальное дерево 7, полученное на основе новых весов (ц, • • •, может быть переупорядочено в дерево Г, в

котором исходные веса {qo, - - ,qn) находятся в корректном порядке слева направо; более того, каждый вес появляется на одном и том же уровне как в дереве Т, так и в дереве Г.

В качестве примера на рис. 18 показано построение дерева для весов qk, представляющих относительные частоты появления букв и, А, В, ..., Z в английском тексте. Первые веса в этом списке равны

186, 64, 13, 22, 32, 103, ... ,

и выполняются неравенства 186 > 13, 64 > 22, 13 < 32; следовательно, мы должны заменить 13,22 значением 35. В новой последовательности

186, 64, 35, 32, 103, ...

следует заменить 35,32 значением 67 и сдвинуть 67 левее 64, получив при этом последовательность

186, 67, 64, 103, ....

Затем 67,64 превращаются в 131 и мы приступаем к исследованию весов, следующих за 103. После того как 27 исходных весов преврап;аются в один вес, 1 ООО, история комбинирования весов определяет бинарное дерево, которое и является решением поставленной задачи.

Рис. 19. Применение алгоритма Гарсия-Воча к данным о частотах появления букв; фаза 3.

Однако листья дерева на рис. 18 не находятся в правильном порядке, поскольку при каждом перемещении qk-i + Як влево дерево тщательно запутывается (см. упр. 41). Тем не менее доказательство леммы Z гарантирует существование дерева, листья которого расположены в правильном порядке и на тех же уровнях, что и в "запутанном" дереве. Такое "распутанное" дерево показано на рис. 19; это оптимальное дерево получено по алгоритму Гарсия-Воча.

Алгоритм G (Алгоритм Гарсия-Воча построения оптимальных бинарных деревьев). Дана последовательность неотрицательных весов wo, wi, ..., w„. Алгоритм позволяет построить бинарное дерево с п внутренними узлами, 12=0 kh которого минимальна (здесь представляет собой расстояние внешнего узла Щ от корня дерева). Алгоритм использует массив из 2п 4- 2 узлов с адресами Х*;, где О < к < 2п + 1. Каждый узел имеет четыре поля, а именно - WT, LLINK, RLINK и LEVEL. Листья построенного дерева - это узлы Хо ... Х„; внутренними узлами будут узлы Х„+1 .. .х2„. Корневым узлом дерева является узел х2„, а узел*х2„ используется в качестве временного. Алгорит.м, кроме того, использует рабочий массив указателей Ро, Pi, Pt, где < < П4-1.

G1. [Начало фазы 1.] Установите УТ(Х) -ir- Wk п LLINK(Xfc) 4- RLINK(Х) 4- Л для О < к < п. Установите также Ро x2„+i, WT(Po) 4- оо. Pi 4- Хо, < 4- 1, m 4- п. Затем выполните шаг G2 для j = 1, 2, ..., п и перейдите к шагу G3.

G2. [Поглощение Wj.] (В этот момент у нас выполнены базовые условия

WT(Pi i) > WT(Pi+i) для1<г<<. (31)

Другими словами, веса в рабочем массиве "попарно убывающие".) Выполните подпрограмму С, описанную ниже, несколько раз, пока не будет соблюдено условие WT(P( i) > Wj (если это условие соблюдено изначально, то выполнять подпрограмму С не нужно). Затем установите i 4- i 4-1 и Pt 4- Xj.

G3. [Завершение фазы 1.] Выполните подпрограмму С несколько раз (возможно, ни разу), пока t не станет равным 1.

G4. [Фаза2.] (Теперь Pi = Хгп - корень бинарного дерева и WT (Pi) = wo-\-----hw„.)

Установите lk равными расстояниям от узла Х до узла Pi для О < к < п (см. упр. 43; на рис. 18 приведен пример построенного дерева; номера уровней показаны справа от узлов).

G5. [Фаза 3.] Изменяя связи X„+i, ..., х2„, постройте новое бинарное дерево с теми же уровнями но с листьями, расположенными в симметричном порядке Xq, ..., Х„ (см. упр. 44; пример полученного дерева показан на рис. 19).

Подпрограмма С (Объединение). Эта подпрограмма является "сердцем" алгоритма Гарсия-Воча. Она объединяет два веса и смещает их на необходимое количество полей влево, обеспечивая выполнение условия "попарного убывания" (31).

С1. [Инициализация.] Установите к i- t.

С2. [Создание нового узла.] (В настоящий момент к > 2.) Установите m 4- m -f-1, LLINK(X„) 4- Р*, 1, RLINK(X„) 4- Рь WT(X„) 4- VT(Pk-i) + WT(Pfc).

C3. [Сдвиг последующих узлов влево.] Установите 14- < - 1, а затем P+i 4- Pj для k<j<t.