b) Найдите простую формулу для производящей функции G„{z) = Р„*2* и используйте ее для выражения Р„ через числа Стирлинга.

c) Чему равна дисперсия этого распределения?

7. [М25] (С. Р. Арора (S. R. Агога) и В. Т. Дент (W. Т. Dent).) Чему равно среднее количество сравнений, необходимое алгоритму Т для поиска т-го наибольшего элемента по его ключу после вставки п элементов в случайном порядке в первоначально пустое дерево?

8. [M5S] Пусть р(п, к) - вероятность того, что полная длина внутреннего пути дерева, построенного по алгоритму Т из п случайным образом упорядоченных ключей, равна к (длина внутреннего пути дерева равна числу сравнений, производимых при сортировке путем вставки в дерево в процессе построения дерева).

a) Найдите рекуррентное соотношение, которое определяет соответствующую производящую функцию.

b) Вычислите дисперсию такого распределения. (При выполнении этого упражнения могут оказаться полезными некоторые упражнения из раздела 1.2.7.)

9. [41] Мы доказали, что поиск по дереву и вставка требуют порядка 21n7V сравнений при вставке ключей в случайном порядке. Однако на практике порядок вставки может быть не случайным. Проведите эмпирические исследования, чтобы выяснить, насколько хорошо вставка в дерево подходит для работы с реальными таблицами символов компилятора или ассемблера. Получится ли в результате вставки идентификаторов большой программы хорошо сбалансированное дерево поиска?

► 10. [22] (Р. В. Флойд (R. W. Floyd).) Предположим, нас не интересует порядок ключей в дереве поиска; однако ожидается, что данные будут вводиться в неслучайном порядке. Обдумайте методы, которые позволят сохранить эффективность поиска, делая входные данные кажущимися случайными.

11. [20] Чему равно максимальное число присвоений S 4- LLINK (R), выполняемых на шаге D3 при удалении узла из дерева размером N?

12. [М22] Как часто в среднем происходит переход от шага D1 к шагу D4 при случайном удалении из случайного дерева, состоящего из N элементов? (См. доказательство теоремы Н.)

► 13. [М23] Если корень случайного дерева удаляется с помощью алгоритма D, останется ли получившееся в результате дерево случайным?

► 14. [22] Докажите, что длина пути дерева, построенного согласно алгоритму D с дополнительным шагом Dl, никогда не превышает длину пути дерева, построенного без этого шага. В каком случае дополнительный шаг Dl уменьшает длину пути?

15. [23] Пусть 01о2о3о4 - перестановка множества {1,2,3,4} и пусть j = 1, 2 или 3. Возьмем одноэлементное дерево с ключом oi, выполним вставку элементов аг, оз по алгоритму Т, удалим Oj по алгоритму D и вставим 04 согласно алгоритму Т. Сколько деревьев из 4! х 3 возможных будут иметь вид I, II, III, IV и V соответственно (согласно классификации (13))?

► 16. [25] Является ли операция удаления коммутативной? Иначе говоря, получится ли одно и то же дерево, если с помощью алгоритма D будет сначала удален узел А, а затем - Y и сначала удален узел Y, а затем - X?

17. [25] Покажите, что если в алгоритме D полностью заменить "левое" "правым" то его легко можно будет распрястранить на удаление данного узла из правопрошитого дерева с сохранением необходимых нитей (см. упр. 2).

18. [М21] Покажите, что, используя закон Зипфа, можно получить (12).

19. [М23] Чему равно приближенное среднее количество сравнений (И), если вероятности входных данных подчиняются закону "80-20" определенному в 6.1-(11)?

20. [М20] Предположим, что мы вставляем ключи в дерево в порядке уменьшения их частот Pl > Р2 > > Рп- Не может ли такое дерево оказаться существенно хуже оптимального?

21. [М20] Если р, q, г - случайно выбранные вероятности, такие, что p + q + r = 1, чему равны вероятности того, что деревья I, П, П1, IV, V из (13) оптимальны? (Рассмотрите соотношения площадей соответствующих областей на рис. 14.)

22. [М20] Докажите, что при выполнении шага К4 алгоритма К г[г, j-1] никогда не превышает г[г-1-1, j].

► 23. [М23] Найдите оптимальное бинарное дерево поиска для случая N = 40 с весами Pl = 9, р2 = рз = • • • = Р40 = 1, qo = qi = - - - = 540 = О (не используя компьютер).

24. [Мй5] Пусть р„ = 5„ = О, а все остальные веса неотрицательны. Докажите, что оптимальное дерево для (pi,..., р„; qo,... ,q„) может быть получено посредством замены

в любом оптимальном для (pi,... ,pn-i; qo,-- - ,qn-i) дереве.

25. [МЙО] Пусть А ш В - непустые множества действительных чисел. Определим, что А < В, если выполняется следующее:

из (о 6 Л, 6 6 В и 6 < о) следует (о 6 В и 6 6 Л).

a) Докажите, что это соотношение транзитивно на непустых множествах.

b) Докажите или опровергните, что А < В тогда и только тогда, когда А < AU В < В.

