Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 22
Текст из файла (страница 22)
Такая замена изменит общую стоимость на -с — 9»(!» — 1»+з — 1) + 9»+з < 9»ч.~ — 9» з. Значит, данное дерево не было оптимальным, если выполнялось условие 9» ~ > 9»~.~,' в случае 9» ~ = 9»~.~ оптимальное дерево было трансформировано в другое оптимальное дерево. В последнем случае последовательность таких трансформаций приведет к 1» <!»+м $ Более глубокий анализ структуры даст нам значительно больше.
Лемма Х. Предположим, что у я к — индексы, такие, что у < й и 1) ф з > 9з.~.~ пйн 1 < 1 < й; Й) 9»-~ < 9»+з,' 61) Ф < 9» з + 9» при 7 < 1 < к )ч) %-з > 9»-~ +9». Тогда существует оптимальное дерево, в котором 1» ~ = 1» и либо а) 1 = 1» — 1, либо Ь) 11 —— 1» и '(,!') является левым дочерина узлом. Доказан»ельстео. При замене "левого" "правым" в лемме % мы увидим, что (й) означает существование оптимального дерева„в котором 1» ! > 1».
Однако ле»»ма 1т' и (1) означают, что 1! < 1» « ° 1». Следовательно, 1» ! = 1». Предположим, что 1, < 1» — 1 < 1,+! для некоторого ! < з < й. Пусть 1 представляет собой наименьший индекс, меньший й, такой, что 1! = 1». Тогда 1,.»! = " = 1! ! = 1» — 1 и [в+1) представляет собой левый дочерний узел. Отсюда вытекает, что !-е нечетно и узел Я является левым дочерним уз!»о»! при ! = »+1, »+3,..., 8. Заменим родительский узел узла Я узлом !+1, а узел Я вЂ” узлом ~в+1~ для я < ! < 1.
Кроме того, заменим внешний узел ~е] внутренним узлом, дочерними узлами которого являются Я и Г».»1). Все зти замены приведут к изменению цены на < д, — д! — д»е! < д, — д» ! — ды т. е. к улучшению дерева при д, < д» ! + д». Следовательно, согласно (1И) 11 > 1» — 1. Дозтого момента мы ни разу не использовали гипотезу (1т). Если 1; = 1» и ' не является левым дочерним узлом, то Я должен быть правым "брауом" узла '-1 .
Заменим их родительский узел узлом ~Я~, а затем заменим каждый лист листом (»-1) для ! < ! < й. Заменим также внешний узел (и) внутренним узлом, являющимся родительским по отношению к (к--») и (»;). Эти действия изменят цену на — д »+9» »+д» < О, так что мы получим оптимальное дерево, удовлетворяющее условию (Ь).
! Лемма Ъ'. Пусть .! а й те же, что и в лемме Л. Рассмотри»! измененные вероятности(де,...,д„',) = (де,...,д »,д», +д»,д,,д» »,д» „...,д„), полученные посредством удаления д» ! и д» и вставки д» ! + 9» после д !. Тогда С(дО ''' д -!) < (д»-»+д») +С(де д ) (29) Доказан»ельсп»во. Достаточно показать, что любое оптимальное дерево для (де,..., д„) может быть трансформировано в дерево той же цены, в котором Я.—:и) и (к) являются "братьями"„т.
е. имеют один и тот же родительский узел, н листья которого появляются в следующем порядке: ДО ()!!'-.0 Я-Я (к) Ц ... (к — 2 2)()Б) ... Я. (30) Мы начнем с дерева, сконструированного в лемме Х. Если зто дерево тина (Ь)„ просто переименуем листья, сместив,й-1~ и $~ влево на Й вЂ” 1 — У мест. Если же это дерево типа (а), предположим, что 1!-~ = 1»-1 н 1, = 1». Вэтом случае мы действуем следующим образом: сначала сместим (я — !.) н Я влево на Й вЂ” 1 — и мест, затем заменим нх новый родительский узел узлом, дочерними узлами которого являются (»Я~ ~и Я~, а также заменим узел Я узлом (з — 1~ для всех,1 < ! < ж $ Лемма 2.
Прп выполнении условий леммы У неравенство (29) становится равен- ством. Доказан»ельсвпео. Каждое дерево для (де,..., д'„, ) соответствует дереву с листьями (30), в котором выпадающие из общего порядка листья Я-0 и Б) представляют дочерние узлы одного н того же родительского узла. Пусть зтот родительский узел — (х). Мы хотим показать, что любое оптимальное дерево этого типа может быть конвертировано в дерево той же цены, но в котором листья располагаются в нормальном порядке — Я) ... Я. 556 ! 414 ! ЗЗЗ 2 !ее 3 147 3 !22 3 Ыб 5 114 3 431 з Зе 6 53 4 Зе б Рис. 18. Применение нисоритма ! арсии-Вача к данным о честознх поивления буки; фазы 1 и 2.
156 64 !3 22 31 153 2! !5 47 1 5 2 4 б 6 5 б 5 4 7 В'СЕЕР55115 З2 25 57 63 15 1 б 6 4 4 б В 2 О Р Я 45 Ы 66 2З Е \Е ! 1Е 5 4 4 6 6 6 6 6 7 Е 5 Т 5 Т В 2 Т Есви 1 = л — 1, доказывать нечего. В противном случае мы имеем 4,', > д,'чч дла1 <1< 5-1, посколькУоэ ~ > дь ~+Дэ > дэ. Следовательно, согласнолемме% 1х < 1 « 1э м где 1, — уровень Ох и 1, — уровень Г~ ~ для 1 < 1 < л — 1. Если же 1 = 1ь ач мы просто смешаем узел Я вправо, замещая последовательность Ох Я, . (л-2) последовательностью Я ... (х-2) Ох; это расположит листья в требуемом порядке. В противном случае предположим, что 1, = 1г и 1,~.~ > 1,. Сначала заменим ® )э') ... ~в на Е ...
Я Я; получим 1 < 1+~ < < 1ь т, где 1 = 1, + 1— общий уровень узлов Я-Д~ и Щ. И, наконец, заменим узлы (ЕЦ ) л) )э+1) ....~~-2 при помощи циклической перестановки. В упр. 40 доказываетсл, что этп действия приведут к уменьшению цены (за исключением случая 1ь . = 1). Однако поскольку согласно лемме Ъ' цена не может уменьшаться, следовательно, 1я э = 1 и лемма доказана. ! Эти леммы показывают, что задача для и + 1 весов 4е, ш, ..., д„может быть сведена к задаче для и весов: сначала находим наименьший индекс А„такой, что йя ~ < 4ь+ы а затем — наибольшее у < л, для которого 4 ~ > дя ~+4ь. После этого мы УдалЯем оь г и Оэ и вставлием сУммУ Уэ-~ +4ь ЯепосРедственно после дэ ~.
В специальном случае з = 0 или )г = и, как вытекает из доказательства, мы должны действовать так, как если бы У нас были бесконечные веса 4 ~ и д„э ~ слева н спРава. Доказательства также показывают, что любое оптимальное дерево Т', полученное на основе новых весов Щ,...,д'„,), может быть переупорядочено в дерево Т, в котором исходные веса (цо: .
° ., д„) находятся в корректном порядке слева направо; более того, каждый вес появляется на одном н том же уровне как в дереве Т, так и в дереве Т'. В качестве примера на рис. 18 показано построение дерева для весов 4я, представляющих относительные частоты появления букв „„А, В, ..., 2 в английском тексте. Первые веса в этом списке равны 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 исходных весов превращаются в один вес, 1000, история комбинн1ювания весов определяет бинарное дерево, которое и является решением поставленной задачи. 667 1 7 166 7 '31 3 166 7 35 5 37 5 38 4 57 38 5 70 5 16 5 48 5 З1, Р 37 Н я !8 Рис. 59. Применение алгоритма Гарсии«47оча к данным о частотах ноивмиии букв; фаза 3, 67 „ 1ОЗ „ 6З 3 57 Е 1 ЗЗ» 71 б 155 6 с р с 1 7 5 3 к 58 4 57 4 63 64 4 51 4 86 4 67 И 0 Б Т 1» б ЗЗ„8 е Р 8З 78 8 17 ., Е 1б 6 Т Однако листья дерева на рис.
18 не находятся в правильном порядке, поскольку при каждом перемещении 4» ~ + 4» влево дерево тщатш~ьно запутывается (см. упр. 41). Тем не менее дою»зательство леммы 2 гарантирует существование дерева, листья которого расположены в правильном порядке н на тех же уровнях, что н в "запутанном" дереве. Такое 'распутанное" дерево показано на рис. 19; зто оптимальное дерево получено по алгоритму Гарсия-Воча.
Алгоритм С (Алгорипьн Гарсия-Вача построения онпп»молиных бинорнмл деревьев). Дана последовательность неотрицательных весов юо„юы ... „ю„. Алгоритм позволяет построить бинарное дерево с н внутренними узлами, ~» н~»1» которого минимальна (здесь 1» представляет собой расстояние внешнего узла ~Я от корня дерева). Алгоритм использует массив из 2н + 2 узлов с адресами Х», где О < Й < 2н + 1.
Каждый узел имеет четыре поля, а именно — ЫТ, Ы.1ИК, К(.1ИК и 1.КЧБ., Листья построенного дерева — это узлы Хо... Х„; внутреинимн узлами будут узлы Х„+~ ...Хэ„. Корневым узлом дерева является узел Хтю а узьл'Хоо используется в качестве временного. Алгоритм, кроме того, использует рабочий массив указателей Ро, Рм, Рс где 1 < н + 1. С1. [Начало фазы Ц Установите ЫТ(Х») +- ю» и Ы.1ИК(Х») +- й1.1ИК(Х») +- Л для О < Л < н. Установите также Ро» вЂ” Ха +ы ИТ(Ро)» — оо, Р) +- Хо 1+- 1, т+- н.
Затем выполните шаг 62 для 1 = 1, 2, ..., н и перейдите к шагу 63. С2. [Поглощение»о ..[ (В этот момент у нас выполнены базовые „словия ЫТ(Р; ») > ЧТ(Р»»~) для 1 < 1 < й (31) Другими словами, веса в рабочем массиве "попарно убывающие".) Выполните подпрограмму С, описанную ниже, несколько роз, пока не будет соблюдено условие ИТ(Р»») > в) (если это условие соблюдено изначально, то вьшолнять подпрограмму С не нужно).
Затем установите 1+- 1+ 1 и Р» +- Х . СЗ. [Завершение фазы 1.[ Выполните подпрограмму С несколько раз (возможно, ни разу), пока 1 не станет равным 1. С4. [Фаза2.[ (Теперьр~ = Хоа — кореньбинарногодереваиИТ(Р~) =во+ +ю„.) Установите 1» равнымн расстояниям от узла Х» до узла Р~ для О < к < н (см. упр. 43; на рис. 18 приведен пример построенного дерева; номера уровней показаны справа от узлов). СБ. [Фаза 3.[ Изменяя связи Х„+ы..., Хя и постройте новое бинарное дерево с теми же уровнями 1», но с листьями, расположеннымн в симметричном порядке Хо, ..., Х„(см. упр. 44; пример полученного дерева показан на рис. 19), $ Подпрограмма С (Ооаединение). Эта подпрограмма является "сердцем" алгоритма Гарсия-Воча.
Она объединяет два веса н смещает нх на необходимое количество полей влево„обеспечивая выполнение условия "попарного убывания" (31). С1. [Инициализация,) Установите к»- й С2. [Создание нового узла.[ (В настоящий момент А. > 2,) Установите га»- гн+ 1, 1.1.1ИК(Х, ) +- Р» ы й( 1ИК(Х ~) + — Р», ИТ(Ха~) ~- ИТ(Р»-») + ЪТ(Р»). СЗ. [Сдвиг последующих узлов влево.) Установите г < — ( — 1, а затем Р.»» +- Р для й<1<й С4. ]Сдвиг предыдущих узлов вправо.] Установите у +- !с — 2: затем, пока ИТ(Р!) < ИТ(Х,„), присваивайте Р чп +- Р. и ! +- ! — 1.
Сб. ]Вставка нового узла.] Присвойте Р~+~ < — Хч . Сб. ]Все?! Если у > 0 и ИТ(Р ~) < ИТ(Х,„), присвойте й+- у и вернитесь к шагу С2. ! Как указывалось выше, подпрограмме С может потребоваться П(п) шагов для создаиия и вставки нового узла, поскольку оиа использует последовательное хранение в памяти вместо связанных списков. Таким образом, общее время работы алгоритма О может составлять Й(пт). Однако более тщательная разработка применяемых структур данных может привести к использованию не более О(п)ойп) шагов (см. упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
