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

Материал из Викиконспекты
Перейти к: навигация, поиск
(2 правки пунктуации)
 
(не показаны 23 промежуточные версии 7 участников)
Строка 1: Строка 1:
'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.
+
'''АВЛ-дерево''' (англ. ''AVL-Tree'') {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.
  
 
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.
 
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.
Строка 13: Строка 13:
 
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где            <tex>F_h - h</tex>-ое число Фибоначчи.   
 
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где            <tex>F_h - h</tex>-ое число Фибоначчи.   
 
|proof=
 
|proof=
Если <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>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>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>.  
 
База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>.  
Строка 25: Строка 25:
  
  
<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть
+
<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \dfrac{ \sqrt{5}+1}{2}</tex>. То есть
  
 
<tex>n \geqslant \varphi^{h}</tex>
 
<tex>n \geqslant \varphi^{h}</tex>
Строка 63: Строка 63:
  
 
<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>
 
<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>
 
 
  |-
 
  |-
 
  |'''Большое левое вращение'''
 
  |'''Большое левое вращение'''
Строка 87: Строка 86:
  
 
<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
 
<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
 +
|}
 +
Малый левый поворот:
 +
  '''function''' rotateLeft(Node a):
 +
    Node b = a.right
 +
    a.right = b.left
 +
    b.left = a
 +
    корректировка высоты a
 +
    корректировка высоты b
  
|}
+
Большой левый поворот пишется проще:
 +
  '''function''' bigRotateLeft(Node a):
 +
    rotateRight(a.right)
 +
    rotateLeft(a)
 +
 
 
Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению.
 
Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению.
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.
+
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на <tex>1</tex> и не может увеличиться.
  
Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.
+
Все вращения, очевидно, требуют <tex>O(1)</tex> операций.
  
 
== Операции ==
 
== Операции ==
Строка 102: Строка 113:
 
=== Удаление вершины ===
 
=== Удаление вершины ===
 
Для простоты опишем рекурсивный алгоритм удаления.
 
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <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>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> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.
Строка 124: Строка 135:
 
[[File:avl_u4.jpg|300px]]
 
[[File:avl_u4.jpg|300px]]
  
== Ссылки ==
+
===Алгоритм разделения AVL-дерева на два===
 +
====Алгоритм первый====
 +
Пусть у нас есть дерево <tex>T</tex>. Мы должны разбить его на два дерева <tex>T_{1}</tex> и <tex>T_{2}</tex> такие, что <tex>T_{1} \leqslant x</tex> и <tex>x < T_{2}</tex>.
 +
 
 +
Предположим, что корень нашего дерева <tex>\leqslant x</tex>, в таком случае все левое поддерево вместе с корнем после разделения отойдет в дерево <tex>T_{1}</tex>. Тогда рекурсивно спускаемся в правое поддерево и там проверяем это условие (так как часть правого поддерева тоже может содержать ключи <tex>\leqslant x</tex>). Если же корень оказался <tex>> x</tex>, то мы спускаемся той же рекурсией, но только в левое поддерево и ищем там.
 +
 
 +
