корневого нуля и выбирается наименьший "источник" на каждом шаге. Из этой последовательности можно восстановить oi... Оп.

с) Сначала построим вспомогательное дерево, в котором родительский узел узла к является первым элементом, большим к, следующим за ним в перестановке qi.. .qn, если такого элемента нет, родительский узел становится узлом 0. Затем создадим копию вспомогательного дерева и повторно пометим ненулевые узлы нового дерева в прямом порядке при помощи следующей процедуры: если метка текущего узла во вспомогательном дереве была к, замените его текущую метку меткой, которая в текущий момент является (1 +pk - 0)ь)-й наименьшей в его поддереве. Например:

Вспомогательное дерево Окончательное дерево

75V-. 4 2 8

4 2 9 7

Для обращения процедуры можно перестроить вспомогательное дерево, выполняя в прямом порядке обмен меток каждого узла с наибольшей меткой в его поддереве.

Конструкции (а) и (Ь) сильно связаны, но конструкция (с) несколько отличается от них. Она имеет интересное свойство, заключающееся в том, что сумма перестановок автомобилей из их предпочтительных положений равна числу инверсий в дереве - числу пар меток о > Ь, где а является предком Ь. Эта связь между последовательностью парковок и инверсиями дерева была впервые открыта в работе G. Kreweras, Periodica Math. Hung. 11 (1980), 309-320. Тот факт, что инверсии деревьев имеют прямое отношение к связным графам [Mallows and Riordan, Buii. Amer. JVfath. Soc. 74 (1968), 92-94], позволяет сделать вывод о том, что сумма С), взятая 1Ю всем последовательностям парковки, где D{p) = (pi - oi)-)-••• -)- (pn - On), равна общему количеству связных графов с п + к ребрами на множестве помеченных вершин {0,1,...,п}. [См. формулы (2.11), (3.5) и (8.13) в статье Janson, Luczak, Knuth, and Pittel, Random Struct. &: Alg. 4 (1993), 233-358.]

32. Будем считать индексы циклическими, т. е. см = со, см+i = ci и т. д. При Cj = bj + Cj+i - 1 для всех j решений не существует, поскольку сумма по всем j дает E*j - Xbj-f-Ecj -М < Следовательно, каждое решение имеет М-] bj значений j, таких, что bj = Cj+i = 0. Если (cq, ... ,Cm i) представляет собой другое решение, то должно выполниться условие Cj+i > О для хотя бы одного такого j; но отсюда вытекает противоречие:

cj+2 > Cj+2, > Cj+3, Решение может быть найдено путем определения см-i, см-2,

..., если предположить, что со = 0; тогда, если со > О, достаточно переопределять см-i, см-2, .. •, пока дальнейшие изменения не станут ненужными.

33. Отдельные вероятности не являются независимыми, поскольку не было принято во внимание условие Ьо +bi + + Ьм-1 = N; это отклонение позволяет сумме J2 bj иметь любое данное неотрицательное значение с ненулевой вероятностью. Соотношения (46) не являются абсолютно корректными; из них следует, например, что qk положительно при всех к, а это противоречит тому факту, что Cj никогда не превосходит N - 1.

