умножив (2) на {п- мы получим

g подставив (3) в (1), получим

=-;f((n-+ 2 -1). (4.56>

Оказывается, что Сп можно представить в нерекурсивной, закрытой форме с помощью гармонической функции

= 1 + Т + Т + --- + Г'

п+1 (4.57)

[{Недоверчивый читатель может проверить, что (4.57) удовлетворяет рекурсивному соотношению (4.56).]

Из формулы Эйлера (используя константу у = 0.577)

= у-Ь ln(n) + -j-f ...

ны получаем для больших п соотношение

о„ 2 [In (п) + у] - 3 = 2 In (п) - с.

Поскольку средняя длина пути в идеально сбалансированном дереве приблизительно равна

< = log(n)-I, (4.58)

опуская постоянное слагаемое, которое становится незначительным для больших п, мы получаем

Игп1 = 2.1п 2-=1.386. (4.59)

Что дает нам результат этого анализа (4.59)? Из него можем сделать вывод, что, стараясь всегда строить иде- ibHo сбалансированное дерево вместо случайного дерева. Получаемого программой 4.4, мы могли бы, по-прежнему Предполагая, что все ключи появляются с равной вероятностью, ожидать среднего выигрыша в длине пути поиска не лее 39 7о. Ударение следует сделать на слове среднего.-!, скольку, разумеется, выигрыш может быть намного больше

Неудачном случае, когда формируемое дерево полностью ,%ождается в список, но вероятность этого случая невелика №сли все перестановки п ключей равновероятны). В связи

С ЭТИМ следует отметить, что ожидаемая средняя длина nv-в случайном дереве растет тоже строго логарифмиче по отношению к числу его узлов, несмотря на то что в ху шем случае длина пути увеличивается в линейной. здв^ симости.

Цифра 39% накладывает ограничения.на объём доп.олнц тельных затрат, которые имеет смысл вкладывать в какую либо доперсстройку структуры дерева при включении щ^, ментов. Разумеется, отношение г между частотой обращени}) (поиска) к узлам (информации) и частотой включений сущ^, ственно влияет на границу, до достижения которой эти за , траты выгодны. Чем больше этот коэффициент, тем больШе выигрыш от такой процедуры перестройки. Цифра 39 % дц. статочно низка, и в большинстве случаев выигрыш от такой процедуры по сравнению с простым алгоритмом включения в дерево не оправдывает затрат, если только число узлов и соотношение между поиском и включением не оказываются велики (или если можно не опасаться худшего случая).

4.4.6. Сбалансированные деревья

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

Одно такое определение сбалансированности было дано Адельсоном-Вельским и Ландисом [4.1]. Критерий сбалансированности следующий:

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

Деревья, удовлетворяющие этому условию, часто называют АВЛ-деревьями (по фамилиям их изобретателей). будем называть их просто сбалансированными деревья! так как их критерий сбалансированности оказывается наиболее подходящим. (Отметим, что все идеально сбалансированные деревья являются также АВЛ-сбалансированными.)

Это определение не только простое, но также приводи к легко выполнимой балансировке, а средняя длина поИсК остается практически такой же, как у идеально сбалансир .: ванного дерева.

Со сбалансированными деревьями можно выполнять сле-у}оШие операции за O(logrt) единицу времени даже в худ-> случае:

1 1айти узел с данным ключом, л' Включить узел с данным ключом. J Удалить узел с данным ключом.

дто является прямым следствием теоремы, доказанной ддельсоном-Вельским и Ландисом, которая утверждает, что сбалансированное дерево никогда не будет более чем на 45 % рыше соответствующего идеально сбалансированного дерева независимо от количества узлов. Если мы обозначим высоту сбалансированного дерева с п узлами через Ль (и), то

log{n+IXЛь(n)< 1.4404 - log(п +2)-0.328 (4.60)

Разумеется, оптимум достигается, если дерево идеально сбалансировано, при n = 2*-1. Но какова структура наихуд-ш'его'АВЛ-сбалансйрованного дерева?

Чтобы найти максимальную высоту h всех сбалансированных деревьев с п узлами, возьмем фиксированное h и попробуем построить сбалансированное дерево с минимальным количеством узлов. Такая стратегия рекомендуется, поскольку, как и в случае минимального h, это значение может быть достигнуто только при некоторых, определенных значениях п.

Рис. 4.30. Деревья Фибоначчи высотой 2, 3 и 4.

Обозначим такое дерево с высотой h через Т^. Очевидно, что о-пустое дерево, а -дерево с одним узлом. Чтобы построить дерево Th для h>\, мы зададим корень с двумя деревьями, которые также имеют минимальное число Узлов. Следовательно, поддеревья также являются Г-де-Ревьями. Очевидно, что одно поддерево обязано иметь вы-оту h-] а другому позволено иметь высоту на единицу еньше, т. е. А - 2. На рис. 4.30 показаны деревья высотой 2, 4. Поскольку принцип их организации напоминает прин-

цип

построения чисел Фибоначчи, подобные деревья назы-К)тся деревьями Фибоначчи. Они определяются следующим %Чзом:.

Рустое дерево есть дерево Фибоначчи с высотой 0.