Это делается с помощью теоремы 6.6. Напомним, что математическое ожидание 15*1 есть fj, = Нп In га, и по теореме 6.6 мы имеем

P{\s\ >(р +1)#4 = p{\s\ -ц> [знп} <с

= е{1-\пр)рНп e-(ln/3-l)/31nn =

= n-Qnp-i)p = = 1/га2

согласно определению числа fi.□

После такой подготовки вернёмся к деревьям поиска.

Теорема 13.6. Средняя высота случайного двоичного дерева поиска, построенного по га различным ключам, есть О (lgra).

Доказательство. Пусть к\, к2, , кп - случайная перестановка данных га ключей, Г - дерево, полученное последовательным добавлением этих ключей к пустому. Для фиксированного номера j и для произвольного числа t рассмотрим вероятность того, что глубина d(kj, Т) ключа kj не меньше t. Согласно следствию 13.4, в этом случае хотя бы одно из множеств Gj и Lj должно иметь размер не менее t/2. Таким образом,

P{d(k3,T) t}< P{\G3\ 2 t/2} + P{\L3\ 2 t/2}.(13.2)

Вначале рассмотрим P{G? t/2}. Оценим условную вероятность этого события при фиксированном множестве U = {t : 1 t j - 1 и ki > kj} (то есть когда известно, какие из элементов к\,..., kj i больше kj). Мы находимся в ситуации леммы 13.5 (все перестановки элементов с индексами из U равновероятны), и поэтому условная вероятность события \Gj\ t/2 при данном U равна вероятности того, что в случайной перестановке из и = \U\ элементов есть по крайней мере t/2 элементов, меньших всех предыдущих. С ростом и эта вероятность только растёт, так что все условные вероятности не превосходят P{\S\ t/2}, где S определено как в лемме 13.5. Поэтому и полная вероятность события {\Gj\ t/2} не превосходит P{\S\ t/2}. Аналогичным образом

Р{-*/2}Р{5*/2}

и, согласно неравенству (13.2),

P{d(k3,T)t}2P{\S\t/2}.

Взяв теперь t = 2(/3 + 1)Яп, где Нп = 1 + 1/2 + ... + 1/га (а /3 4,32 - корень уравнения (In/3 - 1)/3 = 2) и применив лемму 13.5, мы заключаем, что

Всего вершин в дереве не более га, поэтому вероятность того, что какая-то вершина будет иметь глубину 2(/3+ 1)Нп или больше, не более чем в га раз превосходит такую же вероятность для одной вершины, и потому не превосходит 2/га. Итак, с вероятностью по меньшей мере 1 - 2/га высота случайного дерева не превосходит 2(/3 + 1)Нп, и в любом случае она не больше га. Таким образом, математическое ожидание не превосходит (2(/3 + 1)Нп)(1 - 2/га) +

Упражнения

13.4-1 Приведите пример дерева поиска, в котором средняя (по всем вершинам) глубина вершины есть в (lgra), но высота дерева есть w(lgra). Насколько велика может быть высота дерева, если средняя глубина вершины есть в (lgra)?

13.4-2 Покажите, что при нашем понимании случайного двоичного дерева поиска не все упорядоченные деревья с данными га ключами равновероятны. (Указание: Рассмотрите случай га = 3.)

13.4-3* Для данной константы г 1 укажите константу t, для которой вероятность события «высота случайного двоичного дерева поиска не меньше tHn» меньше 1/гаг.

13.4-4* Рассмотрим алгоритм Randomized-Quicksort, применённый к последовательности из га чисел. Докажите, что для любой константы к > 0 существует такая константа с, что с вероятностью не менее 1 - с/пк алгоритм завершает работу за время era lg га.

13-1 Двоичные деревья поиска и равные ключи

Равные ключи - источник проблем при работе с деревьями по-

а. Какова асимптотика времени работы процедуры Tree-Insert при добавлении га одинаковых ключей в изначально пустое дерево?

P{d(kj, Т) > 2(/3 + 1)#4 «С 2Р{5 £ (/3 + 1)#4 2/га2.

□

Задачи

иска.

Задачи к главе 13

263

Причина тут в том, что при выборе в строках 5-7 и 11-13 мы в случае равенства всегда двигаемся направо по дереву. Будем рассматривать случай равенства отдельно. Оцените асимптотику времени добавления га равных ключей в пустое дерево при использовании трёх различных подходов:

б. Храним в вершине х флаг Ь[х], и выбираем левого или правого ребёнка в зависимости от значения Ь[х]. При этом флаг меняется при каждом посещении вершины, так что направления чередуются.

е. Храним элементы с равными ключами в одной вершине (с помощью списка) и добавляем элемент с уже встречавшимся ключом в этот список.

г. Направление движения выбираем случайно. (Каково будет время в худшем случае? Что вы можете сказать о математическом ожидании?)

13-2 Цифровые деревья

Рассмотрим две строки а = aai ... ар и Ь = bob\... bq, составленные из символов некоторого (упорядоченного) алфавита. Говорят, что строка а лексикографически меньше строки b (a is lexicographically less than b), если выполняется одно из двух условий:

1.Существует число j из 0.. min(p, q), при котором аг- = Ьг- для всех г = 0,1,..., j - 1 и aj < by

2.р < q и а{ = bi для всех г = 0,1,..., р.

Например, 10100 < 10110 согласно правилу 1 (при j = 3), а 10100 < 101000 согласно правилу 2. Такой порядок применяется в словарях.

Строение цифрового дерева (radix tree) видно из примера на рис. 13.6, где показано дерево, хранящее битовые строки 1011, 10, 011, 100 и 0. При поиске строки а = aai .. .ар мы на г-м шаге идём налево при о, = 0 и направо при аг- = 1. Пусть элементами множества S являются попарно различные битовые строки суммарной длины п. Покажите, как с помощью цифрового дерева отсортировать S в лексикографическом порядке за ©(га) действий. (Например, для множества рис. 13.6 результатом сортировки будет последовательность 0, 011,10,100,1011.)

13-3 Средняя глубина вершины в случайном двоичном дереве

В этой задаче мы докажем, что математическое ожидание средней глубины вершины в случайном двоичном дереве с га вершинами есть О (lgra). Хотя этот результат слабее, чем результат теоремы 13.6, доказательство устанавливает интересные аналогии между двоичными деревьями поиска и процедурой Randomized-Quicksort из раздела 8.3.