Гастон Тонне (Gaston Gonnet) и Дж. Мунро (J. Munro) [J. Algorithms 5 (1984), 451-470] обнаружили интересный путь вывода точного результата из аргумента, который привел к (51), введя полезную операцию, названную преобразованием Пуассона последовательности {Атп). МЫ имеем е"""* Атп(т2)Уп! = Eit** тогда и только тогда, когда

Атп = iCfcOfc

34. (а) Существует () способов выбора множества j, таких, что о , имеет определенное значение, и [М - \)~ способов присвоения значения другим а. Таким образом.

Piv. = ()(M-l)-VM.

(b) Pn{z) = B(z) в (50). (с) Рассмотрим общее количество проб для поиска всех ключей, не считая получения указателя на заголовок списка на рис. 38 (при использовании такой таблицы). Список длиной к позволяет добавить к общей сумме (*2 ) проб; следовательно,

c;v = +)p;v./7v = (M/7v)(ip;;(i)+ р;(1)).

(d) В случае (i) для списка длиной к требуется к проб (не считая получения заголовка списка), в то время как в случае (ii) требуется к + 5ko проб. Значит, в случае (ii) получим Cn = E(fc + 5ko)PNk = PAr(l) + Рлг(О) = N/M + (1 - IjMf « a + e"", a в случае (i) - просто cn = N/M = Q. В случае (iii) применима формула MCn = М - N + NCn, поскольку М - N хеш-адресов будут указывать на пустые позиции в таблице, в то время как N хеш-адресов приведут к поиску до конца некоторого списка из точки внутри него; это да«т (18).

35. (i) E(l + 5-(fc + l)~)Pfc = l + JV/(2M)-M(l-(l-l/M)+)/(+l) ~ 1 + 5«-(1-е °)/а. (ii) Добавьте YlkoPNk = (1 - 1/М) к е"" к результату (i). (iii) Если неудачный поиск начинается с j-ro элемента списка длиной к, данный ключ имеет случайный порядок по отношению к другим к элементам, так что ожидаемая длина поиска составляет (j • 1 -Ь 2 -Ь • + {k + l-j) + {k + l-j))/(k + l). Суммирование по j дает MCjy = М - N+М Yl{k+9k + 2k)PNk/{(>k + 6) = М-N + M{\N{N ~l)/M + IN/M-1 + {M/(N + l)){l-(\-l/M)+)); следовательно, Cn \a + + {I - e~°)/a.

36. (i) N/M - N/M\ (ii) E(4o + kfPNk = E(<Jfco + k)PNk = Pn(0) + PA(l) + Pn(1)-Вычитание [CnY дает ответ (М - 1)N/M + {1 - 1/М)(1 - 2N/M - (1 - 1/М)) « Q --е"*(1 - 2а- е"") < 1 - е~ - е" = 0.4968. [Для структур данных (iii) требуется более сложный анализ, подобный приведенному в упр. 37.]

37. Пусть Sn - среднее значение (С - 1) и пусть все МN выборов хеш-последовательности и ключей равновероятны. Тогда

MNSn = I ( км) ~ ~ ~ "

= \MY{l){M-lf-k{k-\)(k-l)

= \mN{N - 1){N - 2)J2{-l)iM - If-"

+iM7V(7v-i)x:(:)(M-i)--=

= ImN{N - l)(N - 2)M- + \mN(N - 1)M-.

Дисперсия при этом равна Sn - {(N - l)/2Mf = [N - \)(N + 6M - 5)/12M « + и"-В CJVfath §8.5 рассмотрена интересная связь между общей дисперсией, вычисленной здесь, и двумя другими видами дисперсии: дисперсией (по случайным хеш-таблицам) среднего числа проб (по всем наличным элементам) и средней (по случайным хеш-таблицам) дисперсией числа проб (по всем наличным элементам). Общая дисперсия всегда является

суммой двух других; и в этом случае дисперсия среднего числа проб составляет {M-1){N- 1)/(2M7V).

38. Среднее число проб составляет J2 Nk {2Hk+i-2+Sko) при неудачном поиске и {M/N) х X Е PNkk{2{l + l/k)Hk - 3) - при успешном согласно формулам 6.2.2-(5) и 6.2.2-(6). Эти суммы равны 2f(N) + 2М(1 - (1 - l/M)+)/(iV + 1) + (1 - - 2 и 2{M/N)f{N) + 2/(7V-l) + 2M(l-(l-l/M))/7V-3 соответственно, где f{N) = "£.РкНк. В упр. 5.2.1-40 говорится о том, что f{N) = Ina + 7 + £i(a) + 0{М~) при TV = аМ, М -> оо.

[Хеширование с деревьями было впервые предложено в работе Р. F. Windley, Сотр. J. 3 (1960), 84-88. Анализ в предыдущем параграфе показывает, что такой метод не настолько лучше обычного метода цепочек, чтобы оправдать введение лишних полей ссылок - списки для этого слишком коротки. Более того, когда М мало, хеширование с деревьями не настолько лучше обычного пЬиска по дереву, чтобы оправдать затраты времени на хеширование.]

39. (Этот подход к анализу алгоритма С был предложен Дж. С. Виттером (J. S. Vitter).) Имеем слг+1(А;) = {М-к)см{к) + {к - 1)см(к - 1) при > 2 и, кроме того, ксм(к) = TVM. Следовательно,

к>2 к>2

= Е(( + 2) (2 ) + (fc) = (Л + 2)5n + TVJW-.

В результате получаем Sn = {N - l)iW"- + (TV - 2)М-(М + 2) + • • + М{М + 2)" = i(M(iW + 2) - M - 2iVM).

Рассмотрим общее число проб в случае неудачного поиска, просуммированное по всем М значениям функции h(K); каждый список длиной к вносит вклад k + Sko + (2) в общую сумму, следовательно, MCjv = М"*" + Sn-

40. Определим Un так же, как и 5лг в упр. 39, но с (2), замененным на (з)- Найдем, что Un+1 ={М + 3)Un + 5лг + TVM, значит,

Un = {М(М - 6TV) - 9М{М + 2) + 8М(М + 3)).

Дисперсия равна 2Un/M* +Cn - (Cn), что примерно составляет

1„2 , /1 5\ 2а , 4 .За J 4а

144 12° i° -r(l° s> +9

при TV = аМ, М сх). При а = 1 эта величина ргшна приблизительно 4.50, так что стандартное отклонение ограничено величиной 2.12.

41. Пусть Vn - средняя длина блока занятых ячеек на "верхнем" конце таблицы. Вероятность того, что длина блока равна fc, составляет ANk{M - 1 - к)/М, где Адг - число хеш-последовательностей (35), таких, что алгоритм С оставляет первые N - к и последние к ячеек занятыми, и таких, что подпоследовательность 12... TV-fc оказывается расположенной в порядке возрастания. Вследствие этого

MVn = Ек kANk{M - 1 - к) = TW-+i -Ек(М- k)ANk{M - 1 - fc)

= TW+i - (TW - TV) ANk{M - fc) = -{M- N){M + 1).

Теперь Tn = {N/M){1 + Vn - To - - Tn-i), поскольку To + • + Tn-i представляет собой среднее число предыдущих операций уменьшения R, а TV/Tl<f - вероятность его уменьшения на текущем шаге. Решение этого рекуррентного соотношения - Tn = (N/M)(l + l/M). (Такая простая формула заслуживает более простого доказательства!)