Анализ вставки в сбалансированное дерево. [Те, кому математика кажется скучной и недостойной внимания, могут пропустить материал до (10).] Для выяснения времени работы алгоритма А необходимо ответить на следующие вопросы.

• Сколько сравнений будет выполнено во время поиска?

• Как далеко друг от друга будут находиться узлы S н Q? Иными словами, сколько корректировок будет проведено на шаге А6?

• Как часто будут вьшолняться однократные и двукратные повороты?

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

В первую очередь, нас может заинтересовать количество Bnh сбалансированных бинарных деревьев с п внутренними узлами и высотой h. Для небольших 1г из соотношений

Bo{z) = l, Biiz)z, Bh+iiz) = zB{z){Bh{z) + 2Bh-i{z)) (5)

нетрудно вычислить производящую функцию Bh{z) = 1]„>о-nft" (см. упр. 6). Таким образом,

B2{z) = 2z+z

Вз{г)= Az + &z + Az + z\

Bi{z) = 16г + 328 + AAz + + 80 + z,

и вообще, Bh{z) при /i > 3 имеет вид

2F+i-iFh+2-i 2+1~2Хл 12-+= + сложные члены + гг"" -- z:-, (6)

где Lk = Fk+\ + Fk-\. (Эта формула обобщает теорему А.) Общее количество сбалансированных деревьев высотой h равно Bh = Bh{l) и удовлетворяет рекуррентному соотношению

Bo=Bi=l, Bh+i=Bl + 2BhBh-u (7)

так что 2 = 3, 5з = 3 5, S4 = 32 5 7, В5 = 3 • 52 • 7 • 23; в общем случае

S. = <Mf-V..i,f°, (8)

где Ло = 1, Л1 = 3, А2 = 5, Лз = 7, Ai = 23, Аь = 347, ..., Л = Ah-iBh-2 + 2. Последовательности В и Ад растут очень быстро - как экспонента экспоненты; в упр. 7 показано, что существует действительное число в х 1.43687, такое, что

В, = [в"] - [в-\ + [в"-] -... + (-1)"[2°J. (9)

Если положить, что все В деревьев равновероятны, то, как показано в упр. 8, среднее число узлов в дереве высотой h равно

В1{1)/Вн{1) « (0.70118)2 - 1. (10)

Это означает, что высота сбалансированного дерева с N узлами обычно гораздо ближе к log2 N, чем к log N.

к сожалению, эти результаты в действительности не имеют отношения к алгоритму А, поскольку механизм построения деревьев делает одни из них существенно более вероятными, чем другие. Например, рассмотрим случай, когда Л = 7, при котором имеется 17 сбалансированных деревьев. Существует 7! - 5 040 возможных способов вставки ключей в дерево. При этом идеально сбалансированное "совершенное" дерево

получается 2 160 раз. Дерево же Фибоначчи

(12)

образуется только в 144 случаях, а похожее на него дерево

(13)

будет получено 216 раз. Заменив левые поддеревья в (12) и (13) произвольными сбалансированными деревьями с четырьмя узлами и использовав зеркальное отображение относительно вертикальной оси, получим 16 различных деревьев. Восемь из них, полученные из (12), встречаются по 144 раза, а полученные из (13) - по 216 раз. Как это ни странно, деревья (13) встречаются чаще, чем (12).

Тот факт, что идеально сбалансированные деревья образуются с такой высокой вероятностью, и формула (10), соответствующая случаю равных вероятностей, делают весьма правдоподобным заключение о том, что для среднего времени поиска по сбалансированному дереву необходимо требовать около Ig iV -Н с сравнений, где с мало. Р. В. Флойд (R. W. Floyd) обнаружил, что коэффициент при IgiV не равен в точности 1, поскольку тогда корень дерева должен быть очень близок к медиане, а корни поддеревьев - около четвертых частей. Однако однократные и двукратные повороты не могут просто оставить корень дерева в медиане. Эмпирические исследования показали, что реальное среднее количество сравнений, необходимых для вставки iV-ro элемента, примерно равно 1.01 IgA + 0.1 при не очень малых N.

Для изучения поведения фаз вставки и балансировки алгоритма А можно классифицировать внешние узлы сбалансированного дерева, как показано на рис. 23. Путь, ведущий вверх из внешнего узла, определяется последовательностью плюсов и минусов ("+" для правой ссылки и "-" для левой ссылки). Сначала записываем последовательность до тех пор, пока не будет достигнут первый узел с ненулевым

Рис. 23. Классификация, определяющая поведение алгоритма А после вставки.

фактором сбалансированности или (если такого узла нет) пока не будет достигнут корень. Затем добавляем А или В в соответствии с тем, будет ли новое дерево после вставки в данное место внутреннего узла сбалансированным. Так, путь вверх от [Т\ записывается как ++-В, что означает "правая ссылка, правая ссылка, левая ссылка, несбалансировано" Запись, оканчивающаяся на А, означает, что балансировка после вставки нового узла не требуется, для записи, завершающейся на ++В или -В, необходим однократный поворот, а для записи, завершающейся на +-В или -+В, - двукратный поворот. Если в пути встречается к звеньев, на шаге А6 корректируется ровно к-1 факторов сбалансированности. Таким образом, описанные последовательности предоставляют необходимую информацию о времени работы шагов А6-А10.

Эмпирические тесты со случайными числами в количестве 100 < N < 2000 дали приближенные вероятности для путей различных типов (табл. 1); очевидно, эти вероятности быстро сходятся к предельным значениям при iV - оо. В табл. 2 приведены точные значения вероятностей, соответствующих приведенным в табл. 1 (при N = 10), в предположении, что все 10! перестановок равновероятны. (Вероятность, показанная в табл. 1 как имеющая значение .143, в действительности равна