АВЛ-дерево

Материал из Викиконспекты
Версия от 21:45, 26 марта 2012; Georgy Konoplich (обсуждение | вклад) (Удаление вершины)
Перейти к: навигация, поиск

АВЛ-дерево — сбалансированное двоичное дерево поиска, в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

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

Высота дерева

Теорема:
АВЛ-дерево с [math]n[/math] ключами имеет высоту [math]h = O(\log N)[/math].
Доказательство:
[math]\triangleright[/math]

Высоту поддерева с корнем [math]x[/math] будем обозначать как [math]h(x)[/math], высоту поддерева [math]T[/math] — как [math]h(T)[/math].

Пусть [math]m_h[/math] — минимальное число вершин в AVL-дереве высоты [math]h[/math]. Тогда, как легко видеть, [math]m_{h+2} = m_{h+1} + m_h + 1[/math], откуда [math]m_h = F_{h+2} - 1[/math], где [math]F_h - h[/math]-ое число Фибоначчи. [math]F_h = \Omega(\varphi^h)[/math], [math]\varphi = \frac{ \sqrt{5}+1}{2}[/math]. Делая замену [math]h = \log_\varphi{n}[/math], получаем, что высота AVL-дерева из n вершин — [math]O(\log{n})[/math].
[math]\triangleleft[/math]

Балансировка

Балансировкой вершины называется операция, которая в случае разницы высот левого и правого поддеревьев [math]|h(L) - h(R)| = 2[/math], изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева [math]|h(L) - h(R)| \le 1[/math], иначе ничего не меняет. Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева [math]diff[i] = h(L) - h(R)[/math]

Для балансировки вершины используются один из 4 типов вращений:

Тип вращения Иллюстрация Когда используется Расстановка балансов
Малое левое вращение AVL RR.GIF [math]h(b) - h(L) = 2[/math] и [math]h(C) \le h(R)[/math].

[math]diff[a] = -2[/math] и [math]diff[b] = -1[/math]

или

[math]diff[a] = -2[/math] и [math]diff[b] = 0[/math].


[math]diff[a] = 0[/math] и [math]diff[b] = 0[/math]


[math]diff[a] = -1[/math] и [math]diff[b] = 1[/math]

Большое левое вращение AVL RL.GIF [math]h(b) - h(L) = 2[/math] и [math]h(c) \gt h(R)[/math].

[math]diff[a] = -2[/math] , [math]diff[b] = 1[/math] и [math]diff[c] = 1[/math]

или

[math]diff[a] = -2[/math], [math]diff[b] = 1[/math] и [math]diff[c] = -1[/math]

или

[math]diff[a] = -2[/math], [math]diff[b] = 1[/math] и [math]diff[c] = 0[/math].


[math]diff[a] = 0[/math], [math]diff[b] = -1[/math] и [math]diff[c] = 0[/math]


[math]diff[a] = 1[/math], [math]diff[b] = 0[/math] и [math]diff[c] = 0[/math]


[math]diff[a] = 0[/math], [math]diff[b] = 0[/math] и [math]diff[c] = 0[/math]

Малое правое вращение AVL LL.GIF [math]h(b) - h(R) = 2[/math] и [math]h(C) \le h(L)[/math].

[math]diff[a] = 2[/math] и [math]diff[b] = 1[/math].

или

[math]diff[a] = 2[/math] и [math]diff[b] = 0[/math].


[math]diff[a] = 0[/math] и [math]diff[b] = 0[/math]


[math]diff[a] = 1[/math] и [math]diff[b] = -1[/math]

Большое правое вращение AVL LR.GIF [math]h(b) - h(R) = 2[/math] и [math]h(c) \gt h(L)[/math].

[math]diff[a] = 2[/math], [math]diff[b] = -1[/math] и [math]diff[c] = 1[/math]

или

[math]diff[a] = 2[/math], [math]diff[b] = -1[/math] и [math]diff[c] = -1[/math]

или

[math]diff[a] = 2[/math], [math]diff[b] = -1[/math] и [math]diff[c] = 0[/math].


[math]diff[a] = -1[/math], [math]diff[b] = 0[/math] и [math]diff[c] = 0[/math]


[math]diff[a] = 0[/math], [math]diff[b] = 1[/math] и [math]diff[c] = 0[/math]


[math]diff[a] = 0[/math], [math]diff[b] = 0[/math] и [math]diff[c] = 0[/math]

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

Все операции вращения, очевидно, требуют [math]O(1)[/math] операций.

Операции

Добавление вершины

Пусть нам надо добавить ключ [math]t[/math]. Будем спускаться по дереву, как при поиске ключа [math]t[/math]. Если мы стоим в вершине [math]a[/math] и нам надо идти в поддерево, которого нет, то делаем ключ [math]t[/math] листом, а вершину [math]a[/math] его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину [math]i[/math] из левого поддерева, то [math]diff[i][/math] увеличивается на единицу, если из правого, то уменьшается на единицу. Подъём останавливается, когда приходим в вершину, баланс которой равен нулю, то есть [math]diff[i] = 0[/math]. Если в результате пересчёта баланса, баланс вершины стал равен 2 или -2, то запускаем процедуру балансировки, которая делает одно из четырёх вращений.

Так как в процессе добавления вершины мы рассматриваем не более, чем [math] O(h) [/math] вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет [math] O(\log{n}) [/math] операций.

Удаление вершины

Для простоты опишем рекурсивный алгоритм удаления. Если вершина - лист, то удалим её, иначе найдём самую близкую по значению вершину [math]a[/math], переместим её на место удаляемой вершины и удалим вершину [math]a[/math]. От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину [math]i[/math] из левого поддерева, то [math]diff[i][/math] уменьшается на единицу, если из правого, то увеличивается на единицу. Подъём останавливается, когда приходим в вершину, баланс которой равен нулю, то есть [math]diff[i] = 0[/math]. Если в результате пересчёта баланса, баланс вершины стал равен 2 или -2, то запускаем процедуру балансировки, которая делает одно из четырёх вращений.

В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, [math] O(h) [/math] операций. Таким образом, требуемое количество действий — [math] O(\log{n}) [/math].

Поиск вершины, минимум/максимум в дереве, etc.

Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в наивной реализации дерева поиска.

Слияние двух AVL-деревьев

Дано два дерева [math]T_1[/math] и [math]T_2[/math], все ключи в [math]T_1[/math] меньше ключей в [math]T_2[/math], [math]h(T_1) \le h(T_2)[/math].


Avltree1.jpg

В дереве [math]T_1[/math] удаляем самую правую вершину, назовём её [math]b[/math]. Высота дерева [math]T_1[/math] может уменьшиться на единицу. В дереве [math]T_2[/math] идём от корня всегда в левое поддерево и, когда высота этого поддерева [math]P[/math] будет равна высоте дерева [math]T_1[/math], делаем новое дерево [math]Q[/math], корнем [math]Q[/math] будет вершина [math]b[/math], левым поддеревом будет дерево [math]T_1[/math], а правым дерево [math]P[/math]. Теперь в дереве [math]T_2[/math] у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево [math]Q[/math] и запускаем балансировку. Таким образом, дерево [math]T_2[/math] будет результатом слияния двух АВЛ-деревьев.

Avltree2.jpg

Литература