(Узлы (1), (2), ..., (12) в табл. 1 начинаются соответственно в позициях 20, 19, 3, 14, 1, 17,

I, 7, 3, 20, 18, 4 этой сжатой таблицы.)

Покажите, что, если сжатой таблицей заменить табл. 1, программа Т останется работоспособной, хотя и не столь быстрой.

5. [М26] (Я. И. Патт (Y. N. Patt).) В деревьях на рис. 31 содержатся буквы каждого семейства, упорядоченные по алфавиту. Такое упорядочение не является необходимым, и, если переупорядочить узлы внутри каждого семейства перед построением дерева типа (2), поиск может ускориться. Какое переупорядочение представленного на рис. 31 дерева приведет к оптимальному с этой точки зрения результату? (Используйте частоты, приведенные на рис. 32, и найдите "лес", который позволит минимизировать время успешного поиска, когда он представлен в виде бинарного дерева.)

6. [15] Какое дерево цифрового поиска получится при вставке 15 четырехбитовых бинарных ключей 0001, 0010, ООН,..., 1111 в порядке возрастания согласно алгоритму D? (Начните с ключа 0001 в корневом узле и выполните 14 вставок).

>• 7. [Мйб] Если 15 ключей из упр. 6 вставлены в другом порядке, может быть построено другое дерево. Какая перестановка этих ключей из всех 15! возможных будет наихудшей в том смысле, что она породит дерево с наибольшей длиной внутреннего пути?

8. [20] Рассмотрим следующие изменения в алгоритме D, ведущие к исключению из него переменной К: заменим K" на K" на шаге D2 и удалим операцию "К <- К" на шаге D1. Будет ли полученный в результате этих действий алгоритм корректным, и можно ли с его помощью выполнять поиск и вставку?

9. [21] Напишите MIX-программу для алгоритма D и сравните ее с программой 6.2.2Т. Можете использовать бинарные операции, такие как SLB (бинарный сдвиг АХ влево), JAE (переход при четном А) и др.; возможно, вам поможет упр. 8.

10. [23] Дан файл, все ключи которого представляют собой п-битовые двоичные числа, и дан аргумент поиска К = bibi. - Ьп. Предположим, что необходимо найти максимальное значение к, при котором в файле будет содержаться ключ, начинающийся с bi 62 •.. Ь*. Как эффективно решить поставленную задачу, если файл представлен в виде

a) бинарного дерева поиска (алгоритм 6.2.2Т);

b) бинарного луча (алгоритм Т);

c) бинарного дерева цифрового поиска (алгоритм D)?

II. [21] Можно ли использовать неизмененный алгоритм 6.2.2D для удаления узла из дерева цифрового поиска?

12. [25] Будет ли случайным дерево, полученное путем удаления случайного элемента из случайного дерева цифрового поиска, которое построено с помощью алгоритма D? (См. упр. 11 и теорему6.2.2Н.)

13. [20] {М-арный цифровой поиск.) Объясните, как можно объединить алгоритмы Т и D в один обобщенный алгоритм, при М = 2 представляющий собой алгоритм D. Какие изменения следует внести в табл. 1 для использования алгоритма при М - 30?

► 14. [25] Напишите эффективный алгоритм, который может быть выполнен сразу после успешного окончания алгоритма Р для нахождения всех мест, в которых TEXT содержит К.

15. [28] Разработайте эффективный алгоритм, который может применяться для построения дерева, используемого методом "Патриция" или для вставки новой ссылки на TEXT в существующее дерево. Ваш алгоритм вставки должен обращаться к массиву TEXT не более двух раз.

16. [22] Почему в алгоритме "Патриция" требуется, чтобы один ключ не служил началом другого?

17. [М25] Как выразить решение рекуррентного соотношения

жо = х1=0, ж„ =а„ + т-"Х()(т-1)"-*ж,, п > 2,

С помощью биномиальных преобразований, обобщая метод упр. 5.2.2-36?

18. [М21] Используя результат упр. 17, выразите решения уравнений (4) и (5) через функции и„ и Vn, аналогичные определенным в упр. 5.2.2-38.

19. [НМ23] Найдите асимптотическое значение функции

с точностью 0(1) при п оо для фиксированных значений s > О и m > 1. [Случай для 5 = 0 рассматривался в упр. 5.2.2-50, а случай для s=l, т = 2 - в упр. 5.2.2-48.]

