Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 36
Текст из файла (страница 36)
Здесь 5(Ж) и б(Х) — сложные функции, которыми можно пренебречь, поскольку их абсолютные значения никогда не превьш~ают 10 е (см, упр. 5.2.2-38 и 5.2.2-48). Конечно же, перед нами стоит более трудная задача: обобщить результаты, полученные для бинарных лучей, на случай М-арных лучей. Мы опишем лишь стартовую точку исследований, помещая детальные инструкции в упражнения. Пусть Ам — среднее число внутренних узлов в случайном ЛХ-арном луче поиска, который содержит Х ключей. Тогда Ае = А~ —— 0 н для Л' > 2 имеем Л'( А =1с- 1' („, „,Я )(А,~"!4„), (е ь~+" +ам=к = 1+ ЛХ ~~' ~ )(ЛХ вЂ” Ц ~Аь при Л'> 2 /Х~ (4) с использованием симметрии и суммирования по /сз,..., /см. Аналогично, если через См обозначить общее среднее количество проверок битов, необходимое для поиска всех )У ключей в луче, то Се — — С~ = 0 н гЛ'~ См = Л'+ М' ~ ~ ~(ЛХ вЂ” 1)~ «Сь прн Л' > 2. (5) В упр.
17 показано, как работать с такого рода рекуррентными соотношениями, а в упр. 18 — 25 приводится соответствующая теория случайных лучей (с другой точки зрения анализ Ам был впервые проведен в работе 1. Н, 3оЬпяоп, М. Н, Л(сАпбгем, ХВМ Х Нее. апд ВетеХ. 8 (1964), 189-193, в связи с зквивалентным аппаратно- ориентированным алгоритмом сортировки]. Если теперь перейти к изучению деревьев цифрового поиска, то обнаружится, что формулы похожи, однако ие настолько, чтобы можно было легко определить асимптотическое поведение. Например, если через Сл обозначить среднее суммарное количество проверок битов при поиске всех Х ключей в М-арном дереве цифрового поиска., нетрудно вывести, как и ранее, что Се = С~ = О и См~.~ =Х+ЛХ' ~ ~~~ ( ) (М вЂ” 1)~ ьСь при У > О. Л (6) Это выражение практически идентично выражению (5), однако появления Х + 1 вместо ХХ в левой части уравнения достаточно для того, чтсбы коренным образом изменить характер рекуррентности, а потому использовавшиеся при изучении (5) методы становятся неприемлемыми.
Рассмотрим сначала бинарный цифровой поиск. На рис, 35 показано дерево цифрового поиска, соответствующее шестнадцати ключам из рис. 34, если они поскольку Л'! М ь/й~!... Лм. 'представляет собой вероятность того, что Л~ ключей находятся в первом подлуче, ..., Лм — в ЛХ-м. Это соотношение может быть переписано как вставляются в порядке, который использовался в примерах главы 5. Если будет необходимо определить среднее количество проверок битов прн случайном успешном поиске, окажется, что зто просто длина внутреннего пути дерева, деленная на Х, так как для поиска узла на уровне 1 потребуется 1 проверок. Заметим, однако, что среднее число проверок битов при случайном неудачном поиске не гпак просто связано с длиной внешнего пути дерева, поскольку неудачный поиск с большей вероятяостью оканчивается во внешнем узле недалеко от корня.
Так, вероятность достижения левой ветви узла Р075 на рис. 35 равна 1 (при рассмотрении ключей с бесконечной точностью), а вероятность попадания в левую ветвь узла Оддд составляет лишь »1. Из-за зтого деревья цифрового поиска при равномерном распределении ключей в целом лучше сбалансированы, чем бинарные деревья поиска из алгоритма 6.2.2Т. Рис. 35. Дерево случайного цифрового поиска„построенное по алгоритму Э. Для описания соответствующих характеристик деревьев пифрового поиска можно воспользоваться производящей функцией. Пусть на уровне 1 находится ау внутренних узлов. Рассмотрим произвсдящую функцию а(») = ~",'~ а~»'. Допустим, что производящая функция, соответствующая рис.
35, — а(») = 1 + 2» + 4»» + 5»~ + 4»4. Если на уровне 1 находится Ь~ внешних узлов и Ь(») ж 2,5~»', то согласно упр. 6,2.1-25 получаем Ь(») = 1+ (2» — 1)а(»). (7) Например, 1+ (2» — 1)(1+ 2»+ 4»» + 5»» + 4»») = 3»» + 6»» + 8»~. Среднее количество проверок битов при случайном дспешио»» поиске равно а'(1)/а(1), так как а'(1) — длина внутреннего пути дерева, а а(1) — количество внутренних узлов. Среднее количество проверок битов при случайном неудачном поиске составляет ~~ 15|2 ' = »Ь'(-') = а(~1), поскольку мы достигаем данного внешнего узла уровня 1 с вероятностью 2 ~.
Количество сравнений о»впадает с количеством проверок битов (плюс 1 при успешном завершении поиска). Например, на рис. 35 при успешном поиске будет выполнено в среднем 2,»е проверок битов и 3 зв сравнений, в то время как в случае неудачного поиска обе зти величины будут равны 3»т. Обозначим через дл(г) усредненную по всем деревьям с Х узлами функцию а(»); другими словами, дм(») представляет собой сумму 'Я рт от (») по всем бинар- члены, многие нз которых сократятся. Более полезная формула для ~~и может быть получена в результате применения тождеств из упр. 5.1.1-16: См = (П(1 — 2 1)~ ~~ ~ )(-1) П(1 — 2 ~ ~ ~) ' ~т>! у е>о !30 2 (~~ ~ )(-2 )" — 1+2 Х) П(1 — 2 ~ ') е~>0 с а ~ 1>о 2" Ы" 2™((1-2 ™)ьт — 1+2 "'Х) ~~~ ( — 2 ' ')" .
(14) >о е>о П,=1 (1 2 ) На первый взгляд, никакого улучшения по сравнению с (12) не произошло, однако очень большое достоинство полученного результата заключается в том, что сумма по гп довольно быстро сходится лля любого фиксированного и, Аналогичная ситуация возникает и в случае луча в формулах 5.2.2-(38) и о.2.2-(39); в самом деле, прн рассмотрении только членов с и = О нз (14) получается в точности Ж вЂ” 1 плюс количество проверок битов в бинарном луче.
Теперь можно получить асимптотическое значение так же, как и ранее (см. упр. 27). [Приведенный вывод базируется, в основном. на подходе, предложенном в работе А. 3. Коппе1ш„0. Я. 1чевчпап, 01асгесе Маслешабст 4 (1973), 37-63]. Рис. 36. Дерево, которое строится алгоритмом "Патриция" вместо луча, приведенного ва рис. 34. И, наконец, бросим на метод "Патриция" "математический" взгляд.
В таком случае бинарное дерево похоже на соответствующий луч с теми же ключами, но менее простым способом. Однако теория преобразований Меллина, приведенная в разделе 5.2.2, обеспечивает возможность работы с такого рода рекуррентными соотношениями. Оказывается, решение (17) содержит числа Бернулли: и-1 2 ~/с/2в ' — 1 (18) ь=т Эта формула, вероятно, представляет собой самый твердый асимптатический орешек, который был раэгрыэен в данной книге. Решение, представленное в упр. 34, является поучительным обзором мнагкх ранее встречавшихся задач (с некоторыми нюансами).
Итоги анализа. Следующие результаты сложных математических выкладок этого раздела заслуживают особого внимания. а) Количество узлов, которые необходимы для хранения )ч случайных ключей в М-арном луче с разветвлениями, прекращающимися по достижении падфайлов из ( в ключей, составляет примерна Х/(в 1п М). Это приближение справедливо при больших Л', малых в и малых М. Поскольку узлы луча содержат М полей ссылок, всего при в = М потребуется окало Х/1и М полей ссылок. Ь) Количество цифр нли символов, проверяемых в ходе случайного поиска, составляет для всех рассмотренных методов примерно 1обы Х.
При М = 2 различные методы анализа дают более точные приближения для количества проверок битов. Успешный Неудачный Поиск по лучу 18 Х + 1.33275 18 Л' — 0.10995 Цифровой поиск по дереву 18 Ю вЂ” 1,71665 18 /г' — 0.27395 Поиск методом "Патриция" 18йг+ 0,33275 18Х - 0.31875 (Эти приближения могут быть выражены фундаментальными математическими постоянными; например, 0.31875 на самом деле означает (!их — у)/1п 2 — 1/2).
с) "Случайные данные" в нашем случае означают, что М-ичные цифры равномерно распределены, как если бы ключи были действительными числами между 0 и 1, записанными в М-ичной системе счисления, Методы цифрового поиска не зависят от порядка, в котором ключи введены в файл (за исключением алгоритма П, который слабо чувствителен к порядку); однако они весьма чувствительны к распределению цифр. Например, если нулевые биты встречаются гораздо чаще единичных, деревья будут существенно более асимметричными по сравнению с деревьями, полученными для случайных данных (в упр, 5,2,2-53 приведен пример того, что может случиться при таком смещении данных). УПРАЖНЕНИЯ 1.
[ОО) Если дерево имеет листья, та чта имеет лучу 2. [90) Разработайте алгоритм вставки нового ключа в М-арный луч с использованием соглашений азгвритма Т. 3. [в1) Разработайте алгоритм удаления ключа из М-арного луча с использованием соглашений алгоритма Т. 4.
[81) Большинство из 360 элементов, приведенных в табл. 1, представляет собой пустые ссылки. Оливка можно сжать таблипу да 49 элементов, перекрыв непустые в пустые элементы, как показано ниже. Позинэя Злемеэт Позкцкя Эленект (Узлы (1), (2), ..., (12) в табл. 1 начинаются соответственно в позициях 20, 19, 3, 14, 1, 17, 1, 7, 3, 20, 18, 4 этой сжатой таблицы.) Покажите, что, если сжатой таблицей заменить табл. 1, программа Т останется рабо- тоспо«обной, хотя и ие столь быстрой. э б.
[э486] (Я. Н. Патт (У. Ж. Раы),) В деревьях на рнс. 31 содержатся буквы каждого семейства, упорядоченные по алфавиту. Такое упорядочение не является необходимым. и, если переупорядочить узлы внутри каждого семейства перед построением дерева типа (2), поиск может ускориться. Какое переупорядочение представленного на рис. 31 дерева прэдюдет к оптимальному с этой точки зрения результату? (Используйте частоты, приведенные иа рис. 32, и найдите "лес", который позволит минимизировать время успешного поиска, когда он представлен в виде бинарного дерева.) 6. [15] Какое дерево цифрового поиска получится при вставке 15 четырехбитовых бинарных ключей 0001, 0010, 0011,..., 1111 в порядке возрастания согласно алгоритму О? (Начните с ключа 0001 в корневом узле и выполните 14 вставок).
° 7. [Мйб] Бсяи 15 ключей из упр. 6 вставлены в другом порядке, может быть построено другое дерево. Какая перестановка этих ключей из всех 16! возможных будет иаилудшей в том смысле, что она породит дерево с наибольшей длиной внутреннего пути? 8. [20] Рассмотрим следующие изменения в алгоритме П, ведущве к исключению вз него переменной К': заменим "К'" на "К" ва шаге П2 н удалим операцию "К' +- К" на шаге П1.
Будет ли полученный в результате этих действий алгоритм корректным, и можно ли с его помощью выполнять поиск и вставку? 9. [81] Напишите 812-црограмму для алгоритма П и сравните ее с программой 6.2.2Т. Можете использовать бинарные операции, такие как Я.В (бинарный сдвиг АХ влево),,148 (переход при четном А) и дрп возможно, вам поможет упр. 8. 10, [Зу] Даи файл, все ключи которого представляют собой и-битовые двоичные числа, и даи аргумент поиска К = Ь~ Ьз " Ь . Предположим, что необходимо найти максимальное значение Ь, при котором в Файле будет содержатьсл ключ, начинающийся с Ь! Ьэ...
Ьэ Как эффективно решить поствкленную задачу, если файл представлен в виде а) бинарного дерева поиска (алгоритм 6.2.2Т); Ь) бинарного луча (алгоритм Т); с) бинарного дерева цифрового поиска (алгоритм П)? 11. [81] Можно ли использовать неизмененный алгоритм 6.2.20 для удалешся узла из дерева цифрового поиска? 12. [86] Будет ли случайным дерево, полученное путем удаления случайного элемента из случайного дерева цифрового поиска, которое построено с помощью алгоритма О? (См.
улр, 11 и теорему 6.2.2Н.) 13. [ЕО) (М-арнмп цифровой поиск.) Обьясиите, как можно обьединить алгоритмы Т и П в один обобщенный алгоритм, при М = 2 представлшощий собой алгоритм П, Какие изменения следует внести в табл. 1 для использования алгоритма при ЕХ = 30? ь 14. [85[ Напишите аффективный алгоритм, который может быть выполиеи сразт после успешного окоичания алгоритма Р дзя нахождения всех мест, в которых ТЕХТ содержит К. 15.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
