луча - N/In2 + NS{N) + 0{1). Здесь S{N) и S{N) - сложные функции, которыми можно пренебречь, поскольку их абсолютные значения никогда не превышают 10" (см. упр. 5.2.2-38 и 5.2.2-48).

Конечно же, перед нами стоит более трудная задача: обобщить результаты, полученные для бинарных лучей, на случай М-арных лучей. Мы опишем лишь стартовую точку исследований, помещая детальные инструкции в упражнения.

Пусть An - среднее число внутренних узлов в случайном М-арном луче поиска, который содержит N ключей. Тогда Ло = .4i = О и для N >2 имеем

An = 1+ Е (kk M-iAk+- + AkJ, (3)

поскольку iV! M~/ki \... км- представляет собой вероятность того, что ki ключей находятся в первом подлуче, ..., км - в М-м. Это соотношение может быть переписано как

= l + Mi-()(M-l)-=Afc npHiV>2 (4)

с использованием симметрии и суммирования по Агг,..., км- Аналогично, если через Cn обозначить общее среднее количество проверок битов, необходимое для поиска всех N ключей в луче, то Со = Ci = О и

CN = N + M-(yM-lf-Ck upmN>2- (5)

В упр. 17 показано, как работать с такого рода рекуррентными соотношениями, а в упр. 18-25 приводится соответствующая теория случайных лучей [с другой точки зрения анализ An был впервые проведен в работе L. R. Johnson, М. Н. McAndrew, IBM J. Res. and Devel. 8 (1964), 189-193, в связи с эквивалентным аппаратно-ориентированным алгоритмом сортировки].

Если теперь перейти к изучению деревьев цифрового поиска, то обнаружится, что формулы похожи, однако не настолько, чтобы можно было легко определить асимптотическое поведение. Например, если через Cn обозначить среднее суммарное количество проверок битов при поиске всех N ключей в М-арном дереве цифрового поиска, нетрудно вывести, как и ранее, что Со = Ci = О и

Cjv+i-iV + M- () (M-l)-=C;t npHiV>0. (6)

Это выражение практически идентично выражению (5), однако появления iV -I- 1 вместо 7V в левой части уравнения достаточно для того, чтобы коренным образом изменить характер рекуррентности, а потому использовавшиеся при изучении (5) методы становятся неприемлемыми.

Рассмотрим сначала бинарный цифровой поиск. На рис. 35 показано дерево цифрового поиска, соответствующее шестнадцати ключам из рис. 34, если они

вставляются в порядке, который использовался в примерах главы 5. Если будет необходимо определить среднее количество проверок битов при случайном успешном поиске, окажется, что это просто длина внутреннего пути дерева, деленная на N, так как для поиска узла на уровне I потребуется I проверок. Заметим, однако, что среднее число проверок битов при случайном неудачном гюиске не тпак просто связано с длиной внешнего пути дерева, поскольку неудачный поиск с большей вероятностью оканчивается во внешнем узле недалеко от корня. Так, вероятность достижения левой ветви узла 0075 на рис. 35 равна (при рассмотрении ключей с бесконечной точностью), а вероятность попадания в левую ветвь узла 0232 составляет лишь . Из-за этого деревья цифрового поиска при равномерном распределении ключей в целом лучше сбалансированы, чем бинарные деревья поиска из алгоритма 6.2.2Т.

(0075) Ш23) nQssS) 00652) (Тщ)

□ □ (0775)

(J277) (7575)

Рис. 35. Дерево случайного цифрового поиска, построенное по алгоритму D.

Для описания соответствующих характеристик деревьев цифрового поиска можно воспользоваться производящей функцией. Пусть на уровне I находится щ внутренних узлов. Рассмотрим производящую функцию a{z) = Ylii- Допустим, что производящая функция, соответствующая рис. 35, - a{z) = 1 + 2z + Az + bz + 4z*. Если на уровне I находится b[ внешних узлов и biz) = Yihz, то согласно упр. 6.2.1-25 получаем

b{z)l + {2z-l)a{z). (7)

Например, 1 -t- (2.г - 1)(1 -Ь 2z + Az + bz + \z) = Zz + z 4- 8.г Среднее количество проверок битов при случайном успешном поиске равно а(1)/а(1), так как а(1) - длина внутреннего пути дерева, а а(1) - количество внутренних узлов. Среднее количество проверок битов при случайном неудачном поиске составляет Ylilh2~ = \Ь{\) = о,{\), поскольку мы достигаем данного внешнего узла уровня I с вероятностью 2~К Количество сравнений совпадает с количеством проверок битов (плюс 1 при успешном завершении поиска). Например, на рис. 35 при успешном поиске будет выполнено в среднем 2 проверок битов и 3 сравнений, в то время как в случае неудачного поиска обе эти величины будут равны 3.

Обозначим через guiz) усредненную по всем деревьям с N узлами функцию a{z); другими словами, guiz) представляет собой сумму YlPт(тiz) по всем бинар-

ным деревьям цифрового поиска Т с N внутренними узлами, где ат{г) - производящая функция для внутренних узлов дерева Т, а рт - вероятность того, что Т образуется при вставке N случайных чисел согласно алгоритму D. Тогда среднее количество проверок битов будет равно 5дг(1)/Л в случае успешного и 5лг() - в случае неудачного поиска.

Можно вычислить дм{г) при помощи имитации процесса построения дерева следующим образом. Если a{z) представляет собой производящую функцию для дерева с N узлами, можно сформировать из него N + \ дерево методом вставки в позицию любого внешнего узла. Эта вставка производится в данный внешний узел уровня I с вероятностью 2~; следовательно, сумма производящих функций для N нового дерева, умноженная на вероятность ее появления, равна a{z) + b{\z) = a{z) \-l + {z - 1)0(2;). Усреднение по всем деревьям с N узлами дает

gN+i{z) = gN{z) + l + {z-l)gN{\z); 50(2) = 0. . (8)

С соответствующей производящей функцией для внешних узлов,

hN{z) = l + {2z-l)gN{z),

работать несколько легче в связи с тем, что (8) эквивалентно формуле

hN+i{z)=hN{z) + {2z-l)hN{\z); ho{z) = \. (9)

Многократно применяя это правило, находим, что

/ijv+i(г) = hN-,{z) + 2(22 - l)/ijv-i {\z) + (22 - \){z - l)/i;v-i

= hN-2{z) + 3(22 - 1)Л-2() +3(22 - 1)(2 - 1)Л;у-2(2) + (22-l)(2-l)(i2-l)/liV-2(H

И Т. Д. в результате имеем следующее:

hN{z) = Y,()l[i2-z-l); (10)

Например, 94(2) = 4 + 6(2 - 1) -Ь 4(2 - l){z - 1) + (2 - 1)(2- 1)(2 - 1). Эти формулы позволяют выразить искомые величины в виде сумм произведений:

cN = ff(i) = e(fc+2)n(2"-i); (12)

*;>0 j=l

= е (fc + i) П(2~ - 1) = +1 - (13)

Совершенно неочевидно, что эти формулы для Cjv удовлетворяют (6)!

К сожалению, данные выражения непригодны для вычислений или поиска асимптотических зависимостей, поскольку 2~ - 1 отрицательно; мы получим большие