► 20. [МЗО] Рассмотрим М-арную "лучевую" память, в которой используется последовательный поиск по достижении поддерева из s или меньшего количества лучей (алгоритм Т представляет собой частный случай при s = 1). Примените результаты предыдущих упражнений для анализа

a) среднего количества узлов луча;

b) среднего количества проверок цифр или символов при успешном поиске;

c) среднего количества сравнений, выполняемых при успешном поиске. Сформулируйте ответы на вопросы в виде асимптотических формул при N оо для фиксированных М иа; ответ для (а) должен быть дан с точностью до 0(1), а для (Ь) и (с) - до 0(iV"), [При М = 2 этот анализ применим к модифицированному методу обменной поразрядной сортировки, в котором подфайлы размером < а сортируются посредством вставок.]

21. [М85] Сколько узлов случайного М-арного луча с Л ключами имеют в качестве нулевой компоненты пустую ссылку? (Например, 9 из 12 узлов в табл. 1 имеют пустую ссылку в позиции "и" "Случайность" в данном упражнении, как обычно, означает, что цифры ключей равномерно распределены между О и Л/ - 1.)

22. [М85] Сколько узлов находится в случайном Л/-арном луче с N ключами на уровне I ( = 0,1,2,...)?

23. [М86] Сколько проверок цифр выполняется в среднем в процессе неуспешного поиска в Л/-арном луче, содержащем N случайных ключей?

24. [МЗО] Рассмотрите Л/-арный луч, представленный в виде леса (см. рис, 31). Найдите точные и асимптотические выражения для

а) среднего количества узлов в лесу;

b) среднего количества присвоений "Р 4- RLINK (Р)" в процессе случайного успешного поиска.

► 25. [МЙ.] Математический вывод асимптотических значений в этом разделе весьма сложен (использовалась даже теория функций комплексного переменного). Дело в том, что мы не хотели ограничиться одним членом асимптотической формулы, а вывод второго члена действительно сложен. Назначение данного упражнения - показать, что элементарных методов достаточно для вывода некоторых (пусть и ослабленных) результатов.

a) Докажите по индукции, что решение (4) удовлетворяет неравенству An < M{N - 1)/(М-1).

b) Пусть Dn = Cn - NHn-i/\&M, где Cn определяется формулой (5). Докажите, что Dn = 0{N)\ следовательно, Cn = NXogj N -\- 0{N). [Указание. Используйте (а) и теорему 1.2.7А.]

26. [23] Определите значение бесконечного произведения

(l-i)(l-i)(l-i)(l-i)...

с точностью до пяти значащих цифр непосредственным вычислением. [Указание. См. упр. 5.1.1-16.]

27. [НМ31] Чему с точностью до 0(1) равно асимптотическое значение Cn из (14)?

28. [НМ26] Найдите асимптотическое среднее количество проверок цифр при выполнении в случайно.м М-арном дереве цифрового поиска при М > 2. Рассмотрите случай как успешного, так и неудачного поиска; дайте ответ с точностью до 0(iV~).

29. [НМЩ Чему равно асимптотическое среднее количество узлов в М-арном дереве цифрового поиска, все ссылки которых пусты? (Можно было бы сэкономить память, исключая такие узлы; см. упр. 13.)

30. [М24] Покажите, что производящая функция алгоритма "Патриция" hn{z), определенная в (15), может быть выражена в совершенно ужасном виде:

т>1

V..+...=„ i Vai, .,а,п) (2- - 1)(21+= - 1)... (2i- I))

ai ,...,am > 1

(Таким образом, если бы имелась простая формула для hn{z), можно было бы упростить это громоздкое выражение.)

31. [MSi] Решите рекуррентное соотношение (16).

32. [М21] Чему равно среднее значение суммы всех полей SKIP в случайном дереве алгоритма "Патриция" с iV - 1 внутренним узлом?

33. [МЗО] Докажите, что (18) представляет собой решение рекуррентного соотношения (17). [Указание. Рассмотрите производящую функцию A{z) - Х]п>о o-nZ/n].]

34. [НМ4О] Назначение данного упражнения - поиск асимптотического поведения формулы (18).

a) Докажите, что при п > 2

n Uy2*-i-l 2ЯП-1) 712)

2<k<n J>1

b) Покажите, что слагаемые в правой части (а) приближенно равны 1/(е - 1) - 1/ж-(-1/2, где X = п/2; получающаяся при этом сумма отличается от первоначальной на 0(71").