AOP_Tom3 (1021738), страница 124
Текст из файла (страница 124)
В новой последовательности 186, 64, 35, 32, 103, следует заменить 35,32 значением 67 и сдвинуть 67 левее 64, получин при этом последовательность 186, 67, 64, 103, .... Затем 67, 64 превращаются в 131 и мы приступаем к исследованию весов, следук2щих за 103. После того как 27 исходных весов превращаются в один вес, 1000, история комбинирования весов определяет бинарное дерево, которое и является решением поставленной задачи. к Д .Я ~Ф Ф х о И Й й~ о Ю Ф о а Ф Р Д 6 Ф Р И Однако листья дерева на рис.
18 не находятся в правильном порядке, поскольку прн каждом перемещении уь г + аг влево дерево тщательно запутывается (см. упр. 41). Тем не менее доказательство леммы Х гарантирует существование дерева, листья которого расположены в правильном порядке и на тех же уровнях, что и в "запутанном" дереве. Такое "распуганное" дерево показано на рис. 19; это оптимальное дерево получено по алгоритму Гарсия-Воча. Алгоритм С (Алгорипьм Гарсил-Вача построенил оптаимальямх бинарных деревьев). Дана последовательность неотрицательных весов шо, шг, ..., ш„.
Алгоритм позволяет построить бинарное дерево с п внутренними узлами, 2 ,'„" о шг1г которого минимальна (здесь 1ь представляет собой расстояние внешнего узла [а] от корня дерева). Алгоритм использует массив из 2п + 2 узлов с адресами Хь, где О < к < 2п+ 1. Каждый узел имеет четыре поля, а именно — МТ, Е(.1МК, 81.1МК и (.КУКЕ. Листья построенного дерева — это узлы Хо... Х„; внутреннимн узлами будут узлы Х„т,...
Ха„. Корневым узлом дерева является узел Ха„, а узел'Ха„используется в качестве временного. Алгоритм, кроме того, использует рабочий массив указателей Ро; Ры -, Ри где ( «гг+ 1. С1. [Начало фазы 1.] Установите МТ(Хг) г — шг и ЕЕ1МК(Хг) + — 811МК(Хь) +- Л для О < а < и. Установите также Ро +- Хг„гы ЫТ(Ро) +- оо, Рг + — Хо. г +- 1, т +- и. Затем выполните шаг С2 для у = 1, 2, ..., и и перейдиге к шагу СЗ. С2. [Поглощение ш .] (В этот момент у нас выполнены базовые условия МТ(Рг г) > МТ(Р;.~) для 1 < ( < й (31) Другими словами, веса в рабочем массиве "попарно убывающие,".) Выполните подпрограмму С, описанную ниже, несколько раз, пока не будет соблюдено условие МТ(Р~ г) > ш (если это условие соблюдено изначально, то выполнять подпрограмму С не нужно). Затем установите г+-1+ 1 и Рг г — Х, СЗ.
[Завершение фазы 1.] Выполните подпрограмму С несколько раз (возможно, ни разу), пока 1 не станет равным 1. С4. [Фаза 2.] (Теперь Р~ = Хга — корень бинарногодерева и МТ(рг) = шо+ +им.) Установите (г равными расстояниям от ушта Хь до узла Р, для О < к < и (см. упр, 43,. на рис. 18 приведен пример построенного дерева; номера уровней показаны справа от узлов). Сб. [Фаза 3.] Изменяя связи Х„ьг,..., Хг„, постройте новое бинарное дерево с теми же уровнями 1г, но с листьями, расположенными в симметричном порядке Хо, ..., Х„(см. упр.
44: пример полученного дерева показан на рис. 19). 1 Подпрограмма С (Обогдингиие). Эта подпрограмма является "сердцем" алгоритма Гарсия-Воча. Она объединяет два веса н смещает нх на необходимое количество полей влево, обеспечивая выполнение условия "непарного убывания" (31).
С1. [Инициализация.] Установите Й г- г. С2. [Создание нового узла.] (В настоящий момент й > 2.) Установите т г — т+ 1, Е(.1МК(Х„,) г- Рь ы йб1МК(Х,„) + — Рь, МТ(Х„,) + — МТ(Рг г) + ЫТ(Рг). СЗ. [Сдвиг последующих узлов влево.] Установите г г- ( — 1. а затем Рг.,г < — Р, для 1<1«С. С4. [Сдвиг предыдущих узлов вправо.] Установите у ! — Й вЂ” 2; затем, пока ЫТ(Р/) ( НТ(Х„,), присваивайте Рг,~ <- Р, и / <- / — 1. Сб. [Вставка нового узла.] Присвойте Р/ы ~ — Х СН.
[Всеу] Если/' > 0 и НТ(Р, !) < ЫТ(Х„,), присвойте й+-/ и вернитеськ шагу С2. 1 Как указывалось выше, подпрограмме С может потребоваться ()(и) шагов для создания и вставки нового узла, поскольку она использует последовательное хранение в памяти вместо связанных списков. Таким образом, общее время работы алгоритма С может составлять й(пз).
Однако более тщательная разработка применяемых структур данных может привести к использованию не более 0(п!ойп) шагов (см. упр. 4э). Фазы 2 и 3 требуют только 0(п) шагов. Кляйтман (К!е!Мпап) и Сакс (Ба(гз) (ЯХ4М ./. А!НеЬ, Р/зсг. Мег!юсЬ 2 (!981), 142 — 146) доказали, что оптимальная взвешенная длина пути никогда не превышает значение оптимальной взвешенной длины пути, которая получается при перестановке Ч в "пилообразном" порядке: ЧО~Чз ~Ч4~'''~Ч2(в/2' ~Чт(в/в! — 1 ~'''~ЧЗ ~Ч1 (32) (Этот порядок представляет собой инверсию "органного" порядка, который обсуждался в упр. 6.1 — 18.) В последнем случае алгоритм Гарсия-Воча сводится к алгоритму Хаффмана на множестве весов Чв + Чм Чз + Чз....., поскольку веса в рабочем массиве в действительности находятся в порядке невозрастания [а не только в "попарно убывающем" порядке, как в (31)). Следовательно, мы можем улучшить верхнюю границу в теореме М, не зная порядка весов.
Оптимапьное бинарное дерево на рис. 19 имеет, помимо значения в теории поиска, большое прикладное значение в теории кодирования: используя 0 для левых ветвей дерева и 1 — для правых, мы получим следующие коды переменной длины. 00 1 1000 Н 11001 А 0100 ,1 1001000 Б 1101 Н О!0100 Н 1001001 Т 1110 С 010101 1, 100101 0 11Г100 0 01011 М 10011 Ч 111101 (ЗЗ) Е 0110 Н 1010 Н 111110 Р ОИ 100 О 1011 Х 11111100 0 011101 Р 110000 Т 11111101 Н 01111 Ц 110001 2 ШПП Таким образом, сообщение типа Н1ОНТ ОН может быть закодировано строкой 1100110000111010111111100010111010.
Декодирование слева направо выполняется просто и однозначно, несмотря на то что коды имеют различную длину — сама структура дерева показывает, когда заканчивается один символ и начинается другой. При данном методе кодирования сохраняется алфавитный порядок и используется в среднем около 4.2 бит для кодирования одного символа. Таким образом, этот код можно использовать для упаковки файлов данных без нарушения лексикографического порядка буквенной информации. (Число 4.2 бит иа символ минимально среди всех кодов, в которых используются бинарные деревья: ано может быть уменьшено до 4.1 бит на символ при отказе от алфавитного порядка. Уменьшение до 4.1 бит на символ с сохранением алфавитного порядка возможно при кодировании ие отдельных символов, а пар символов.) История и библиография.
Рассмотренные в этом разделе методы поиска с использованием деревьев были открыты независимо несколькими исследователями в 50-е годы. В неопубликованнолл меморандуме, датированном августом 1952 года, А. И. Думи (А. 1. Пнтеу) описал приллитивный путь вставки в дерево. Рассмотрим барабан с 2" элементами, каждый из которых имеет бинарный адрес. Следуйте описанной ниже программе. 1. Прочтите первый элемент и поместите его по адресу 2" ', т. е. в середину массива хранения. 2. Прочтите следующий элемент. Сравните его с первым. 3.
Если он больше, поместите его по адресу 2" ' + 2ь-з. Если же ан меньше, поместите его по адресу 2"-з, и т. д. Другая ранняя форма вставки в дерево была введена Д. Дж. Вилером (1У. Х ЖЬее1ег), который допускал многапутевые разветвления (подобные тем, которые булут рассмотрены в разделе 6.2.4); еще один метод вставки в бинарное дерево был предложен К. М. Бернерсом-Ли (С. М. Вегпеге-1 ее) (см. Сотр. Х 2 (1959), 5).
Первые опубликованные описания вставки в дерево принадлежат П. Ф, Виндли (Р. Р. %1пб!еу) (Сотр, Х 3 (1960), 84 — 88), Э. Д. Бугу (А. Р. ВоосЬ) и Э. Дж. Т. Колину (А. Х Т. Со11п) (1пуогтабоп аль Сопсю1 3 (1960), 327-334), а также Томасу Н. Хиббарду (ТЬошаз Н. Н1ЬЬшт1) (,1АСМ 9 (1962), 13 — 28). По-видимому, каждый из авторов пришел к своему методу независимо от других, и в каждой статье среднее количество сравнений (6) выводится по-своему.
Авторы также сосредоточивали свое внимание на разных аспектах алгоритма: Виндли подробно разбирал сортировку путем вставки в дерево, Бут и Калин исследовали влияние предварительного построения идеально сбвлансированнога дерева из первых 2" — 1 элементов (см. упр. 4), Хиббард предложил идею удаления и показал связь между анализом вставки в дерево и анализом быстрой сортировки.
Идеи оигпимольнмх бинарных деревьев поиска первоначально были развиты для частного случая р~ = . — — р„= 0 в контексте бинарного кодирования алфавита, подобного (33). В очень интересной статье Э. Н. Гильберта (Е. )л1. С11Ьег1) и Э. Ф. Мура (Е.
Р. Мооге) (Вой Вуэгет Тесй. Х 38 (1959), 933-968) обсуждается эта задача и ее связь с другими задачами кодирования. Гильберт и Мур доказали теорему М для специального случая Р = 0 и заметили, что оптимальное дерево может быть построено за 0(лл~ ) шагав с помощью метода наподобие алгоритма К, на без использования соотношения монотонности (17). К.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
