С4. [Сдвиг предыдущих узлов вправо.] Установите j 4- /г - 2; затем, пока УТ(Р) <

WT(Xm), присваивайте P+i 4- ?j и j 4- j - 1. С5. [Вставка нового узла.] Присвойте P i 4- 1т-

Сб. [Все?] Если j > О и WT(Pj i) < WKXm), присвойте к <- j и вернитесь к шагу С2. I

Как указывалось выше, подпрограмме С может потребоваться П(п) шагов для создания и вставки нового узла, поскольку она использует последовательное хранение в памяти вместо связанных списков. Таким образом, общее время работы алгоритма G может составлять П(п). Однако более тщательная разработка применяемых структур данных может привести к использованию не более (9(nlogn) шагов (см. упр. 45). Фазы 2 и 3 требуют только 0{п) шагов.

Кляйтман (Kleitman) и Сакс (Saks) {SIAM J. Algeb. Discr. Methods 2 (1981), 142-146) доказали, что оптимальная взвешенная длина пути никогда не превышает значение оптимальной взвешенной длины пути, которая получается при перестановке ? в "пилообразном" порядке:

?0 < ?2 < ?4 < • • • < ?2Ln/2j < ?2Гп/21-1 < " < ?3 < ?1 • (32)

(Этот порядок представляет собой инверсию "органного" порядка, который обсуждался в упр. 6.1-18.) В последнем случае алгоритм Гарсия-Воча сводится к алгоритму Хаффмана на множестве весов ?о + ?i, ?2 + ?з, • • • , поскольку веса в рабочем массиве в действительности находятся в порядке невозрастания (а не только в "попарно убывающем" порядке, как в (31)). Следовательно, мы можем улучшить верхнюю границу в теореме М, не зная порядка весов.

Оптимальное бинарное дерево на рис. 19 и.меет, помимо значения в теории поиска, большое прикладное значение в теории кодирования: используя О для левых ветвей дерева и 1 - для правых, мы получим следующие коды переменной длины.

U 00 I 1000 R 11001

А 0100 J 1001000 S 1101

В 010100 К 1001001 Т 1110

С 010101 L 100101 и 111100

D 01011 М 10011 V 111101 (33)

Е ОНО N 1010 W 111110

F 011100 О 1011 X 11111100

G 011101 Р 110000 Y 11111101

Н 01111 Q 110001 Z 1111111 Таким образом, сообщение типа RIGHT ON может быть закодировано строкой

1100110000111010111111100010111010.

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

(Число 4.2 бит на символ минимально среди всех кодов, в которых используются бинарные деревья; оно может быть уменьшено до 4.1 бит на символ при отказе от алфавитного порядка. Уменьшение до 4.1 бит на символ с сохранением алфавитного порядка возможно при кодировании не отдельных символов, а пар символов.)

История и библиография. Рассмотренные в этом разделе методы поиска с использованием деревьев были открыты независимо несколькими исследователями в 50-е годы. В неопубликованном меморандуме, датированном августом 1952 года, А. И. Думи (А. I. Dumey) описал примитивный путь вставки в дерево.

Рассмотрим барабан с 2" элементами, каждый из которых имеет бинарный адрес.

Следуйте описанной ниже программе.

1. Прочтите первый элемент и поместите его по адресу 2"", т. е. в середину массива хранения.

2. Прочтите следующий элемент. Сравните его с первым.

3. Если он больше, поместите его по адресу 2"" + 2"". Если же он меньше, поместите его по адресу 2"", и т. д.

Другая ранняя форма вставки в дерево была введена Д. Дж. Вилером (D. J. Wheeler), который допускал многопутевые разветвления (подобные тем, которые будут рассмотрены в разделе 6.2.4); еще один метод вставки в бинарное дерево был предложен К. М. Бернерсом-Ли (С. М. Berners-Lee) (см. Сотр. J. 2 (1959), 5).

Первые опубликованные описания вставки в дерево принадлежат П. Ф. Виндли (Р. F. Windley) {Сотр. 3. 3 (1960), 84-88), Э. Д. Буту (А. D. Booth) и Э. Дж. Т. Ко-лину (А. J. Т. Colin) (Information and Controi 3 (1960), 327-334), a также Томасу Н. Хиббарду (Thomas N. Hibbard) {JACM 9 (1962), 13-28). По-видимому, каждый из авторов пришел к своему методу независимо от других, и в каждой статье среднее количество сравнений (6) выводится по-своему. Авторы также сосредоточивали свое внимание на разных аспектах алгоритма: Виндли подробно разбирал сортировку путем вставки в дерево. Бут и Колин исследовали влияние предварительного построения идеально сбалансированного дерева из первых 2" - 1 элементов (см. упр. 4), Хиббард предложил идею удаления и показал связь между анализом вставки в дерево и анализом быстрой сортировки.

Идеи оптимальных бинарных деревьев поиска первоначально были развиты для частного случая pi = • • = р„ = О в контексте бинарного кодирования алфавита, подобного (33). В очень интересной статье Э. Н. Гильберта (Е. N. Gilbert) и Э. Ф. Мура (Е. F. Moore) [Bell System Tech. J. 38 (1959), 933-968] обсуждается эта задача и ее связь с другими задачами кодирования. Гильберт и Мур доказали теорему М для специального случая Р = О и заметили, что оптимальное дерево может быть построено за 0{п) шагов с помощью метода наподобие алгоритма К, но без использования соотношения монотонности (17). К. Ю. Айверсон (К. Е. Iverson) [А Programming Language (Wiley, 1962), 142-144] независимо рассмотрел другой случай, когда все qk равны нулю. Он предположил, что оптимальное дерево можно получить, выравнивая вероятности левого и правого поддеревьев; к сожалению, мы видели, что эта идея не срабатьшает... Д. Э. Кнут (D. Е. Knuth) [Acta Informatica 1 (1971), 14-25, 270] последовательно рассмотрел случаи произвольных весов рк

и 9/0 и доказал, что алгоритм может быть сведен к 0{п) шагам; он также представил пример использования этих методов в компиляторе, где ключами дерева являлись "зарезервированные слова" ALGOL-подобного языка. Т. Ч. Ху (Т. С. Ни) несколько лет изучал собственный алгоритм для случая pj = 0; из-за сложности задачи было трудно найти строгое доказательство корректности алгоритма, однако в сотрудничестве с А. К. Таккером (А. С. Tucker) такое доказательство, в конце концов, было найдено [SIAM J. Applied Math. 21 (1971), 514-532]. Упрощения, приведшие к разработке алгоритма G, были найдены несколькими годами позже А. М. Гарсия (А. М. Garsia) и М. Л. Вочем (М. L. Wachs) [SICOMP 6 (1977), 622-642]; их доказательство, впрочем, было слишком сложным и запутанным. Леммы W, X, Y и Z, описанные выше, появились благодаря Дж. X. Кингстону (J. Н. Kingston) [J. Algorithm.s 9 (1988), 129-136]. (См. также статью Ху (Ни), Кляйтмана (Kleitman) и Тамаки (Tamaki) [SIAM J. Applied Math. 37 (1979), 246-256], в которой дано элементарное доказательство алгоритма Ху-Таккера и некоторые обобщения для других ценовых функций.)

Теорема В доказана Паулем Дж. Байером (Paul J. Bayer) [MIT/LCS/TM-69 (Mass. Inst, of Tech., 1975)], который также доказал теорему М (в ослабленной формулировке). Строгое доказательство указанной теоремы найдено К. Мельхорном (К. Mehlhorn) [SICOMP 6 (1977), 235-239].

УПРАЖНЕНИЯ

1. [15] Алгоритм Т сформулирован только для непустых деревьев. Какие изменения должны быть внесены в алгоритм для корректной работы и в случае пустых деревьев?

2. [20] Измените алгоритм Т таким образом, чтобы он работал с правопрошитыми деревьями (см. раздел 2.3.1; такие деревья упрощают выполнение симметричного обхода дерева).

► 3. [20] В разделе 6.1 мы видели, что, внеся небольшие изменения в алгоритм последовательного поиска 6.IS, можно сделать его более быстрым (алгоритм 6.1Q). Можно ли воспользоваться похожим приемом для ускорения работы алгоритма Т?

4. [М24] (Э. Д. Бут (А. D. Booth) и Э. Дж. Т. Колин (А. J. Т. Colin).) Даны N ключей в случайном порядке. Предположим, что мы используем первые 2" -1 из них для построения идеально сбалансированного дерева и размещаем 2* ключей на уровне к для всех О < А; < п; затем для вставки оставшихся ключей мы используем алгоритм Т. Чему равно среднее число сравнений в случае успешного поиска? {Указание. Модифицируйте формулу (2).)

► 5. [М25] Имеется 11! = 39916 800 различных способов упорядочения названий CAPRICORN, AQUARIUS и т. д. для их вставки в бинарное дерево поиска.

a) В результате скольких перестановок получится дерево, изображенное на рис. 10?

b) В результате скольких перестановок получится вырожденное дерево, в каждом узле LLINK или RLINK которого равны Л?

6. [М26] Пусть Рпк - количество перестановок oi ог ... о„ множества {1,2,..., п}, таких, что при использовании алгоритма Т для вставки ai,02,... ,о„ в изначально пустое дерево для вставки элемента о„ потребуется ровно к сравнений. (В этой задаче мы пренебрегаем сравнениями, выполняемыми при вставке oi,...,o„ i. В принятых в тексте обозначениях C i = (HitPnt)/"!, так как это среднее количество сравнений, которые выполняются в случае неудачного поиска в дереве, содержащем п - 1 элемент.)

а) Докажите, что P(„+i)k = 1Рп(к-\) + (п - 1)Рпк- {Указание. Посмотрите, не окажется ли в дереве o„+i ниже, чем а„.)