Эффективность сортировки вставкой в АВЛ - дерево .

Ожидаемое число сравнений, необходимых для вставки узла в бинарное дерево поиска, равно O(log2n). Поскольку в дерево вставляется n элементов, средняя эффективность должна быть O(n log2n). Однако в худшем случае, когда исходный список отсортирован в обратном порядке, она составит O(n2). Соответствующее дерево поиска вырождается в связанный список. Покажем, что худший случай требует O(n2) сравнений. Первая вставка требует 0 сравнений. Вторая вставка - двух сравнений (одно с корнем и одно для определения того, в какое поддерево следует вставлять данное значение). Третья вставка требует трех сравнений, 4 - я четырех,..., n - я вставка требует n сравнений. Тогда общее число сравнений равно:

 

0 + 2 + 3 +... + n = (1 + 2 + 3 +... + n) - 1 = n(n + 1) / 2 - 1 = O(n2)

 

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

Когда n случайных значений повторно вставляются в бинарное дерево поиска, можно ожидать, что дерево будет относительно сбалансированным. Наилучшим случаем является законченное бинарное дерево. Для этого случая можно оценить верхнюю границу, рассмотрев полное дерево глубиной d. На i-ом уровне (1≤i≤d) имеется 2i узлов. Поскольку для помещения узла на уровень i требуется i+1 сравнение, сортировка на полном дереве требует (i+1) * 2i сравнений для вставки всех элементов на уровень i.

Если вспомнить, что n = 2(d+1) - 1, то верхняя граница меры эффективности выражается следующим неравенством:

 

 

Таким образом, эффективность алгоритма в лучшем случае составит O(n log2n).

 

Удаление элемента из сбалансированного дерева.

Алгоритм удаления элемента из сбалансированного дерева будет выглядеть так:

1. Поиск по дереву.

2. Удаление элемента из дерева.

3. Восстановление сбалансированности дерева (обратный проход).

1 - ый и 2 - ый шаги необходимы, чтобы найти в дереве вершину, которая должна быть удалена.

3 - ий шаг представляет собой обратный проход от места, из которого взят элемент для замены удаляемого, или от места, из которого удален элемент, если в замене не было необходимости.

Операция удаления может потребовать перебалансировки всех вершин вдоль обратного пути к корню дерева, то есть порядка log(N) вершин.

 

Анализ операций над сбалансированным деревом.

Понятно, что в случае полного двоичного дерева мы получим сложность T(log(n)) (на каждом шаге размер дерева поиска будет сокращаться вдвое). Рассмотрим минимальное сбалансированное дерево (худший случай). Таким будет дерево, у которого для каждой вершины высота левого и правого поддеревьев различаются на 1. Для такого дерева можно записать следующую рекуррентную формулу для числа вершин (h – высота дерева):

 

 

Покажем, что h<log₂(N_h). Для этого необходимо и достаточно показать, что 2^h>N_h. Докажем последнее методом математической индукции.а) h=0: 2⁰>N₀=0; б) h=1: 2¹>N₁=1; в) h>1: Пусть 2^h-2>N_h-2 и 2^h-1>N_h-1. Тогда 2^h-2+2^h-1>N_h-2+ N_h-1. И далее получаем 2^h>1+2^h-2+2^h-1>1+N_h-2+ N_h-1=N_h, что и требовалось доказать.

Таким образом алгоритмы поиска/добавления/удаления элементов в сбалансированном дереве имеют сложность T(log(n)). Г.М. Адельсон -Вельский и Е.М. Ландис доказали теорему, согласно которой высота сбалансированного дерева никогда не превысит высоту идеально сбалансированного дерева более, чем на 45%.