10. Например, каждое слово х ключа можно заменить словом ах mod m, где т - размер машинного слова, а а - случайный множитель, взаимно простой с т. Можно также порекомендовать величину, близкую к - 1)т (см. раздел 6.4). Гибкое распределение памяти при работе с деревьями может сделать такие методы более притягательными, чем схемы с хешированием.

11. Л - 2; однако это происходит с вероятностью \/{NN]) только при удалении

® N N-1 ... 2.

12. i(n + 1)(п + 2) удалений в доказательстве теоремы Н относятся к случаю 1, так что ответ - {N + l)/2N.

13. Да. Доказательство теоремы Н показывает, что если удалить к-й вставленный элемент, то для любого фиксированного к результат будет случайным. (Г. Д. Кнотт (Ph. D. thesis, Stanford, 1975) показал, что результат остается случайным после любой фиксированной последовательности вставок и удалений элементов (ki,..., kd)-)

14. Пусть NODE (Т) находится на уровне А; и пусть LLINK (Т) = Л, RLINK (Т) = Ri, LLINK (Ri) = R2, ..., LLINK(Rd) = Л, где Rd 7 Л и d > 1. Допустим, что в правом поддереве узла NODE(Ri) находится Hi, 1 < г < d, внутренних узлов. При наличии шага Dlj длина внутреннего пути уменьшается на А; + d + ni + • • + n; без этого шага она уменьшается на А; + d + п.

15. 11, 13, 25, 11, 12. (Еслиау является наименьшим, средним, наибольшим из {01,02,03}, после удаления дерево \ будет получено (4, 2, 3) х 4 раз.)

16. Да; коммутативной будет даже операция удаления из перестановок, определенная в доказательстве теоремы Н (если пренебречь перенумерацией). При наличии элемента между элементами X к Y коммутативность удаления очевидна, поскольку на операцию удаления влияет только относительное расположение элементов Х, У и их наследников и удаления X w.Y пе взаимодействуют между собой. С другой стороны, если У является преемником X kY - больший елемент, то оба порядка удаления просто удаляют элементы X w.Y. Если У - преемник X, & Z - преемник У, оба удаления приведут к замещению первого встреченного элемента X, У или Z элементом Z и к удалению второго и третьего из встретившихся элементов из перестановки.

18. Воспользуйтесь упр. 1.2.7-14.

