Оценка сложности поиска в АВЛ-дереве

Два крайних случая АВЛ-деревьев это:

(а) совершенное дерево – все узлы имеют показатель баланса 0;

(б) дерево Фибоначчи – все узлы, кроме листовых, имеют показатель баланса +1, либо все узлы, кроме листовых, имеют показатель баланса –1.

Не для каждого набора ключей можно построить совершенное дерево, равно как и не для каждого набора ключей можно построить дерево Фибоначчи. Но эти деревья позволяют оценить диапазон возможных высот АВЛ-деревьев. Совершенное дерево является частным случаем идеально сбалансированного дерева, поэтому оно имеет минимально возможную высоту для данного количества узлов. Дерево Фибоначчи, напротив, имеет максимально возможную высоту для данного количества узлов, при условии, что сохраняются свойства АВЛ-дерева. В совершенном дереве у каждого узла, кроме листовых, ровно два сына. Тогда количество узлов m равно 1 + 2 + 2² + … Количество таких слагаемых равно количеству уровней в дереве, т.е. на единицу больше высоты этого дерева. Если количество слагаемых равно h + 1, то степень двойки в последнем слагаемом будет равна h:

Поэтому высота совершенного дерева вычисляется как h = log2(m + 1) – 1

Дерево Фибоначчи имеет минимально возможную высоту для заданного количества узлов среди всех АВЛ-деревьев. Если переформулировать свойство дерева Фибоначчи, то получится, что при заданной высоте оно имеет минимальное количество узлов из всех возможных АВЛ-деревьев.

Из определения дерева Фибоначчи следует, что для любого узла, кроме листовых, разность высот левого и правого поддеревьев равна 1 либо –1. Не ограничивая общности рассуждений, будем считать, что эта разность равна 1. Таким образом, если высота дерева равна h, то высоты левого и правого поддеревьев равны h – 2 и h – 1 соответственно. Это свойство выполняется для любого поддерева дерева Фибоначчи.

*ДАЛЬШЕ МНОГО ВЫЧИСЛЕНИЙ ВСЯКИХ, ШЛИ БЫ ОНИ НАФИГ*

Высота h АВЛ-дерева из m узлов находится в диапазоне

Это соотношение задает оценку количества сравнений при поиске узла в АВЛ-дереве на пути от корня к этому узлу. Если, например, в АВЛ-дереве 10⁶ вершин, то его высота, а, следовательно, и сложность поиска узла в нем, не превысит 29.

Особенностью АВЛ-дерева является то, что оно является сбалансированным в следующем смысле: для любого узла дерева высота его правого поддерева отличается от высоты левого поддерева не более чем на единицу. Доказано, что этого свойства достаточно для того, чтобы высота дерева логарифмически зависела от числа его узлов: высота h АВЛ-дерева с n ключами лежит в диапазоне от log2(n + 1) до 1.44 log2(n + 2) − 0.328. А так как основные операции над двоичными деревьями поиска (поиск, вставка и удаление узлов) линейно зависят от его высоты, то получаем гарантированную логарифмическую зависимость времени работы этих алгоритмов от числа ключей, хранимых в дереве.