Изменения
→Балансировка
'''АВЛ-дерево''' (англ. ''AVL-Tree'') {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.
!Расстановка балансов
|-
|'''Малое левое вращение''' (''Small left rotation'')
| [[Файл:avl_u1.jpg|2000x200px]]
|
<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>
|-
|'''Большое левое вращение''' (Big left rotation'')
| [[Файл:avl_u2.jpg|2000x200px]]
|
|}
Малый левый поворот:
Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению.
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на <tex>1</tex> и не может увеличиться.
Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.
== Операции ==
=== Удаление вершины ===
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина {{- --}} лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <tex>a</tex>, переместим её на место удаляемой вершины и [[Дерево поиска, наивная реализация#Удаление|удалим]] вершину <tex>a</tex>. От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> уменьшается на единицу, если из правого, то увеличивается на единицу. Если пришли в вершину и её баланс стал равным <tex>1</tex> или <tex>-1</tex>, то это значит, что высота этого поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс стал равным <tex>2</tex> или <tex>-2</tex>, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.
В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.
Если мы пришли в поддерево <tex>Q</tex>, корень которого <tex>> x</tex>, совершаем аналогичные действия: делаем NULL'ами ссылки на корень <tex>Q</tex>, запоминая ссылку на его левое поддерево. Делаем новую вершину со значением бывшего корня левым листом самой левой вершины <tex>Q</tex> и запускаем балансировку. Объединяем полученное АВЛ-дерево с уже построенным ранее <tex>T_{2}</tex> аналогичным первому случаю способом, только теперь мы ищем самое левое поддерево <tex>T_{2}</tex>.
{| cellpadding="2"
Итоговая асимптотика алгоритма {{---}} <tex>O(\log{n})</tex>.
== АВЛ-дерево с O(1) бит в каждом узле ==
=== Идея ===
В обычной реализации АВЛ-дерева в каждом узле мы хранили высоту этого узла. Так как высоты левых и правых поддеревьев в АВЛ-дереве отличаются максимум на <tex>1</tex>, то мы будем хранить не всю высоту дерева, а некоторое число, которое будет показывать, какое поддерево больше, или равны ли они, назовём ''фактор баланса''. Таким образом в каждом узле будет хранится <tex>1</tex> {{---}} если высота правого поддерева выше левого, <tex>0</tex> {{---}} если высоты равны, и <tex>-1</tex> {{---}} если правое поддерево выше левого.
=== Операции ===
'''Операция добавления''' <br>
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Пересчитываем баланс данного узла <tex>a</tex>. Если он оказался <tex>0</tex>, то высота поддерева с корнем в этой вершине не изменилась и пересчет балансов останавливается. Дальше начинаем подниматься вверх по дереву, исправляя балансы попутных узлов. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то баланс увеличивается на единицу, если из правого, то уменьшается на единицу. Если мы пришли в вершину и её баланс стал равным <tex>1</tex> или <tex>-1</tex>, то это значит, что высота поддерева изменилась и подъём продолжается. Если баланс вершины <tex>a</tex>, в которую мы собираемся идти из ее левого поддерева, равен <tex>1</tex>, то делается поворот для этой вершины <tex>a</tex>. Аналогично делаем поворот, если баланс вершины <tex>a</tex>, в которую мы идем из ее правого поддерева, равен <tex>-1</tex>. Если в результате изменения узла, фактор баланса стал равен нулю, то останавливаемся, иначе продолжаем подъём.
'''Операция удаления''' <br>
Если вершина {{---}} лист, то просто удалим её, иначе найдём ближайшую по значению вершину <tex>a</tex>, поменяем ее местами с удаляемой вершиной и удалим. От удалённой вершины будем подниматься вверх к корню и пересчитывать фактор баланса вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то фактор баланса уменьшается на единицу, если из правого, то увеличивается на единицу. Если мы пришли в вершину и её баланс стал равным <tex>1</tex> или <tex>-1</tex>, то это значит, что высота поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс вершины <tex>a</tex>, в которую мы собираемся идти из ее левого поддерева, равен <tex>-1</tex>, то делается поворот для этой вершины <tex>a</tex>. Аналогично делаем поворот, если баланс вершины <tex>a</tex>, в которую мы идем из ее правого поддерева, равен <tex>1</tex>. Если в результате изменения узла, фактор баланса стал равен нулю, то подъём продолжается, иначе останавливается.
=== Балансировка ===
Опишем операции балансировки, а именно малый левый поворот, большой левый поворот и случаи их возникновения. Балансировка нам нужна для операций добавления и удаления узла. Для исправления факторов баланса, достаточно знать факторы баланса двух(в случае большого поворота {{---}} трех) вершин перед поворотом, и исправить значения этих же вершин после поворота. Обозначим фактор баланса вершины <tex>i</tex> как <tex>balance[i]</tex>. Операции поворота делаются на том шаге, когда мы находимся в правом сыне вершины <tex>a</tex>, если мы производим операцию добавления, и в левом сыне, если мы производим операцию удаления. Вычисления производим заранее, чтобы не допустить значения <tex>2</tex> или <tex>-2</tex> в вершине <tex>a</tex>. На каждой иллюстрации изображен один случай высот поддеревьев. Нетрудно убедиться, что в остальных случаях всё тоже будет корректно.
{| border="1" cellpadding="5" cellspacing="0"
!Тип вращения
!Иллюстрация
!Факторы балансов до вращения
!Факторы балансов после вращения
|-
|'''Малое левое вращение'''
| [[Файл:Avl_u1.jpg|2000x200px]]
|
'''1 вариант:''' <tex>balance[a] = -1</tex> и <tex>balance[b] = -1</tex>
'''2 вариант:''' <tex>balance[a] = -1</tex> и <tex>balance[b] = 0</tex>
|
'''1 вариант:''' <tex>balance[a] = 0</tex> и <tex>balance[b] = 0</tex>
'''2 вариант:''' <tex>balance[a] = -1</tex> и <tex>balance[b] = 1</tex>
|-
|'''Большое левое вращение'''
| [[Файл:Avl_u2.jpg|2000x200px]]
|
'''1 вариант:''' <tex>balance[a] = -1</tex> , <tex>balance[b] = 1</tex> и <tex>balance[c] = 1</tex>
'''2 вариант:''' <tex>balance[a] = -1</tex>, <tex>balance[b] = 1</tex> и <tex>balance[c] = -1</tex>
'''3 вариант:''' <tex>balance[a] = -1</tex>, <tex>balance[b] = 1</tex> и <tex>balance[c] = 0</tex>
|
'''1 вариант:''' <tex>balance[a] = 0</tex>, <tex>balance[b] = -1</tex> и <tex>balance[c] = 0</tex>
'''2 вариант:''' <tex>balance[a] = 1</tex>, <tex>balance[b] = 0</tex> и <tex>balance[c] = 0</tex>
'''3 вариант:''' <tex>balance[a] = 0</tex>, <tex>balance[b] = 0</tex> и <tex>balance[c] = 0</tex>
|}
=== Примеры ===
Ниже приведены примеры добавления и удаления вершины с подписанными изменениями факторов баланса каждой вершины.
{| cellpadding="2"
| || [[Файл:Avl_add.png|thumb|left|1050px|'''Добавление''']]
|}
{| cellpadding="2"
| || [[Файл:Avl_delete.png|thumb|left|1050px|'''Удаление''']]
|}
== См. также ==
* [[Splay-дерево]]
* [[Красно-черное дерево]]
* [[2-3 дерево]]
== Источники информации ==
* [http://habrahabr.ru/post/150732/ Habrahabr {{---}} АВЛ-деревья]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]
[[Категория:Структуры данных]]