Пусть мы пришли в поддерево <tex>S</tex>, корень которого <tex>\leqslant x</tex>. В таком случае этот корень со своим левым поддеревом должен отойти в дерево <tex>T_{1}</tex>. Поэтому мы делаем следующее: запоминаем ссылку на правое поддерево <tex>S</tex>, удаляем корень, запоминая его значение (не меняя конфигурацию дерева, то есть просто делаем ссылки на него NULL'ами). Таким образом, мы отделяем сбалансированное АВЛ-дерево (бывшее левое поддерево <tex>S</tex>). Делаем новую вершину со значением бывшего корня правым листом самой правой вершины <tex>S</tex> и запускаем балансировку. Обозначим полученное дерево за <tex>T'</tex>. Теперь нам нужно объединить его с уже построенным ранее <tex>T_{1}</tex> (оно может быть пустым, если мы первый раз нашли такое дерево <tex>S</tex>). Для этого мы ищем в дереве <tex>T_{1}</tex> самое правое поддерево <tex>P</tex> высоты, равной высоте <tex>T'</tex> (спускаясь от корня всегда в правые поддеревья). Делаем новое дерево <tex>K</tex>, сливая <tex>P</tex> и <tex>T'</tex> (очевидно, все ключи в <tex>T_{1}</tex> меньше ключей в <tex>T'</tex>, поэтому мы можем это сделать). Теперь в дереве <tex>T_{1}</tex> у отца вершины, в которой мы остановились при поиске дерева <tex>P</tex>, правым поддеревом делаем дерево <tex>K</tex> и запускаем балансировку. После нужно спуститься в правое поддерево бывшего дерева <tex>S</tex> (по ссылке, которую мы ранее запомнили) и обработать его.
 +
 
 +
Если мы пришли в поддерево <tex>Q</tex>, корень которого <tex>> x</tex>, совершаем аналогичные действия: делаем NULL'ами ссылки на корень <tex>Q</tex>, запоминая ссылку на его левое поддерево. Делаем новую вершину со значением бывшего корня левым листом самой левой вершины <tex>Q</tex> и запускаем балансировку. Объединяем полученное АВЛ-дерево с уже построенным ранее <tex>T_{2}</tex> аналогичным первому случаю способом, только теперь мы ищем самое левое поддерево <tex>T_{2}</tex>.
 +
 
 +
Рассмотрим пример (рис. 1). Цветом выделены поддеревья, которые после разделения должны отойти в дерево <tex>T_{1}</tex>. <tex>x = 76</tex>.
 +
 
 +
{| cellpadding="2"
 +
| || [[Файл:AVL.jpg|thumb|left|525px|Рис. 1. Разделение АВЛ-дерева на два.]]
 +
|}
 +
 
 +
Корень дерева <tex>\leqslant x</tex>, поэтому он со всем выделенным поддеревом должен отойти в дерево <tex>T_{1}</tex>. По описанному выше алгоритму отделяем это поддерево с корнем и делаем из них сбалансированное АВЛ-дерево <tex>T'</tex> (рис. 2). Так как это первая ситуация, в которой корень рассматриваемого поддерева был <tex>\leqslant x</tex>, <tex>T'</tex> становится <tex>T_{1}</tex>. Далее по сохраненной ссылке спускаемся в правое поддерево. Его корень <tex>> x</tex>. Следовательно, строим из него и его правого поддерева <tex>T_{2}</tex> и спускаемся в левое поддерево. Снова корень <tex>\leqslant x</tex>. Строим новое <tex>T'</tex> и объединяем его с уже существующим <tex>T_{1}</tex> (рис. 3).
 +
 
 +
{| cellpadding="2"
 +
| || [[Файл:АВВЛ2.jpg|thumb|left|525px|Рис. 2. Создание T'.]]
 +
|}
 +
{| cellpadding="2"
 +
| || [[Файл:AVL3.jpg|thumb|left|1050px|Рис. 3. Объединение T' и T1.]]
 +
|}
 +
 
 +
Далее действуем по алгоритму и в итоге получаем (рис. 4):
 +
 
 +
{| cellpadding="2"
 +
| || [[Файл:End.jpg|thumb|left|525px|Рис. 4. АВЛ-деревья после разделения.]]
 +
|}
 +
 
 +
Данный алгоритм имеет сложность <tex>O(\log^{2} n)</tex>.
 +
 
 +
====Алгоритм второй====
 +
Рассмотрим решение, которое имеет сложность <tex>O(\log{n})</tex>.
 +
 
 +
Вернемся к примеру (рис. 1). Теперь рекурсивно спустимся вниз и оттуда будем строить деревья <tex>T_{1}</tex> и <tex>T_{2}</tex>, передавая наверх корректные АВЛ-деревья. То есть для рис. 1 первым в дерево <tex>T_{1}</tex> придет вершина <tex>75</tex> с левым поддеревом (выделено светло-зеленым цветом), так как это корректное АВЛ-дерево, оно же и вернется из рекурсии. Далее мы попадем в вершину со значением <tex>70</tex> и должны слить ее и ее левое поддерево (выделено светло-синим) с тем, что нам пришло. И сделать это нужно так, чтобы передать наверх корректное АВЛ-дерево. Будем действовать по такому алгоритму, пока не дойдем до вершины.
 +
 
 +
Пусть мы пришли в поддерево <tex>S</tex> с корнем <tex>\leqslant x</tex>. Тогда сольем его с уже построенным на тот момент <tex>T_{1}</tex> (<tex>T_{1}</tex> пришло снизу, а значит по условию рекурсии это корректное АВЛ-дерево, <tex>S \leqslant T_{1}</tex> и <tex>h(T_{1}) \leqslant h(S)</tex>). Но так как обычная процедура слияния сливает два АВЛ-дерева, а <tex>S</tex> не является корректным АВЛ-деревом, мы немного ее изменим. Пусть мы в дереве <tex>S</tex> нашли самое правое поддерево <tex>K</tex>, высота которого равна высоте <tex>T_{1}</tex>. Тогда сделаем новое дерево <tex>T'</tex>, корнем которого будет вершина <tex>S</tex> (без нее это дерево является сбалансированным), правым поддеревом {{---}} <tex>T_{1}</tex>, левым {{---}} <tex>K</tex>. И подвесим <tex>T'</tex> на то место, где мы остановились при поиске <tex>K</tex>. Запустим балансировку. В случае, когда корень поддерева, в которое мы пришли, <tex>> x</tex>, все аналогично.
 +
 
 +
Разберем пример на рис. 1. Пусть мы рекурсивно спустились до узла <tex>77</tex>. Ключ больше <tex>x</tex>, поэтому эта вершина станет деревом <tex>T_{2}</tex> и передастся наверх. Теперь мы поднялись в узел <tex>75</tex>. Он со своим левым поддеревом станет деревом <tex>T_{1}</tex> и мы снова поднимемся наверх в узел <tex>70</tex>. Он со своим левым поддеревом снова должен отойти в дерево <tex>T_{1}</tex>, и так как теперь дерево <tex>T_{1}</tex> уже не пустое, то их надо слить. После слияния по описанному выше алгоритму получим (рис. 5)
 +
 
 +
{| cellpadding="2"
 +
| || [[Файл:Ex.jpg|thumb|left|525px|Рис. 5.]]
 +
|}
 +
 
 +
После мы поднимемся в вершину с ключом <tex>80</tex>. Она с правым поддеревом отойдет в дерево <tex>T_{2}</tex> (рис. 6).
 +
 
 +
{| cellpadding="2"
 +
| || [[Файл:Ex2am.jpg|thumb|left|525px|Рис. 6.]]
 +
|}
 +
 
 +
И на последней итерации мы поднимемся в корень дерева с ключом <tex>50</tex>, он с левым поддеревом отойдет в дерево <tex>T_{1}</tex>, после чего алгоритм завершится.
 +
 
 +
Пусть поддеревьев с ключами <tex>\leqslant x</tex> оказалось больше, чем поддеревьев с ключами <tex>> x</tex>. Докажем для них логарифмическую асимптотику. Дерево на последнем уровне имеет высоту <tex>H_{k}</tex> (она может быть не равна <tex>1</tex>, если мы придём в <tex>x</tex>). Его мы передаем наверх и вставляем в поддерево высотой <tex>H_{k-1}</tex>. <tex>H_{k} \leqslant H_{k-1}</tex>, так как разница высот поддеревьев у любой вершины не больше <tex>1</tex>, и мы при переходе от <tex>H_{k}</tex> к <tex>H_{k-1}</tex> поднимаемся как минимум на одну вершину вверх. Слияние этих поддеревьев мы выполним за <tex>H_{k-1} - H_{k}</tex>, получим в итоге дерево высоты не большей, чем <tex>H_{k-1}</tex>. Его мы передадим наверх, поэтому в следующий раз слияние будет выполнено за <tex>H_{k-2} - H_{k - 1}</tex> и так далее. Таким образом мы получим <tex>(H - H_{1}) + (H_{1} - H_{2}) + (H_{2} - H_{3}) + \cdots +  (H_{k - 1} - H_{k}) = H - H_{k} = O(\log{n})</tex>.
 +
 
 +
Итоговая асимптотика алгоритма {{---}} <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 {{---}} АВЛ-деревья]
 
* [http://habrahabr.ru/post/150732/ Habrahabr {{---}} АВЛ-деревья]
== Источники информации ==
 
 
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]
 
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]
  
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Деревья поиска]]
 
[[Категория:Деревья поиска]]
 +
[[Категория:Структуры данных]]

Текущая версия на 22:01, 5 сентября 2019

АВЛ-дерево (англ. AVL-Tree) — сбалансированное двоичное дерево поиска, в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 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 = F_{h+2} - 1[/math], где [math]F_h - h[/math]-ое число Фибоначчи.
Доказательство:
[math]\triangleright[/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]m_1 = F_3 - 1[/math] — верно, [math]m_1 = 1, F_3 = 2[/math].

Допустим [math]m_h = F_{h+2} - 1[/math] — верно.

Тогда [math]m_{h+1} = m_h + m_{h-1} + 1 = F_{h+2} - 1 + F_{h+1} - 1 + 1 = F_{h+3} - 1[/math].

Таким образом, равенство [math]m_h = F_{h+2} - 1[/math] — доказано.
[math]\triangleleft[/math]


[math]F_h = \Omega(\varphi^h)[/math], [math]\varphi = \dfrac{ \sqrt{5}+1}{2}[/math]. То есть

[math]n \geqslant \varphi^{h}[/math]

Логарифмируя по основанию [math]\varphi[/math], получаем

[math]\log_{\varphi}n \geqslant h[/math]

Таким образом, получаем, что высота AVL-дерева из n вершин — [math]O(\log{n})[/math].
[math]\triangleleft[/math]

Балансировка[править]

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

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

Тип вращения Иллюстрация Когда используется Расстановка балансов
Малое левое вращение Avl u1.jpg

[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 u2.jpg

[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]

Малый левый поворот:

 function rotateLeft(Node a):
   Node b = a.right
   a.right = b.left
   b.left = a
   корректировка высоты a
   корректировка высоты b

Большой левый поворот пишется проще:

 function bigRotateLeft(Node a):
   rotateRight(a.right)
   rotateLeft(a)
 

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

Все вращения, очевидно, требуют [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]1[/math] или [math]-1[/math], то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным [math]2[/math] или [math]-2[/math], то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.

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

Удаление вершины[править]

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

В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, [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) \leqslant h(T_2)[/math].

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

Дерево [math]T_1[/math] и [math]T_2[/math] до слияния


Avl u3.jpg

Дерево [math]T_2[/math] после слияния


Avl u4.jpg

Алгоритм разделения AVL-дерева на два[править]

Алгоритм первый[править]

Пусть у нас есть дерево [math]T[/math]. Мы должны разбить его на два дерева [math]T_{1}[/math] и [math]T_{2}[/math] такие, что [math]T_{1} \leqslant x[/math] и [math]x \lt T_{2}[/math].

Предположим, что корень нашего дерева [math]\leqslant x[/math], в таком случае все левое поддерево вместе с корнем после разделения отойдет в дерево [math]T_{1}[/math]. Тогда рекурсивно спускаемся в правое поддерево и там проверяем это условие (так как часть правого поддерева тоже может содержать ключи [math]\leqslant x[/math]). Если же корень оказался [math]\gt x[/math], то мы спускаемся той же рекурсией, но только в левое поддерево и ищем там.

Пусть мы пришли в поддерево [math]S[/math], корень которого [math]\leqslant x[/math]. В таком случае этот корень со своим левым поддеревом должен отойти в дерево [math]T_{1}[/math]. Поэтому мы делаем следующее: запоминаем ссылку на правое поддерево [math]S[/math], удаляем корень, запоминая его значение (не меняя конфигурацию дерева, то есть просто делаем ссылки на него NULL'ами). Таким образом, мы отделяем сбалансированное АВЛ-дерево (бывшее левое поддерево [math]S[/math]). Делаем новую вершину со значением бывшего корня правым листом самой правой вершины [math]S[/math] и запускаем балансировку. Обозначим полученное дерево за [math]T'[/math]. Теперь нам нужно объединить его с уже построенным ранее [math]T_{1}[/math] (оно может быть пустым, если мы первый раз нашли такое дерево [math]S[/math]). Для этого мы ищем в дереве [math]T_{1}[/math] самое правое поддерево [math]P[/math] высоты, равной высоте [math]T'[/math] (спускаясь от корня всегда в правые поддеревья). Делаем новое дерево [math]K[/math], сливая [math]P[/math] и [math]T'[/math] (очевидно, все ключи в [math]T_{1}[/math] меньше ключей в [math]T'[/math], поэтому мы можем это сделать). Теперь в дереве [math]T_{1}[/math] у отца вершины, в которой мы остановились при поиске дерева [math]P[/math], правым поддеревом делаем дерево [math]K[/math] и запускаем балансировку. После нужно спуститься в правое поддерево бывшего дерева [math]S[/math] (по ссылке, которую мы ранее запомнили) и обработать его.

Если мы пришли в поддерево [math]Q[/math], корень которого [math]\gt x[/math], совершаем аналогичные действия: делаем NULL'ами ссылки на корень [math]Q[/math], запоминая ссылку на его левое поддерево. Делаем новую вершину со значением бывшего корня левым листом самой левой вершины [math]Q[/math] и запускаем балансировку. Объединяем полученное АВЛ-дерево с уже построенным ранее [math]T_{2}[/math] аналогичным первому случаю способом, только теперь мы ищем самое левое поддерево [math]T_{2}[/math].

Рассмотрим пример (рис. 1). Цветом выделены поддеревья, которые после разделения должны отойти в дерево [math]T_{1}[/math]. [math]x = 76[/math].

Рис. 1. Разделение АВЛ-дерева на два.

Корень дерева [math]\leqslant x[/math], поэтому он со всем выделенным поддеревом должен отойти в дерево [math]T_{1}[/math]. По описанному выше алгоритму отделяем это поддерево с корнем и делаем из них сбалансированное АВЛ-дерево [math]T'[/math] (рис. 2). Так как это первая ситуация, в которой корень рассматриваемого поддерева был [math]\leqslant x[/math], [math]T'[/math] становится [math]T_{1}[/math]. Далее по сохраненной ссылке спускаемся в правое поддерево. Его корень [math]\gt x[/math]. Следовательно, строим из него и его правого поддерева [math]T_{2}[/math] и спускаемся в левое поддерево. Снова корень [math]\leqslant x[/math]. Строим новое [math]T'[/math] и объединяем его с уже существующим [math]T_{1}[/math] (рис. 3).

Рис. 2. Создание T'.
Рис. 3. Объединение T' и T1.

Далее действуем по алгоритму и в итоге получаем (рис. 4):

Рис. 4. АВЛ-деревья после разделения.

Данный алгоритм имеет сложность [math]O(\log^{2} n)[/math].

Алгоритм второй[править]

Рассмотрим решение, которое имеет сложность [math]O(\log{n})[/math].

Вернемся к примеру (рис. 1). Теперь рекурсивно спустимся вниз и оттуда будем строить деревья [math]T_{1}[/math] и [math]T_{2}[/math], передавая наверх корректные АВЛ-деревья. То есть для рис. 1 первым в дерево [math]T_{1}[/math] придет вершина [math]75[/math] с левым поддеревом (выделено светло-зеленым цветом), так как это корректное АВЛ-дерево, оно же и вернется из рекурсии. Далее мы попадем в вершину со значением [math]70[/math] и должны слить ее и ее левое поддерево (выделено светло-синим) с тем, что нам пришло. И сделать это нужно так, чтобы передать наверх корректное АВЛ-дерево. Будем действовать по такому алгоритму, пока не дойдем до вершины.

Пусть мы пришли в поддерево [math]S[/math] с корнем [math]\leqslant x[/math]. Тогда сольем его с уже построенным на тот момент [math]T_{1}[/math] ([math]T_{1}[/math] пришло снизу, а значит по условию рекурсии это корректное АВЛ-дерево, [math]S \leqslant T_{1}[/math] и [math]h(T_{1}) \leqslant h(S)[/math]). Но так как обычная процедура слияния сливает два АВЛ-дерева, а [math]S[/math] не является корректным АВЛ-деревом, мы немного ее изменим. Пусть мы в дереве [math]S[/math] нашли самое правое поддерево [math]K[/math], высота которого равна высоте [math]T_{1}[/math]. Тогда сделаем новое дерево [math]T'[/math], корнем которого будет вершина [math]S[/math] (без нее это дерево является сбалансированным), правым поддеревом — [math]T_{1}[/math], левым — [math]K[/math]. И подвесим [math]T'[/math] на то место, где мы остановились при поиске [math]K[/math]. Запустим балансировку. В случае, когда корень поддерева, в которое мы пришли, [math]\gt x[/math], все аналогично.

Разберем пример на рис. 1. Пусть мы рекурсивно спустились до узла [math]77[/math]. Ключ больше [math]x[/math], поэтому эта вершина станет деревом [math]T_{2}[/math] и передастся наверх. Теперь мы поднялись в узел [math]75[/math]. Он со своим левым поддеревом станет деревом [math]T_{1}[/math] и мы снова поднимемся наверх в узел [math]70[/math]. Он со своим левым поддеревом снова должен отойти в дерево [math]T_{1}[/math], и так как теперь дерево [math]T_{1}[/math] уже не пустое, то их надо слить. После слияния по описанному выше алгоритму получим (рис. 5)

Рис. 5.

После мы поднимемся в вершину с ключом [math]80[/math]. Она с правым поддеревом отойдет в дерево [math]T_{2}[/math] (рис. 6).

Рис. 6.

И на последней итерации мы поднимемся в корень дерева с ключом [math]50[/math], он с левым поддеревом отойдет в дерево [math]T_{1}[/math], после чего алгоритм завершится.

Пусть поддеревьев с ключами [math]\leqslant x[/math] оказалось больше, чем поддеревьев с ключами [math]\gt x[/math]. Докажем для них логарифмическую асимптотику. Дерево на последнем уровне имеет высоту [math]H_{k}[/math] (она может быть не равна [math]1[/math], если мы придём в [math]x[/math]). Его мы передаем наверх и вставляем в поддерево высотой [math]H_{k-1}[/math]. [math]H_{k} \leqslant H_{k-1}[/math], так как разница высот поддеревьев у любой вершины не больше [math]1[/math], и мы при переходе от [math]H_{k}[/math] к [math]H_{k-1}[/math] поднимаемся как минимум на одну вершину вверх. Слияние этих поддеревьев мы выполним за [math]H_{k-1} - H_{k}[/math], получим в итоге дерево высоты не большей, чем [math]H_{k-1}[/math]. Его мы передадим наверх, поэтому в следующий раз слияние будет выполнено за [math]H_{k-2} - H_{k - 1}[/math] и так далее. Таким образом мы получим [math](H - H_{1}) + (H_{1} - H_{2}) + (H_{2} - H_{3}) + \cdots + (H_{k - 1} - H_{k}) = H - H_{k} = O(\log{n})[/math].

Итоговая асимптотика алгоритма — [math]O(\log{n})[/math].

АВЛ-дерево с O(1) бит в каждом узле[править]

Идея[править]

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

Операции[править]

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

Операция удаления
Если вершина — лист, то просто удалим её, иначе найдём ближайшую по значению вершину [math]a[/math], поменяем ее местами с удаляемой вершиной и удалим. От удалённой вершины будем подниматься вверх к корню и пересчитывать фактор баланса вершин. Если мы поднялись в вершину [math]i[/math] из левого поддерева, то фактор баланса уменьшается на единицу, если из правого, то увеличивается на единицу. Если мы пришли в вершину и её баланс стал равным [math]1[/math] или [math]-1[/math], то это значит, что высота поддерева не изменилась, и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс вершины [math]a[/math], в которую мы собираемся идти из ее левого поддерева, равен [math]-1[/math], то делается поворот для этой вершины [math]a[/math]. Аналогично делаем поворот, если баланс вершины [math]a[/math], в которую мы идем из ее правого поддерева, равен [math]1[/math]. Если в результате изменения узла, фактор баланса стал равен нулю, то подъём продолжается, иначе останавливается.

Балансировка[править]

Опишем операции балансировки, а именно малый левый поворот, большой левый поворот и случаи их возникновения. Балансировка нам нужна для операций добавления и удаления узла. Для исправления факторов баланса, достаточно знать факторы баланса двух(в случае большого поворота — трех) вершин перед поворотом, и исправить значения этих же вершин после поворота. Обозначим фактор баланса вершины [math]i[/math] как [math]balance[i][/math]. Операции поворота делаются на том шаге, когда мы находимся в правом сыне вершины [math]a[/math], если мы производим операцию добавления, и в левом сыне, если мы производим операцию удаления. Вычисления производим заранее, чтобы не допустить значения [math]2[/math] или [math]-2[/math] в вершине [math]a[/math]. На каждой иллюстрации изображен один случай высот поддеревьев. Нетрудно убедиться, что в остальных случаях всё тоже будет корректно.

Тип вращения Иллюстрация Факторы балансов до вращения Факторы балансов после вращения
Малое левое вращение Avl u1.jpg

1 вариант: [math]balance[a] = -1[/math] и [math]balance[b] = -1[/math]


2 вариант: [math]balance[a] = -1[/math] и [math]balance[b] = 0[/math]

1 вариант: [math]balance[a] = 0[/math] и [math]balance[b] = 0[/math]


2 вариант: [math]balance[a] = -1[/math] и [math]balance[b] = 1[/math]

Большое левое вращение Avl u2.jpg

1 вариант: [math]balance[a] = -1[/math] , [math]balance[b] = 1[/math] и [math]balance[c] = 1[/math]


2 вариант: [math]balance[a] = -1[/math], [math]balance[b] = 1[/math] и [math]balance[c] = -1[/math]


3 вариант: [math]balance[a] = -1[/math], [math]balance[b] = 1[/math] и [math]balance[c] = 0[/math]

1 вариант: [math]balance[a] = 0[/math], [math]balance[b] = -1[/math] и [math]balance[c] = 0[/math]


2 вариант: [math]balance[a] = 1[/math], [math]balance[b] = 0[/math] и [math]balance[c] = 0[/math]


3 вариант: [math]balance[a] = 0[/math], [math]balance[b] = 0[/math] и [math]balance[c] = 0[/math]

Примеры[править]

Ниже приведены примеры добавления и удаления вершины с подписанными изменениями факторов баланса каждой вершины.

Добавление
Удаление

См. также[править]

Источники информации[править]