26. [М22] Пусть (pi,... ,Рп; до,...,qn) - неотрицательные веса ирп+Яп = х. Докажите, что при X, изменяющемся от О до оо, и при постоянных (pi,... ,Pn-i; qo,-- - ,qn-i) цена c(0, n) оптимального бинарного дерева поиска является выпуклой, непрерывной, кусочно-линейной функцией X с целыми угловыми коэффициентами. Другими словами, докажите, что существуют положительные целые числа lo > h > • > im и действительные константы О = шо < a:i <•••< < Хт+1 - ОО И уо <у1 < Ут, такие, что с(0, n) = yh+ IhX при Xh <х < Xh+1, о <h <т.

27. [МЗЗ] Цель данного упражнения состоит в доказательстве того, что множество корней R{i,j) оптимальных бинарных деревьев удовлетворяет соотношению

R{i,j-l) < R(i,j) < Rii+l,j) для j - г > 2,

где отношение < введено в упр. 25 при неотрицательных весах (pi,... ,р„; qo,..-, qn). Доказательство проводится по индукции по j - г; наша задача состоит в том, чтобы доказать, что Д(0, п-1) < R{0,n) при п > 2 в предположении справедливости соотношения при j - i < п. (В Силу симметрии отсюда следует, что R(0, п) < R{l,n).)

a) Докажите, что Д(0, п - 1) < Д(0, п) при р„ = д„ = О (см. упр. 24).

b) Пусть Рп + qn = X. Воспользуемся обозначениями упр. 26. Пусть Rh - множество оптимальных корней R{0,n) при < х < Xh+i, а Rl - множество оптимальных корней для X ~ Xh. Докажите, что

Rq Ro 1 1 * Rm Rm.

Отсюда из п. (а) и упр. 25 следует, что Л(0, п-1) < R{0,n) для всех х. (Указание. Рассмотрите случай х = Xh ч предположите, что деревья

t(0,r-l) t(r,n) и «(0,s-l) t{s,n) [гГ] на уровне г на уровне I

оптимальны с s < г и I > I. Воспользуйтесь предположением индукции для доказательства того, что существует оптимальное дерево с корнем (г\ у которого [п\ располагается на уровне I, а также оптимальное дерево с корнем (Т) и узлом [п] на уровне /.)

28. [24] Используйте некоторый макроязык для определения макроса "оптимальный бинарный поиск", параметром которого является вложенная спецификация оптимального бинарного дерева.

29. [0] Каково Hauxydiu.ee бинарное дерево поиска для 31 наиболее употребительного английского слова (эти слова представлены вместе с частотами их появления на рис. 12)?

30. [М,?] Докажите, что цена оптимальных бинарных деревьев поиска удовлетворяет "квадрантному неравенству" с(г, j) - с(г, > c(i+l,j) - с(г+1, j-1) при j >г + 2.

31. [М35] (К. Ч. Тан (К. С. Tan).) Докажите, что среди всех распределений вероятностей

(pi,..., р„; до,... ,qn) (pi Н-----h Рп + 9о Н-----Н 9п = 1) дерево с минимальной ценой наиболее

дорого при р. = О для всех г, Qj = О для всех четных j и qj - 1/Гп/2] для всех нечетных j.

► 32. [М25] Пусть n-bl = 2"+к, где О < А; < 2™. Существует ровно (") бинарных деревьев, в которых все внешние узлы расположены на уровнях тшт+1. Покажите, что среди всех этих деревьев мы получим одно с минимальной ценой для весов (pi,... ,Pn;qo,. . ,qn), если применим алгоритм К к весам (pi,... ,р„; M+qo,..., M+qn) при достаточно большом М.

33. [М41] Для нахождения бинарного дерева поиска, минимизирующего время работы программы Т, следует минимизировать величину 7С -I- Cl, а не просто количество сравнений С. Разработайте алгоритм для поиска оптимальных бинарных деревьев поиска, когда левые и правые ветви дерева имеют разные цены. (В случае, когда "правая" цена в два раза больше "левой" а частоты всех узлов одинаковы, оптимальными становятся деревья Фибоначчи [см. L. Е. Stanfel, JACM 17 (1970), 508-517].) На машинах, которые не могут получать результат сравнения из трех возможных (больше, меньше, равно), программа, реализующая алгоритм Т, вынуждена производить на шаге Т2 два сравнения - меньше и больше. Б. Шейл (В. Slieil) и В. Р. Пратт (V. R. Pratt) обнаружили, что эти сравнения не требуют одного и того же ключа и может оказаться предпочтительным бинарное дерево, внутренние узлы которого определяют либо проверку равенства, либо проверку "меньше, чем" но не обе. Такая ситуация может оказаться интересной альтернативой поставленной задаче.

34. [НМ21] Покажите, что асимптотическое значение полиномиального коэффициента

ipiN, P2N, p„n) при N -¥ оо стремится к энтропии H(pi,p2, • • • ,Рп)-

35. [НМ22] Завершите доказательство теоремы В, доказав справедливость неравенства (24).

► 36. [НМ25] (Клод Шеннон (Claude Shannon).) Пусть X п Y - случайные величины, принимающие конечные множества значений {xi,... ,Хт} и {j/i,... ,у„}. Введем обозначения Pi = Рг(А = Xi), qj = Рт(У = yj), Tij = Рг(Х = Xi и Y = yj); кроме того, положим, что Н(Х) = H(pi,. . ,pm) и H(Y) = H(qi,. .,qn) представляют собой энтропии X и Y