Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 23
Текст из файла (страница 23)
45). Фазы 2 и 3 требуют только 0(п) шагов. Кляйтман (К!еРлпап) и Сакс (Байя) (ЯАМ .!. А!Иеб. Пист. Месбог(я 2 (1981), 142-146) доказали, что оптимальиая взвешенная длина пути никогда не превышает значение оптимальной взвешенной длины пути, которая получается при перестановке в в "пилообразном" порядке: че < чя < !И « чт(чю! < Я(~~э'-~ < ' ' " < чз < !Ь (32) (Этот порядок представляет собой инверсию "органного" порядка, который обсуждался в упр. 6,1-18.) В последнем случае алгоритм Гарсия-Воча сводится к алгоритму Хаффмаиа на множестве весов дв + !Ь, дв + пз, ..., поскольку веса в рабочем массиве в действительности находятся в порядке иевозрастаиия (а ие только в "попарно убывающем" порядке, как в (ЗЦ).
Следовательно, мы можем улучшить верхиюю границу в теореме М, ие зная порядка весов. Оптимальное бинарное дерево иа рис. 19 имеет, помимо значения в теории поиска, большое прикладное значение в теории кодирования: используя 0 для левых ветвей дерева и 1 — для правых, мы получим следующие коды переменной длины. 00 1 1000 й 11001 А 0100 Л 1001000 8 1101 8 010100 К 1001001 Т 1110 С 010101 1. 100101 0 111100 0 01011 И 10011 Ч 111101 (33) 8 0110 И 1010 Ч 111110 Р 011100 0 1011 Х 11111100 8 011101 Р 110000 Т 11П1101 Н 01111 Ц 110001 2 1111111 Таким образом, сообщение типа 810НТ 0И может быть закодировано строкой 1100110000111010111111100010111010.
Декодирование слева направо выполняется просто и однозначно, несмотря иа то что коды имеют различную длину -- сама структура дерева показывает, когда заканчивается один символ и начинается другой. При данном методе кодирования сохраняется алфавитный порядок и используется в среднем около 4.2 бит для кодирования одного символа. Таким образом, этот код можно использовать для упаковки файлов данных без нарушения лексикографического порядка буквеииой информации, (Число 4,2 бит на символ минимально среди всех кодов, в которых используются бинарные деревья; оно может быть уменьшено до 4.1 бит на символ при отказе от алфавитного порядка.
Уменьшение до 4.1 бит на символ с сохранением алфавитного порядка возможно при кодировании не отдельных символов, а пар символов.) История и библиография. Рассмотренные в этом разделе методы поиска с использованием деревьев были открыты независимо несколькими исследователями в 50-е годы.
В неопубликованном меморандуме, датированном августом 1952 года, Л. И. Думи (А. 1. Пптеу) описал примитивный путь вставки в дерево. Рассмотрим барабан с 2" элементами, каждый из которых имеет бинарный адрес. Следуйте описанной ниже программе. 1. Прочтите первый элемент и поместите его по адресу 2" ~, т. е, в середину массива хранения. 2. Прочтите следующий элемент.
Сравните его с первым. 3. Если ои больше, поместите его по адресу 2" ' + 2" з. Если же он меньше, поместите его по адресу 2" в, и т. д. Другая ранняя форма вставки в дерево была введена Д. Дж. Вилером (П. 3, %Ьее!ег), который допускал многопутевые разветвления (подобные тем, которые будут рассмотрены в разделе 6.2.4); еще один метод вставки в бинарное дерево был предложен К. М. Бернерсом-Ли (С. М. Вегпегв-Бее) (см. Сотр.
Я. 2 (1959), 5). Первые опубликованные описания вставки в дерево принадлежат П. Ф. Виндли (Р. Р. %'щсИеу) (Сотр. д. 3 (1960), 84-88), Э. Д. Буту (А. О. ВоосЬ) и Э. Дж. Т, Колину (А. д. Т. Сойп) (1п(огтаг)оп апд Сопсго) 3 (1960), 327-334), а также Томасу Н. Хиббарду (ТЬотав К. Н1ЬЬагд) (,УАСМ 9 (1962), 13-28). По-видимому, каждый из авторов пришел к своему методу независимо от других, и в каждой статье среднее количество сравнений (6) вывалится по-своему. Авторы также сосредоточивали свое внимание на разных аспектах алгоритма: Виндли подробно разбирал сортировку путем вставки в дерево, Бут и Колин исследовали влияние предварительного построения идеально сбалансированного дерева из первых 2" — 1 элементов (см. упр.
4), Хиббард предложил идею удаления и показал связь между анализом вставки в дерево и анализом быстрой сортировки. Идеи оптнмольнмк бинарных деревьев поиска первоначально были развиты для частного случая р~ = ... — — р„= 0 в контексте бинарного кодирования алфавита, подобного (ЗЗ). В очень интересной статье Э. Н, Гильберта (Е. Х.
СВЬегс) и Э. Ф. Мура (Е. Р. Мооге) (Ве)( ЯувВет Тесй. Х 38 (1959), 933-968] обсуждается эта задача и ее связь с другими задачами кодирования. Гильберт и Мур доказали теорему М для специальною случая Р = 0 и заметили, что оптимальное дерево может быть построено за 0(пз) пвагов с помощью метода наподобие алгоритма К, но без использования соотношения монотонности (17). К. К). Айверсон (К. Е. 1тегвоп) (А Ргойгатпипй Ьапйпайе (%11еу, 1962), 142-144] независимо рассмотрел другой случай, когда все дь равны нулю. Он предположил, что оптимальное дерево можно получить, выравнивая вероятности левого и правого поддеревьев; к сожалению,мы видели, что зта идея ие срабатывает... Д. Э.
Кнут (О. Е. КппсЬ) [Асса ЕпГогтав)са 1 (1971), 14-25, 270] погледовательно рассмотрел случаи произвольных весов рь и йь н доказал, что алгоритм может быть сведен к О(пз) шагам; он также представил пример использования этих методов в компиляторе, где ключами дерева являлись '"зарезервированные слова" АЬПОЬ-подобного языка. Т. Ч. Ху (Т. С.
Нп) несколько лет изучал собственный алгоритм для случая р: = 0; из-за сложности задачи было трудно найти строгое доказательство корректности алгоритма, однако в сотрудничестве с А. К. Таккером (А. С, Тпсйег) такое доказательство, в конце концов, было найдено [ЯАМ Х Арр!1ег( МаСЬ. 21 (1971), 514-532[. Упрощения, приведшие к разработке алгоритма С, были найдены несколькими годами позже А. М. Гарсии (А, М. Саггба) и М. Л. Вочем (М. 1,. %асйэ) [ЯСОМР 6 (1977), 622 — 642]; их доюзательство, впрочем, было слишком сложным и запутанным.
Леммы %, Х, Ъ и Х, описанные выше, появились благодаря Дж. Х. Кингстону (Х Н. К1пбэсоп) [Х А(8огДЬтз 9 (1988), 129-136[. (См. также статью Ху (Нп), Кляйтмана (К1е)сгпап) и Тамаки (Тягла)п) [ЯАМ Х Аррйед МагЬ. 37 (1979), 246-256], в которой дано элементарное доказательство алгоритма Ху-Таккера н некоторые обобщения для других ценовых функций.) Теорема В доказана Паулем Дж. Байером (Рап1 3. Вауег) [М1Т/ЬСБ/ТМ-69 (Маза. 1пэп о( ТесЬ., 1975)], который также доказал теорему М (в ослабленной формулировке).
Строгое доказательство указанной теоремы найдено К. Мельхорном (К. МеЫЬогп) [ЯСОМР 6 (1977), 235--239]. УПРАЖНЕНИЯ 1. [10] Алгоритм Т сформулирован только для иепустык деревьев. Какие изменения дачжны быть внесены в алгоритм для корректной работы и в случае пустых деревьев? 2. [30] Измените алгоритм Т таким образом, чтобы он работал с ораванрошишэсми деревьями (см, раздел 2.3,1; такие деревья упрощают выполнение симметричного обхода дерева). 3.
[30] В разделе 6.1 мы видели, что, внеся небольшие изменения в алгоритм последовательного поиска 6.13, можно сделать его более быстрым (алгоритм 6.112). Можно ли воспользоваться похожим приемом для ускоренна работы алгоритма Т? 4. [М34] (Э. Д. Бут (А. П. Воогб) и Э. Дж. Т. Колин (А, Х Т. Сойв).) Даны Ф ключей в случайном порядке. Предположим, что мы используем первые 2" — 1 из них для построения нлеальпо сбалансированного дерева и размещаем 2" ключей на уровне 1 для всех 0 ( 1 < и; затем для вставки оставшихся ключей мы используем алгоритм Т. Чему равно среднее число сравнений в случае успешного поиска? (Указание.
Модифишэруйте формулу (2).) 6. [ИЗБ] Имеетсв 11! = 39916 800 различных способов упорядочения названий САР31003Н. 10013103 и т. д, для их вставки в бинарное дерево поиска. а) В результате скольких перестановок получится дерево, изображенное нв рис. 10? о) В результате скольких перестановок получится емроясдсннос дерево, в каждом узле 11133 или 3113к которого равны Л? 6. [М30] Пусть Р„ь -- количество перестановок а~ аэ...а множества (1,2,...,и). таких, что при использовании алгоритма Т лля вставки амаг...а„в изначально пустое дерево для вставки элемента а„потребуется ровно 1 сравнений. (В этой задаче мы пренебрегаем сравнениями, выполняемыми при вставке аь,а„ь В принятых в тексте обозначениях С'„, = (2, АР„э)7лй так как это среднее количество сравнений, которые выполняются в случае неудачного поиска в дереве, содержащем и — 1 элемент.) а) Докажите, что Ры+мь — — 2Р„ы м+ (и — 1)Р„ы (Указание.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
