АВЛ-дерево — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Высота дерева)
Строка 4: Строка 4:
  
 
== Высота дерева ==
 
== Высота дерева ==
 +
{{Теорема
 +
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
 +
||proof=
 +
 
Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.
 
Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.
  
 
Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>, откуда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи. <tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. Делая замену <tex>h = \log_\varphi{n}</tex>, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.
 
Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>, откуда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи. <tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. Делая замену <tex>h = \log_\varphi{n}</tex>, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.
 +
}}
  
 
== Балансировка ==
 
== Балансировка ==

Версия 18:12, 24 марта 2012

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

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

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

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

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

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

Процесс включения вершины состоит из двух частей:

  1. Прохода по пути поиска, пока не убедимся, что ключа в дереве нет.
  2. "Отступления" назад по пути поиска, вплоть до корня и пересчета высот в каждой вершине на обратном пути. При необходимости осуществляется балансировка.

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

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

Для простоты опишем рекурсивный алгоритм удаления. Если вершина - лист, то удалим её и вызовем балансировку всех её предков в порядке от родителя к корню. Иначе найдём самую близкую по значению вершину и переместим её на место удаляемой вершины, при этом вызвав процедуру её удаления.

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

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

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

Литература