AOP_Tom3 (1021738), страница 125
Текст из файла (страница 125)
Ю. Айверсан (К. Е. 1хегвоп) [А Ргойгатттй 1.апйпаде (ИЧ1еу, 1962), 142-.144) независимо рассмотрел другой случай, когда все дь равны нулю. Он предположил, что оптимальное дерево можно получить, выравнивая вероятности левого и правого поддеревьев; к сожалению, мы видели, что эта идея не срабатывает...
Д. Э. Кнут (В. Е. Кппл)л) (Асса 1пуогтабса 1 (1971), 14 — 25, 270) последовательно рассмотрел случаи произвольных весон рл и 9А и доказал, что алгоритм может быть сведен к О(пз) шагам; он также представил пример использования этих методов в компиляторе, где ключами дерева являлись "зарезервированные слова" АЬСОЬ-подобного изыка. Т. Ч. Ху (Т. С. Нп) несколько лет изучал собственный алгоритм для случая рз = О: из-за сложности задачи было трудно найти строгое доказательстно корректности алгоритма, однако в сотрудничестве с А.
К. Таккером (А. С. Тпс!сег) такое доказательство, в конце концов, было найдено [51АМ Х Арр!!Ы МасЛ. 21 (1971), 514-532[. Упрощения, приведшие к разработке алгоритма С, были найдены несколькими годами позже А. М. Гарсия (А. М. Сага!а) и М. Л. Вочем (М. Ь. ЧгасЛв) [51СОМР 6 (1977), 622 — 642[;. их доказательство, впрочем, было слишком сложным и запутанным. Леммы 1У, Х, У и Е, описанные выше, появилигь благодаря Дж.
Х. Кингстону (Х Н. К!пкэсоп) [Х А!Вогййпж 9 (1968), 129 — 136[, (См. также статью Ху (Нп), Кляйтмана (К1ейлпап) и Тамаки (ТашаЫ) [ЯАМ Х Арр!!ег! МагЛ. 37 (1979), 246 — 256], в которой дано элементарное доказательство алгоритма Ху-Таккера и некоторые обобщения для других ценовых функций.) Теорема В доказана Паулем Дж. Байером (Рап! 3. Вауег) [М1Т/ЬСВ/ТМ-69 (Маээ. 1пэк о! ТесЛ., 1975)[, который также доказал теорему М (в ослабленной фор- мулировкеЬ Строгое доказательство у.казанной теоремы найдено К. Мельхорном (К. МеЫЛогп) [51СОМР 6 (1977), 235. 239[. УПРАЖНЕНИЯ 1. [15) Алгоритм Т сформулирован толька для непустых деревьев. Какие изменении должны быть внесены в алгоритм для корректной работы и в случае пустых деревьев? 2.
[60[ Измените алгоритм Т таким образом, чтобы он работал с правоярои~игаььнн деревьями (см. раздел 2.3,1; такие деревья упрощают выполнение симметричного обхода дерева). 3. [60) В разделе 6.1 мы видели, что, внеся небольшие изменения в атгоритм последовательного поиска 6.16, можно сделать ега более быстрым (алгоритм 6.111).
Можно ли воспользоваться похожим приемом для ускорения работы алгоритма Т? 4. [М24) (Э. Д. Бут (А. П. ВоотЬ) н Э Дж, Т. Колин (А. Х '1'. Со!ш).) Даны Аг ключей в случайном порядке. Предположим, что мы используем первые 2" — 1 из них для построения идеально сбалансированного дерева и размещаем 2" ключей на уровне А для всех 0 ( А < н; затем для вставки оставшихся ключей мы используем алгоритм Т. Чему равно среднее число сравнений в случае успешного поиска? (Указание. Модифнпируйте формулу (2).) б. [М25[ Имеется 11' = 39916 800 различных способов упорядочения названий САРК10006, А00АК106 и т. д для их вставки в бинарное дерево поиска.
а) В результате скольких перестановок получится дерево, изображенное на рис. 10? Ь) В результате скольких перестановок получится вырожденное дерево, в каждом узле 0116К или КЬ16К которого равны Л? 6. [М25[ Пусть Р о — количество перестановок а1 аз... а„множества (1, 2,..., п), таких, что прн использовании алгоритма Т для вставки анас,...,а„в изначально пустое дерево для вставки элемента а потребуется ровно ?г сравнений.
(В этой задаче мы пренебрегаем сравненними, выполняемыми при вставке ан...,а„г. В принятых в тексте обозначениях С„', = (2 „АР„о)/пЬ твк как это среднее количество сравнений, которые выполняются в случае неудачного поиска в дереве, содержащем и — 1 элемент.) а) Докажите, что Р< Мь = 2Роы,! + (и — 1)Р„ю (Указание. ПосмотРите, не окажетсЯ ли в дереве а +~ ниже, чем а„.) Ь) Найдите простую формулу для производящей функции С„(э) = 2 „Р,ьх и используйте ее для выражения Р„ь через числа Стирлинга. с) Чему равна дпсперспя этого распределения? 7.
[М25] (С. Р. Арора (Б. В.. Агота) и В. Т. Дент (гэ'. Т. Оеог).) Чему равно среднее количество сравяений, необходимое алгоритму Т для поиска т-го нанболыпего элемента па его ключу после вставки и элементов в случайном порядке в первоначально пустое дерево? 6. [МЗ3] Пусть р(п, 1) — вероятность того, что полная длина внутреннего пути дерева, построенного по алгоритму Т из п случайным образом упорядоченных ключей, равна й (длнна внутреннего пути дерева равна числу сравнений, производимых при сортировке путем вставки в дерево в процессе построения дерева).
а) Найдите рекуррентное соотношение, которое определяет соответствующую производящую функцию. Ь) Вычислите дисперсию такого распределения. (Прн выполнении этого упражнения могут оказаться полезными некоторые упражнения из раздела 1.2.7.) 9. [41] Мы доказали, что поиск по дереву и вставка требуют порядка 2)п М сравнений при вставке ключей в случайном порядке. Однако на практике порядок вставки может быть не случайным Проведите эмпирические исследования, чтобы выяснить, насколько хорошо вставка в дерево подходит для работы с реальными таблицами символов компилятора или ассемблера. Пачучится ли в результате вставки идентификаторов бачьшой программы хорошо сбалансированное дерево поиска? ь 10. [22] (Р. В.
Флойд (Н. % Е)оус)) ) Предположим, нас не интересует порядок ключей в дереве поиска; однако ожидается, что данные будут вводиться в неслучайном порядке. Обдумайте методы, которые позволят сохранить эффективность поиска, делая входные данные кажущимися слу чайными. 11. [20] Чему равно максимальное число присвоений Б е — ШйКЫ), выполняемых на шаге ОЗ при удалении узла из дерева размером А'? 12. [М22] Как часто в среднем происходит переход от шага О1 к шагу О4 при случайном удалении из случайного дерева, состоящего из АГ элементов? (См. доказательство теоремы Н.) ь 13. [М23] Если корень случайного дерева удаляется с помощью алгоритма О, останется ли получившееся в результате дерево случайным? ь 14.
[22] Докажите, что длина пути дерева, построенного согласно алгоритму О с догюлнительным шагом О11', никогда не превышает длину пути дерева, построенного без этого шага. В каком случае дополнительный шаг О1-' уменьшает длину пути? 13. [23] Пусть а~ аз аз аз — — перестановка множества (1,2,3,4) и пусть 7 = 1, 2 или 3. Возьмем одноэлементное дерево с ключом ам выполним вставку элементов аэ, аэ по алгоритму Т, удалим а~ па алгоритму О и вставим аэ согласно алгоритму Т. Скольхо деревьев из 4! х 3 возможных будут иметь вид 1, П, П!, 1Ч и Ч соответственно (согласно классификации (13))? ь 16.
[25] Является ли операция удаления коммугпагпивнаб? Иначе говоря, получится ли одно и то же дерево, если с помощью алгоритма О будет сначала удален узел Х, а затеи— К и сначала удален узел У, а затем — Х? 17. [23] Покажите, что если э алгоритме П полностью заменить "левое" "правым", то его легко можно будет распространить на удаление данного узла из провопрошппшэо дерева с сохранением необходимых нитей (см.
упр 2). 12. [М21] Покажите, что, используя закон Зипфа, можно получить (12). 19. [М2З] Чему равно приближенное среднее количества сравнений (11), если вероятности входных данных подчиняются закону»80 .20") определенному в 0.1-(11)? 20. [М20] Предположим, что мы вставляем ключи в дерево в порядке уменьшения их частот р1 > ро » р . Не может ли такое дерево оказаться существенно хуже оптимального? 21. (М20] Если р, О, г — случайно выбранные вероятности, такие, что р+ О+ г = 1, чему равны вероятности того, что деревья 1, П, Ш, 1У, У из (13) оптимальны? (Рассмотрите соотношения площадей соответствующих областей на рис. 14.) 22. [М20] Докажите, что при выполнении шага К4 алгоритма К г[1, З вЂ” 1] никогда не превышает г[1+1, 0].
ь 23. [М22] Найдите оптимальное бинарное дерево поиска для случая 0? = 40 с весами Р1 = 9 рг = Рз = . = Р»о = 1„0о = Гп = . = 0»о = 0 (не используя компьютер). 24. [М20] Пусть р = О, = О, а все остальные веса неотрицательны. Докажите, что оптимальное дерева для (рм,.,, рГО до,..., д ) мажет быть получено посредством замены в любом оптимальном для (рм.,.,р»-ц Оо, 0 -~) д~ре~е 26. [М20] Пусть А и  — непустые множества действительных чисел. Определим, что А < В, если выполняется следующее: из (о Е А, 6 Е В и 6 < а) следует (о Е В и 6 Е А).
а) Докажите, что это соотношение транзитивно на непустых множествах. Ь) Докажите нли опровергните, чта А < В тогда и только тогда, когда А < А О В < В. 20. [М22] Пусть (рм,ргб до,..., 0») — неотрицательные веса и р»+О» ы х. Докажите, что при х, изменяющемся от 0 до со, и при постоянных (рм.,.,р -ц до,,я о) цена с(0, и) аптимольнога бинарного дерева поиска является выпуклой, непрерывной, кусочно- линейной функцией х с целыми угловычи коэффициентами. Другими словами, докажите, что существуют положительные целые числа 1о > 1~ > . > 1,„и действительные констан- тыО=хо <х« . х <хмл~ ыаоиуо <у1 .
<у, такие, чтос(О,п) =ул+1лх при хл < х < хл„.п 0 < 6 < т, 27. (МЗЗ] Цель данного упражнения состоит в доказательстве того, что множество корней Л(1,0) оптимальных бинарных деревьев удовлетворяет соотношению Л(л, у — 1) < Л(ОЗ) < Л(1+1, 0) для З вЂ” 1 > 2, где отншпение < введена в упр. 25 при неотрицательных весах (рм..., р»; до,,у»). Доказательство проводится по индукции по З вЂ” 1; наша задача состоит в том, чтобы доказать, что Л(0, и — 1) < Л(0, и) при и > 2 в предположении справедливости соотношения при у — 1 < и.
(В силу симметрии отсюда следует, что Л(0, и) < Л(1, и).) а) Докажите, что Л(0, и — 1) < Л(0, и) при р„= О» = 0 (см. упр. 24). Ь) Пусть р„+ О» = х. Воспользуемся обозначениями упр. 2б. Пусть Лл — множества оптимальных корней Л(0, а) при хл < х < хлч м а Лл — множество оптимальных корней для х = хл. Докажите, что Л,',<Ло<Л',<Л1« Л,'„<Л,. Отсюда из и. (а) и упр.
25 следует, что Н(0, и-1) < Н(О,п) для всех ж (Указание. Рассмотрите случай х = хл н предположите, что деревья й(О, т — 1) С(г., и) и Г(0, з — 1) Г(», и) и ва уровне ! П Е яа уровне !' при )у -+ оа стремится к энтропии Н(рп рю, р ). 35. (НМЯ2] Завершите доказательство теоремы В, доказав справедливость неравенства (24) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
