AOP_Tom1 (1021736), страница 115
Текст из файла (страница 115)
Всякий раз, когда в построении объединяются два веса, они по крайней мере не меньше весов, которые объединялись на предыдущем этапе, если все ю;— неотрицательные числа. Это значит, что существует прекрасный способ поиска дерева Хаффмэна при условии, что веса расположены в порядке неубывания. Тогда достаточно создать две очереди, одна из которых будет содержать исходные веса, а другая — объединенные веса. На каждом этапе этой процедуры наименьший неиспользованный вес будет находиться в начале одной из очередей, поэтому его не придется игкать. В упр. 13 показано, как реализовать эту процедуру при работе с отрицательными весами. Вообще, существует много деревьев, которые минимизируют 2 ю,1,. Если в описанном выше алгоритме при очередном объединении весов всегда используется исходный, а не комбинированный вес, то полученное с помощью этого алгоритма дерево будет иметь наименьшее значение величин гпах1, и 2 1, среди всех деревьев, которые минимизируют 2,'ю 1..
Если веса принимают положительные значения, это дерево также минимизирует 2 ю. 7(1 ) для любой выпуклой функции 7' по всем таким деревьям. [См. Е. 8. Бслюагсх, 1лГогта11ол алс( Сол1го! 7 (1964), 37 — 44; С. Маг]гоша]су, Асса 1л?оггла11са 16 (1981), 363-370.) Метод Хаффмэна можно обобщить для г-арных, а также для бинарных деревьев (см. упр. 10). Еще одно важное обобщение метода Хаффмэна рассматривается в разделе 6.2.2. Обсуждение длины пути будет продолжено в разделах 5.3.1, 5.4.9 и 6.3.
УПРАЖНЕНИЯ 1. [18) Существуют лн какие-либо другие бинарные деревья с 12 внутренними узлами и минимальной длиной пути, кроме полного бинарного дерева (5)? 2. [17] Нарисуйте схему расширенного бинарного дерева с концевыми узлами, которые содержат веса 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, имеющие минимальную взвешенную длину пути. 3. [М21) Расширенное бинарное дерево с тл внешними узлами определяет множество длин пути 1м1щ, 1ж от корня к соответствующим внешним узлам. И наоборот, если дано множество чисел 1м1г, -,1, всегда ли можно построить расширенное бинарное дерево, в котором эти номера являются длинами пути, расположенными в некотором порядке? Покажите, что это возможно тогда н только тогда, когда 2 ., 2 ' = 1.
4. [М25] (Задача Э. С. Шварца (Е. 8. Бс1пгагсх) и Б. Каллика (В. Ка1)1ск).) Предположим, ш~ < шз < < ш . Покажите, что существует расширенное бинарное дерево, которое л~инимизирует 2, ш,(, и для козорого концевые узлы в порядке слева направо содержат значении иц, шт,.,,, ш,„. [Например, дерево (11) ме удовлетворяет этому условию, так как веса в нем располагаются в порядке 19, 23, 11, 13, 29, 2, 3, 5, 7, 17, 31, 37, 41. Мы ищем дерево, в котором веса располагаются в порндке возрастания, а это условие не всегда выполняется в построении Хаффмэна.] 5. [ВМ25] Пусть В( , ) = ~ ььа " ", ,р>о где 5 р — количество бинарных деревьев с и узлами и внутренним путем длиной р.
[Таким образом, В(ш,з) = 1+ э+2ия~+ (ш +4шз)яз+ (4ш" -ь2ш~+ 8ше)гэ+ В(1, з) — функция В(х) из уравнения (13) раздела 2.3.4.4.] а) Найдите функциональное соотношение, которог характеризует В(иг,а), обобщив 2 3.4.4 †(12). Ь) Используйте результат (а) для определения средней внутренней длины путаю бинарного дерева с и узлами, предполагая, что каждое из +(~,") деревьев равновероятно. с) Найдите асимптотическое значение этой величины. 6. [15] Какое соотношение, аналогичное соотношению (2), можно установить между количеством квадратных и круглых узлов, если 1-арное дерево расширить квадратными узлами, как в (1)? 7. [М21) Какое соотион~ение можно установить между длинами внешнего и внутреннего путей в барном дереве? (См, упр. 6; необходимо получить обобщение уравнения (3).) 8.
[Мйу] Докажите справедливость формулы (7), 9. [М2Ц Числа в круглых узлах дерева (11) равны сумме весов из внешних узлов соответствующих поддеревьев. Покажите, что сумма всех значений в круглых узлах равна взвешенной длине пути. ь 10. [Мйб] (Задача Д. Хаффмзна.) Покажите, как можно построить 1-арное дерево с минимальной взвешенной длиной пути для заданных неотрицательных весов ич., шм, ш„. Постройте оптимальное тернарное дерево для весов 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.
11. [15] Существует ли связь межлу полным бинарным деревом (5) и десятичной системой обозначений Дьюи для бинарных деревьев, описанной в упр. 2.3,1 — 5? ь 12. [М20] Пусть случайным образом выбран некоторый узел бинарного дерева, причем такой выбор равновероятен для всех узлов дерева. Покажите, что средний размер подле. рева с корнем в этом узле связан с длиной пути данного дерева. 13, [22] Создайте алгоритм, который на основе гл весов вл < юг « ш приводит к построению расширенного бинарного дерева с минимальной взвешенной длиной пути. Представьте итоговое дерево в виде трех массивов А[Ц...
А[2гл — Ц, ЦЦ... В[т — Ц, Н[Ц... Я[т — Ц, где 8[1] и В[1] указывают на правых и левых детей внутреннего узла 0 корнем является узел 1, а А[1] — это вес узла б Исходные веса следует представить в виде весов внешних узлов А[т], ..., А[2т — Ц. При этом в созданном алгоритме должно выполняться менее чем 2т сравнений весов. Замечание.
Некоторые или все из представленных весов могут иметь отрицательное значение! 14. [25] (Задача Т. Н. Ху (Т. С. Нц) и А, К. Такера (А. С. Твс)гег).) После и шагов алгоритма Хаффмэна объединенные узлы образуют лес из т — й расширенных бинарных деревьев. Докажите, что этот лес имеет наименьшую общую взвешенную длину пути среди всех лесов, состоящих из т — й расширенных бинарных деревьев с данными весами. 15.
[М95] Покажите, что алгоритм, подобный алгоритму Хаффмэна, позволяет найти расширенное бинарное дерево„которое минимизирует величины (а) ивах(ю! + Н,..., ю + 1 ) (Ь) ю!х" + + ю «х' для заданного х > 1. 16. [М25! (Задача Ф. К. Хвана (Е. К. Нюапк).) Пусть ю! « . юм и ю! « ю' два лгножества весов с ю<~ ю, для 1 < й < т. у=! в=! Докажите, что минимальная взвешенная длина пути удовлетворяет неравенству < ~~! и!,1;. в=! 17. [НМЯ0] (Задача Ч. Р. Глэсси (С. Н. 61алвеу) и Р.
М. Карпа (Н. М. Кагр).) Пусть в„..., в ! — числа во внутренних (круглых) узлах расширенного бинарного дерева, образованного с помощью алгоритма Хаффмэна, расположенные в порядке его построения. Пусть « в!,..., в, — веса внутренних узлов произвольного расширенного бинарного дерева с тем же множеством весов (ю!,..., ю ), которые перечяслены в таком произвольном порядке, что каждый некорневой внутренний узел располагается перед его родителем. (а) Докажите, что ) в <~ в„ для 1 < й < т.
(Ь) Результат (а) эквивалентен выражению для каждой неубывающей вогнутой функции у, а именно — для каждой функции У с У'(х) > О и У«(х) < О. [См. НаЫу, Ь!гг!еюооб, апс1 Рб!уа, Меввелбег оу Ма!5. 58 (1939), 145 — 152.] Используйте этот факт, чтобы показать, что минимальное значение в рекурреитном соотношении Р(г!) = у(п) + ппп (Е(!г) + Г(п — й)), Е(1) = О !«в< всегда достигается для и = 2!!в!«!вн прн условии, что данная функция у(п) обладает свойствами !зу(п) = 1(п + 1) — 7(п) > О и «а!у(п) = зу(п + 1) — Ы(п) < О. в2.3.4.6. История и библиографии.
Как известно, деревья появились уже на третий день сотворения мира и на протяжении веков древовидные структуры (особенно —. генеалогические деревья) очень широко применялись. Как вватематическмй объект понятие дерева было впервые формально определено, по-видимому, в работе Г. Р. Кирхгофа (С. В. К!гс1!ЬоК) [Аппа)еп г)ег РЬувР2 ппг) Сйепие 72 (1847), 497— 508, в английском переводе опубликовано в 1ВЕ ТгапзасНопв СТ-5 (1958), 4 7].
Он использовал свободные деревья для поиска набора фундаментальных циклов в электрической цепи с помощью законов, которые теперь носят его имя. Причем Кирхгоф делал это почти так же, как м4и в разделе 2.3.4.1. Приблизительно в то же время понятие "дерево" появилось в книге К. Г. К, фон Штаудта (К. С. СЬг. гоп Бгаш1г) [СеогпесНе дег Ба8е (рр.
20 — 21)]. Термин "дерево" и многие результаты, которые, в основном, имеют отношение к задаче перечисления деревьев, появились десять лет спустя в ряде работ Артура Кали (АггЬпг Сау1еу) [см. Со!!ессеи Магйетабса! Рарегэ оГА. Сау!еу 3 (1857), 242-246; 4 (1859), 112-115: 9 (1874), 202-204; 9 (1875), 427 — 460; 10 (1877), 598 — 600; 11 (1881), 365-367: 13 (1889), 26-28]. Кэпи не знал о работах Кирхгофа и фон Штаудта и свои исследования начал, изучая структуру алгебраических формул. Позднее Кали продолжил их в основном для изучения задач изомерии в химии. Древовидные структуры также независимо изучались К. В.
Борхардтол~ (С. %. ВогсЬаггЬ) [Сге!!е 57 (1860), 111-12Ц, И. Б. Листингом ( д. В, ЫэВпй) [Согбпйег АЬЬапг(!индел, Масй. С1аээе, 10 (1862), 137 — 139] и М. Э. К. Жорданом (М. Е. С. Зогс1ап) [Сге!!е 70 (1869), 185-190]. "Лемма о бесконечном дереве" впервые была сформулирована Д. Кенигом (Пепеэ Кои!8) [Рипдагпепса Магй. 8 (1926), 114-134]: особое место он уделил ей в главе 6 своей классической книги ТЛеог!е г!ег епг!!!сйеп ипг! ипепг!!юсйеп Сгарйеп (Бе!рг!8, 1936). Аналогичный результат. так называемая "теорема о веере", чуть раньше был опубликован в работе Л.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