19. 2Ялг - 1 - 2X;f=i(fc - if/kN = 2Ялг - 1 - 2/(9 + 0(iV-*). (Распределение Парето 6.1-(13) приводит к подобному асимптотическому результату с поправкой Oin" logn).)

20. Да, конечно. Предположим, что Ki < • < Kn, так что дерево, построенное при помощи алгоритмах, вырожденное. Если, например, р*, = (l + ((iV+l)/2-A:)e)/iV, среднее число сравнений равно {N+l)/2 - {N - 1)е/12, в то время как оптимальное дерево требует менее [IgAl сравнений.

21 5> 1 20 I- (Большинство углов равны 30°, 60° или 90°.) 22. При d = 2 это очевидно; при d > 2 имеем r[i, < г[г+1, j - 1] < r[i+l, j]. 23.

(Увеличение веса первого узла в конце концов приведет к его хгеремещению в корневое положение. Это наводит на мысль о сложности динамического поддержания оптимальности дерева.)

24. Пусть с означает цену дерева, полученного посредством удаления п-го узла из оптимального дерева. Тогда с(0, п-1) < с < с(0, п) - qn-i, поскольку операция удаления всегда перемещает п-1 на один уровень вверх. Аналогично с(0, п) < с(0, п-1) -I- Qn-i, так как при предлагаемой замене цена дерева равна последнему выражению, откуда следует, что

С(0, п-1) = с = С(0, П) - Qn-l.

25. (а) Предположим, что А<ВиВ<С,и пусть а е А, b е В, с е С, с < а. Если с < Ь, то се В; следовательно, с е А и а е В; значит, а еС. Если с > 6, то а £ В; следовательно, а е С я с е В; значит, с е А. (Ь) Это легко доказать самостоятельно.

26. Цена любого дерева имеет вид у + 1х, где у > О - некоторое действительное число, а I - целое, большее 0. Минимум конечного числа таких функций (взятых по всем деревьям) всегда имеет описанный вид.

27. (а) Из ответа к упр. 24 (в частности, из того, что с = с(0, п - 1)) вытекает, что Л(0,п-1) = Д(0,п)\{п}.

(Ь) Если 1 = 1, результат в указании тривиален. В противном случае обозначим пути к [п] как

И [So), [Si)

Поскольку г = Го > «о = « и Г( < Si = п, можно найти уровень А; > О, такой, что гк > Sk а Гк+1 < Sk+i- По индукции имеем Гк+i £ Щгк,п), Sk+i € R{sk,n) и R{sk,n) < R{rk,n). Значит, Гк+1 е R(sk,n) и Sk+i £ R(rk,n); отсюда следует результат, приведенный в указании.

Теперь для доказательства того, что R < Rh, положим, что г е R, s е Rh, s < г, и рассмотрим оптимальные деревья, показанные для х = Xh- Получим, что Z > Zh, и можно предположить, что I = Ih- Для доказательства соотношения Rh < Rh+i положим, что г е Rh, S G Rh+ij s < г, и рассмотрим оптимальные деревья, показанные для х = Xh+i-Получим, что I <lh, и можно предположить, что 1 = Ih-

29. Это вырожденное дерево (см. упр. 5) с YOU на вершине дерева и THE внизу, которое требует в среднем 19.158 сравнений.

Дуглас А. Гамильтон (Douglas А. Hamilton) доказал, что наихудшим деревом всегда является некоторое вырожденное дерево. Таким образом, существует 0(п)-алгоритм получения наихудших бинарных деревьев поиска.

30. Cm.R. L. Wessner, Information Processing Letters 4 (1976), 90-94; F. F. Yao, SIAJVf J. Algebraic and Discrete Metliods 3 (1982), 532-540.

31. Cm. Acta Informatica 1 (1972), 307-310.

32. Когда M достаточно велико, оптимальное дерево должно иметь указанный вид и минимальная цена должна быть в М раз больше минимальной длины внешнего пути плюс решение сформулированной проблемы.

(Примечание. Статья Весснера, указанная в ответе к упр. 30, поясняет, как найти оптимальное бинарное дерево поиска высоты < L. Для частного случая pi = • • = р„ = О решение было получено Т. Ч. Ху (Т. С. Ни) и К. Ч. Таном (К. С. Tan) (MRC Report 1111 (Univ. of Wisconsin, 1970)). A. M. Гарсия (A. M. Garsia) и M. Л. Воч (M. L. Wachs) доказали, что в этом случае все внешние узлы окажутся максимум на двух уровнях, если mink=i{qk-i + qk) > inaxEt=o Як, а также представили алгоритм, требующий только 0(п) шагов для поиска оптимального двухуровневого дерева).

33. Решение поставленной задачи можно найти в А. Itai, SICOMP 5 (1976), 9-18; альтернативные варианты рассмотрены в работе D. Spuler, Acta Informatica 31 (1994), 729-740.

34. Согласно аппроксимации Стирлинга при pi .. .рп О это значение равно 2-.....рп)

х(27гЛГ)(-">/2(р.. .p„)-V2(i + Oa/N)).

35. Минимальное значение правой части неравенства, равное 1-р+Я(р, 1-р), достигается при 2ж = (1 - р)/р. Однако согласно (20) при к = 2 Н(р, д, г) < 1 - р + Я(р, 1 - р).

36. Сначала докажем утверждение из указания, принадлежащее Дженсену (Jensen) (Acta Math. 30 (1906), 175-193). Если / вогнута, следовательно, функция д{р) = f{px + (1 -р)у) " Pfi} " (1 " P)f{y) вогнута: кроме того, она удовлетворяет условию д(0) = д(1) = 0. Если для некоторого О < р < 1 д{р) < О, то должны существовать ро < р, для которого д(ро) < О, и pi > р, для которого g(pi) > О согласно теореме о среднем. Однако это противоречит условию вогнутости. Следовательно, /(рж + (1 - р)у) > pf{x) + (1 - p)f(y) при О < р < 1, что геометрически очевидно. Теперь по индукции можно доказать, что /(pia;i Н-----1- РпХп) > pif{x\) Н-----h Pnfix„), поскольку /(pizi Н-----h рпХ„) > pi/(zi) +

----hPn-2f{Xn-2) + (Pn-1 +Рп)/((Рп-1Жп-1 +РпЖп)/(рп-1 + Рп)) ПрИ П > 2.

Согласно лемме Е имеем

H{XY) = Н(Х) + Ylp.Hira/pi,r,n/Pi); 1=1

и последняя сумма i Pifirij/Pi) < EJ=i fiET=i ij) = H{Y), где функция /(ж) =

a;lg(l/z) вогнута.

37. Согласно п. (а) упр. 3.3.2-26 имеем Pr(Pi > s) = {1 - s)"~. Отсюда

ЕЯ(Р1Р„) = пЕPi lg(l/Pi) = п /\l -«)"- rf(5 \g{l/s)) = -{A + В)/ In 2,

где A = n/o(l-s)"-rfs = l и

В = nj\l - s)--\nsds = fj() (-!)*/(! - In.)

согласно упр. 1.2.7-13. Таким образом, ответ равен (Я - 1)/ In 2. (Это значение Ig п + (7 - 1)/ In 2 + 0(п~) очень близко к максимальной энтропии Я(,..., ) = Ign, и Я(р1,... ,рп) с высокой вероятностью равна n(logn).)

38. Если Sk-\ = Sk, имеем qk-\ = Рк = Як = О (см. (26)). Постройте дерево для п-1 вероятности (pi,... ,рА;-1,р*+1,... ,p„;qo, • •. ,qk-i,qk+i, ,qn) и замените лист к-11 двухлистовым поддеревом.

39. Можно провести доказательство так же, как и в теореме М, если О < wi < W2 < <

WnH Sk = Ш1 Ч-----hwk, поскольку из Wk >2~* следует, что sk-i+2~* < Sk < Sk+i - 2~ при

упорядоченных весах. Следовательно, имеем \ак\ < 1 + lg{l/wk)- (Этот результат вместе с соответствующей нижней границей H{wi,... ,w„) составлял теорему 9 в оригинальной статье Шеннона 1948 года.)

40. При к = S + 3 указанная перестановка изменяет цену с qk~il + qki + qk-2lk-2 до qk-2l + qk-il + qklk-2, так что изменение равно {qk-2 - ?*)( - it-2); эта величина отрицательна при I < 1к-2, поскольку qk-2 > qk-

Точно так же при к > s + i перестановка изменяет цену на величину

= qs + l{l - Is + l) + qs+2{l - ls+2) + qs+sih+l - ls+з) + • • + qk-2{lk-i - lk-2)

+ qk-i{lk-3 - I) +qk{lk-2 - l). Мы имеем qs+i > qs+з, q3+2 > qs+i, • • •, qk-2 > qk- Таким образом, находим S < {qk-2 - qk){l - lk-2) + {qk-3 - qk-i){l - lk-з) < 0;

= -Hn