http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=217.71.235.207&*Викиконспекты - Вклад участника [ru]2026-05-19T16:51:00ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&diff=47625АВЛ-дерево2015-06-05T16:45:40Z<p>217.71.235.207: </p>
<hr />
<div>'''АВЛ-дерево''' (англ. ''AVL-Tree'') {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.<br />
<br />
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.<br />
<br />
== Высота дерева ==<br />
{{Теорема <br />
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.<br />
||proof=<br />
<br />
Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.<br />
<br />
{{Лемма<br />
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи. <br />
|proof=<br />
Если <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> докажем по индукции. <br />
<br />
База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>. <br />
<br />
Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно. <br />
<br />
Тогда <tex>m_{h+1} = m_h + m_{h-1} + 1 = F_{h+2} - 1 + F_{h+1} - 1 + 1 = F_{h+3} - 1</tex>. <br />
<br />
Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.<br />
}}<br />
<br />
<br />
<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \dfrac{ \sqrt{5}+1}{2}</tex>. То есть<br />
<br />
<tex>n \geqslant \varphi^{h}</tex><br />
<br />
Логарифмируя по основанию <tex>\varphi</tex>, получаем<br />
<br />
<tex>\log_{\varphi}n \geqslant h</tex><br />
<br />
Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.<br />
}}<br />
<br />
== Балансировка ==<br />
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \leqslant 1</tex>, иначе ничего не меняет.<br />
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex><br />
<br />
Для балансировки вершины используются один из 4 типов вращений:<br />
<br />
{| border="1" cellpadding="5" cellspacing="0"<br />
!Тип вращения<br />
!Иллюстрация<br />
!Когда используется<br />
!Расстановка балансов<br />
|-<br />
|'''Малое левое вращение''' (''Small left rotation'')<br />
| [[Файл:avl_u1.jpg|2000x200px]] <br />
|<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex><br />
<br />
<br />
<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex><br />
|-<br />
|'''Большое левое вращение''' (англ. Big left rotation'')<br />
| [[Файл:avl_u2.jpg|2000x200px]]<br />
|<br />
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
|}<br />
Малый левый поворот:<br />
rotateleft(node a) {<br />
node b = a.right<br />
a.right = b.left<br />
b.left = a<br />
fixheight(a)<br />
fixheight(b)<br />
}<br />
Большой правый поворот пишется проще:<br />
bigrotateleft(node a) {<br />
rotateright(a.right)<br />
rotateleft(a)<br />
}<br />
Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению.<br />
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на <tex>1</tex> и не может увеличиться.<br />
<br />
Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.<br />
<br />
== Операции ==<br />
=== Добавление вершины ===<br />
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным <tex>1</tex> или <tex>-1</tex>, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным <tex>2</tex> или <tex>-2</tex>, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.<br />
<br />
Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.<br />
<br />
=== Удаление вершины ===<br />
Для простоты опишем рекурсивный алгоритм удаления.<br />
Если вершина {{---}} лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <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>, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.<br />
<br />
В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.<br />
<br />
=== Поиск вершины, минимум/максимум в дереве, etc. ===<br />
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.<br />
===Слияние двух AVL-деревьев===<br />
<br />
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \leqslant h(T_2)</tex>. <br />
<br />
В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.<br />
<br />
Дерево <tex>T_1</tex> и <tex>T_2</tex> до слияния<br />
<br />
<br />
[[File:avl_u3.jpg|340px]]<br />
<br />
Дерево <tex>T_2</tex> после слияния<br />
<br />
<br />
[[File:avl_u4.jpg|300px]]<br />
<br />
===Алгоритм разделения AVL-дерева на два===<br />
====Алгоритм первый====<br />
Пусть у нас есть дерево <tex>T</tex>. Мы должны разбить его на два дерева <tex>T_{1}</tex> и <tex>T_{2}</tex> такие, что <tex>T_{1} \leqslant x</tex> и <tex>x < T_{2}</tex>.<br />
<br />
Предположим, что корень нашего дерева <tex>\leqslant x</tex>, в таком случае все левое поддерево вместе с корнем после разделения отойдет в дерево <tex>T_{1}</tex>. Тогда рекурсивно спускаемся в правое поддерево и там проверяем это условие (так как часть правого поддерева тоже может содержать ключи <tex>\leqslant x</tex>). Если же корень оказался <tex>> x</tex>, то мы спускаемся той же рекурсией, но только в левое поддерево и ищем там.<br />
<br />
Пусть мы пришли в поддерево <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> (по ссылке, которую мы ранее запомнили) и обработать его.<br />
<br />
Если мы пришли в поддерево <tex>Q</tex>, корень которого <tex>> x</tex>, совершаем аналогичные действия: делаем NULL'ами ссылки на корень <tex>Q</tex>, запоминая ссылку на его левое поддерево. Делаем новую вершину со значением бывшего корня левым листом самой левой вершины <tex>Q</tex> и запускаем балансировку. Объединяем полученное АВЛ-дерево с уже построенным ранее <tex>T_{2}</tex> аналогичным первому случаю способом, только теперь мы ищем самое левое поддерево <tex>T_{2}</tex>.<br />
<br />
Рассмотри пример (рис. 1). Цветом выделены поддеревья, которые после разделения должны отойти в дерево <tex>T_{1}</tex>. <tex>x = 76</tex>.<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:AVL.jpg|thumb|left|525px|Рис. 1. Разделение АВЛ-дерева на два.]]<br />
|}<br />
<br />
Корень дерева <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).<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:АВВЛ2.jpg|thumb|left|525px|Рис. 2. Создание T'.]]<br />
|}<br />
{| cellpadding="2"<br />
| || [[Файл:AVL3.jpg|thumb|left|1050px|Рис. 3. Объединение T' и T1.]]<br />
|}<br />
<br />
Далее действуем по алгоритму и в итоге получаем (рис. 4):<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:End.jpg|thumb|left|525px|Рис. 4. АВЛ-деревья после разделения.]]<br />
|}<br />
<br />
Данный алгоритм имеет сложность <tex>O(\log^{2} n)</tex>.<br />
<br />
====Алгоритм второй====<br />
Рассмотрим решение, которое имеет сложность <tex>O(\log{n})</tex>.<br />
<br />
Вернемся к примеру (рис. 1). Теперь рекурсивно спустимся вниз и оттуда будем строить деревья <tex>T_{1}</tex> и <tex>T_{2}</tex>, передавая наверх корректные АВЛ-деревья. То есть для рис. 1 первым в дерево <tex>T_{1}</tex> придет вершина <tex>75</tex> с левым поддеревом (выделено светло-зеленым цветом), так как это корректное АВЛ-дерево, оно же и вернется из рекурсии. Далее мы попадем в вершину со значением <tex>70</tex> и должны слить ее и ее левое поддерево (выделено светло-синим) с тем, что нам пришло. И сделать это нужно так, чтобы передать наверх корректное АВЛ-дерево. Будем действовать по такому алгоритму, пока не дойдем до вершины.<br />
<br />
Пусть мы пришли в поддерево <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>, все аналогично.<br />
<br />
Разберем пример на рис. 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)<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:Ex.jpg|thumb|left|525px|Рис. 5.]]<br />
|}<br />
<br />
После мы поднимемся в вершину с ключом <tex>80</tex>. Она с правым поддеревом отойдет в дерево <tex>T_{2}</tex> (рис. 6). <br />
<br />
{| cellpadding="2"<br />
| || [[Файл:Ex2am.jpg|thumb|left|525px|Рис. 6.]]<br />
|}<br />
<br />
И на последней итерации мы поднимемся в корень дерева с ключом <tex>50</tex>, он с левым поддеревом отойдет в дерево <tex>T_{1}</tex>, после чего алгоритм завершится.<br />
<br />
Пусть поддеревьев с ключами <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>.<br />
<br />
Итоговая асимптотика алгоритма {{---}} <tex>O(\log{n})</tex>.<br />
<br />
== См. также ==<br />
* [[Splay-дерево]]<br />
* [[Красно-черное дерево]]<br />
* [[2-3 дерево]]<br />
<br />
== Источники информации ==<br />
* [http://habrahabr.ru/post/150732/ Habrahabr {{---}} АВЛ-деревья]<br />
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория:Деревья поиска]]<br />
[[Категория:Структуры данных]]</div>217.71.235.207http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&diff=47624АВЛ-дерево2015-06-05T16:42:32Z<p>217.71.235.207: /* Удаление вершины */</p>
<hr />
<div>'''АВЛ-дерево''' (англ. ''AVL-Tree'') {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.<br />
<br />
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.<br />
<br />
== Высота дерева ==<br />
{{Теорема <br />
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.<br />
||proof=<br />
<br />
Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.<br />
<br />
{{Лемма<br />
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи. <br />
|proof=<br />
Если <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> докажем по индукции. <br />
<br />
База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>. <br />
<br />
Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно. <br />
<br />
Тогда <tex>m_{h+1} = m_h + m_{h-1} + 1 = F_{h+2} - 1 + F_{h+1} - 1 + 1 = F_{h+3} - 1</tex>. <br />
<br />
Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.<br />
}}<br />
<br />
<br />
<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \dfrac{ \sqrt{5}+1}{2}</tex>. То есть<br />
<br />
<tex>n \geqslant \varphi^{h}</tex><br />
<br />
Логарифмируя по основанию <tex>\varphi</tex>, получаем<br />
<br />
<tex>\log_{\varphi}n \geqslant h</tex><br />
<br />
Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.<br />
}}<br />
<br />
== Балансировка ==<br />
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \leqslant 1</tex>, иначе ничего не меняет.<br />
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex><br />
<br />
Для балансировки вершины используются один из 4 типов вращений:<br />
<br />
{| border="1" cellpadding="5" cellspacing="0"<br />
!Тип вращения<br />
!Иллюстрация<br />
!Когда используется<br />
!Расстановка балансов<br />
|-<br />
|'''Малое левое вращение''' (''Small left rotation'')<br />
| [[Файл:avl_u1.jpg|2000x200px]] <br />
|<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex><br />
<br />
<br />
<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex><br />
|-<br />
|'''Большое левое вращение''' (англ. Big left rotation'')<br />
| [[Файл:avl_u2.jpg|2000x200px]]<br />
|<br />
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
|}<br />
Малый левый поворот:<br />
rotateleft(node a) {<br />
node b = a.right<br />
a.right = b.left<br />
b.left = a<br />
fixheight(a)<br />
fixheight(b)<br />
}<br />
Большой правый поворот пишется проще:<br />
bigrotateleft(node a) {<br />
rotateright(a.right)<br />
rotateleft(a)<br />
}<br />
Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению.<br />
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на <tex>1</tex> и не может увеличиться.<br />
<br />
Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.<br />
<br />
== Операции ==<br />
=== Добавление вершины ===<br />
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным <tex>1</tex> или <tex>-1</tex>, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным <tex>2</tex> или <tex>-2</tex>, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.<br />
<br />
Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.<br />
<br />
=== Удаление вершины ===<br />
Для простоты опишем рекурсивный алгоритм удаления.<br />
Если вершина {{---}} лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <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>, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.<br />
<br />
В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.<br />
<br />
=== Поиск вершины, минимум/максимум в дереве, etc. ===<br />
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.<br />
===Слияние двух AVL-деревьев===<br />
<br />
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \leqslant h(T_2)</tex>. <br />
<br />
В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.<br />
<br />
Дерево <tex>T_1</tex> и <tex>T_2</tex> до слияния<br />
<br />
<br />
[[File:avl_u3.jpg|340px]]<br />
<br />
Дерево <tex>T_2</tex> после слияния<br />
<br />
<br />
[[File:avl_u4.jpg|300px]]<br />
<br />
===Алгоритм разделения AVL-дерева на два===<br />
====Алгоритм первый====<br />
Пусть у нас есть дерево <tex>T</tex>. Мы должны разбить его на два дерева <tex>T_{1}</tex> и <tex>T_{2}</tex> такие, что <tex>T_{1} \leqslant x</tex> и <tex>x < T_{2}</tex>.<br />
<br />
Предположим, что корень нашего дерева <tex>\leqslant x</tex>, в таком случае все левое поддерево вместе с корнем после разделения отойдет в дерево <tex>T_{1}</tex>. Тогда рекурсивно спускаемся в правое поддерево и там проверяем это условие (так как часть правого поддерева тоже может содержать ключи <tex>\leqslant x</tex>). Если же корень оказался <tex>> x</tex>, то мы спускаемся той же рекурсией, но только в левое поддерево и ищем там.<br />
<br />
Пусть мы пришли в поддерево <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> (по ссылке, которую мы ранее запомнили) и обработать его.<br />
<br />
Если мы пришли в поддерево <tex>Q</tex>, корень которого <tex>> x</tex>, совершаем аналогичные действия: делаем NULL'ами ссылки на корень <tex>Q</tex>, запоминая ссылку на его левое поддерево. Делаем новую вершину со значением бывшего корня левым листом самой левой вершины <tex>Q</tex> и запускаем балансировку. Объединяем полученное АВЛ-дерево с уже построенным ранее <tex>T_{2}</tex> аналогичным первому случаю способом, только теперь мы ищем самое левое поддерево <tex>T_{2}</tex>.<br />
<br />
Рассмотри пример (рис. 1). Цветом выделены поддеревья, которые после разделения должны отойти в дерево <tex>T_{1}</tex>. <tex>x = 76</tex>.<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:AVL.jpg|thumb|left|525px|Рис. 1. Разделение АВЛ-дерева на два.]]<br />
|}<br />
<br />
Корень дерева <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).<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:АВВЛ2.jpg|thumb|left|525px|Рис. 2. Создание T'.]]<br />
|}<br />
{| cellpadding="2"<br />
| || [[Файл:AVL3.jpg|thumb|left|1050px|Рис. 3. Объединение T' и T1.]]<br />
|}<br />
<br />
Далее действуем по алгоритму и в итоге получаем (рис. 4):<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:End.jpg|thumb|left|525px|Рис. 4. АВЛ-деревья после разделения.]]<br />
|}<br />
<br />
Данный алгоритм имеет сложность <tex>O(\log^{2} n)</tex>.<br />
<br />
====Алгоритм второй====<br />
Рассмотрим решение, которое имеет сложность <tex>O(\log{n})</tex>.<br />
<br />
Вернемся к примеру (рис. 1). Теперь рекурсивно спустимся вниз и оттуда будем строить деревья <tex>T_{1}</tex> и <tex>T_{2}</tex>, передавая наверх корректные АВЛ-деревья. То есть для рис. 1 первым в дерево <tex>T_{1}</tex> придет вершина <tex>75</tex> с левым поддеревом (выделено светло-зеленым цветом), так как это корректное АВЛ-дерево, оно же и вернется из рекурсии. Далее мы попадем в вершину со значением <tex>70</tex> и должны слить ее и ее левое поддерево (выделено светло-синим) с тем, что нам пришло. И сделать это нужно так, чтобы передать наверх корректное АВЛ-дерево. Будем действовать по такому алгоритму, пока не дойдем до вершины.<br />
<br />
Пусть мы пришли в поддерево <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>, все аналогично.<br />
<br />
Разберем пример на рис. 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)<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:Ex.jpg|thumb|left|525px|Рис. 5.]]<br />
|}<br />
<br />
После мы поднимемся в вершину с ключом <tex>80</tex>. Она с правым поддеревом отойдет в дерево <tex>T_{2}</tex> (рис. 6). <br />
<br />
{| cellpadding="2"<br />
| || [[Файл:Ex2am.jpg|thumb|left|525px|Рис. 6.]]<br />
|}<br />
<br />
И на последней итерации мы поднимемся в корень дерева с ключом <tex>50</tex>, он с левым поддеревом отойдет в дерево <tex>T_{1}</tex>, после чего алгоритм завершится.<br />
<br />
Пусть поддеревьев с ключами <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>.<br />
<br />
Итоговая асимптотика алгоритма {{---}} <tex>O(\log{n})</tex>.<br />
== Источники информации ==<br />
* [http://habrahabr.ru/post/150732/ Habrahabr {{---}} АВЛ-деревья]<br />
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория:Деревья поиска]]<br />
[[Категория:Структуры данных]]</div>217.71.235.207http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&diff=47622АВЛ-дерево2015-06-05T16:26:12Z<p>217.71.235.207: </p>
<hr />
<div>'''АВЛ-дерево''' (англ. ''AVL-Tree'') {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.<br />
<br />
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.<br />
<br />
== Высота дерева ==<br />
{{Теорема <br />
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.<br />
||proof=<br />
<br />
Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.<br />
<br />
{{Лемма<br />
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи. <br />
|proof=<br />
Если <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> докажем по индукции. <br />
<br />
База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>. <br />
<br />
Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно. <br />
<br />
Тогда <tex>m_{h+1} = m_h + m_{h-1} + 1 = F_{h+2} - 1 + F_{h+1} - 1 + 1 = F_{h+3} - 1</tex>. <br />
<br />
Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.<br />
}}<br />
<br />
<br />
<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \dfrac{ \sqrt{5}+1}{2}</tex>. То есть<br />
<br />
<tex>n \geqslant \varphi^{h}</tex><br />
<br />
Логарифмируя по основанию <tex>\varphi</tex>, получаем<br />
<br />
<tex>\log_{\varphi}n \geqslant h</tex><br />
<br />
Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.<br />
}}<br />
<br />
== Балансировка ==<br />
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \leqslant 1</tex>, иначе ничего не меняет.<br />
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex><br />
<br />
Для балансировки вершины используются один из 4 типов вращений:<br />
<br />
{| border="1" cellpadding="5" cellspacing="0"<br />
!Тип вращения<br />
!Иллюстрация<br />
!Когда используется<br />
!Расстановка балансов<br />
|-<br />
|'''Малое левое вращение''' (''Small left rotation'')<br />
| [[Файл:avl_u1.jpg|2000x200px]] <br />
|<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex><br />
<br />
<br />
<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex><br />
|-<br />
|'''Большое левое вращение''' (англ. Big left rotation'')<br />
| [[Файл:avl_u2.jpg|2000x200px]]<br />
|<br />
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
|}<br />
Малый левый поворот:<br />
rotateleft(node a) {<br />
node b = a.right<br />
a.right = b.left<br />
b.left = a<br />
fixheight(a)<br />
fixheight(b)<br />
}<br />
Большой правый поворот пишется проще:<br />
bigrotateleft(node a) {<br />
rotateright(a.right)<br />
rotateleft(a)<br />
}<br />
Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению.<br />
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на <tex>1</tex> и не может увеличиться.<br />
<br />
Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.<br />
<br />
== Операции ==<br />
=== Добавление вершины ===<br />
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным <tex>1</tex> или <tex>-1</tex>, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным <tex>2</tex> или <tex>-2</tex>, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.<br />
<br />
Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.<br />
<br />
=== Удаление вершины ===<br />
Для простоты опишем рекурсивный алгоритм удаления.<br />
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <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>, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.<br />
<br />
В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.<br />
<br />
=== Поиск вершины, минимум/максимум в дереве, etc. ===<br />
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.<br />
===Слияние двух AVL-деревьев===<br />
<br />
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \leqslant h(T_2)</tex>. <br />
<br />
В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.<br />
<br />
Дерево <tex>T_1</tex> и <tex>T_2</tex> до слияния<br />
<br />
<br />
[[File:avl_u3.jpg|340px]]<br />
<br />
Дерево <tex>T_2</tex> после слияния<br />
<br />
<br />
[[File:avl_u4.jpg|300px]]<br />
<br />
===Алгоритм разделения AVL-дерева на два===<br />
====Алгоритм первый====<br />
Пусть у нас есть дерево <tex>T</tex>. Мы должны разбить его на два дерева <tex>T_{1}</tex> и <tex>T_{2}</tex> такие, что <tex>T_{1} \leqslant x</tex> и <tex>x < T_{2}</tex>.<br />
<br />
Предположим, что корень нашего дерева <tex>\leqslant x</tex>, в таком случае все левое поддерево вместе с корнем после разделения отойдет в дерево <tex>T_{1}</tex>. Тогда рекурсивно спускаемся в правое поддерево и там проверяем это условие (так как часть правого поддерева тоже может содержать ключи <tex>\leqslant x</tex>). Если же корень оказался <tex>> x</tex>, то мы спускаемся той же рекурсией, но только в левое поддерево и ищем там.<br />
<br />
Пусть мы пришли в поддерево <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> (по ссылке, которую мы ранее запомнили) и обработать его.<br />
<br />
Если мы пришли в поддерево <tex>Q</tex>, корень которого <tex>> x</tex>, совершаем аналогичные действия: делаем NULL'ами ссылки на корень <tex>Q</tex>, запоминая ссылку на его левое поддерево. Делаем новую вершину со значением бывшего корня левым листом самой левой вершины <tex>Q</tex> и запускаем балансировку. Объединяем полученное АВЛ-дерево с уже построенным ранее <tex>T_{2}</tex> аналогичным первому случаю способом, только теперь мы ищем самое левое поддерево <tex>T_{2}</tex>.<br />
<br />
Рассмотри пример (рис. 1). Цветом выделены поддеревья, которые после разделения должны отойти в дерево <tex>T_{1}</tex>. <tex>x = 76</tex>.<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:AVL.jpg|thumb|left|525px|Рис. 1. Разделение АВЛ-дерева на два.]]<br />
|}<br />
<br />
Корень дерева <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).<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:АВВЛ2.jpg|thumb|left|525px|Рис. 2. Создание T'.]]<br />
|}<br />
{| cellpadding="2"<br />
| || [[Файл:AVL3.jpg|thumb|left|1050px|Рис. 3. Объединение T' и T1.]]<br />
|}<br />
<br />
Далее действуем по алгоритму и в итоге получаем (рис. 4):<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:End.jpg|thumb|left|525px|Рис. 4. АВЛ-деревья после разделения.]]<br />
|}<br />
<br />
Данный алгоритм имеет сложность <tex>O(\log^{2} n)</tex>.<br />
<br />
====Алгоритм второй====<br />
Рассмотрим решение, которое имеет сложность <tex>O(\log{n})</tex>.<br />
<br />
Вернемся к примеру (рис. 1). Теперь рекурсивно спустимся вниз и оттуда будем строить деревья <tex>T_{1}</tex> и <tex>T_{2}</tex>, передавая наверх корректные АВЛ-деревья. То есть для рис. 1 первым в дерево <tex>T_{1}</tex> придет вершина <tex>75</tex> с левым поддеревом (выделено светло-зеленым цветом), так как это корректное АВЛ-дерево, оно же и вернется из рекурсии. Далее мы попадем в вершину со значением <tex>70</tex> и должны слить ее и ее левое поддерево (выделено светло-синим) с тем, что нам пришло. И сделать это нужно так, чтобы передать наверх корректное АВЛ-дерево. Будем действовать по такому алгоритму, пока не дойдем до вершины.<br />
<br />
Пусть мы пришли в поддерево <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>, все аналогично.<br />
<br />
Разберем пример на рис. 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)<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:Ex.jpg|thumb|left|525px|Рис. 5.]]<br />
|}<br />
<br />
После мы поднимемся в вершину с ключом <tex>80</tex>. Она с правым поддеревом отойдет в дерево <tex>T_{2}</tex> (рис. 6). <br />
<br />
{| cellpadding="2"<br />
| || [[Файл:Ex2am.jpg|thumb|left|525px|Рис. 6.]]<br />
|}<br />
<br />
И на последней итерации мы поднимемся в корень дерева с ключом <tex>50</tex>, он с левым поддеревом отойдет в дерево <tex>T_{1}</tex>, после чего алгоритм завершится.<br />
<br />
Пусть поддеревьев с ключами <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>.<br />
<br />
Итоговая асимптотика алгоритма {{---}} <tex>O(\log{n})</tex>.<br />
== Источники информации ==<br />
* [http://habrahabr.ru/post/150732/ Habrahabr {{---}} АВЛ-деревья]<br />
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория:Деревья поиска]]<br />
[[Категория:Структуры данных]]</div>217.71.235.207http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&diff=47621АВЛ-дерево2015-06-05T16:24:01Z<p>217.71.235.207: </p>
<hr />
<div>'''АВЛ-дерево''' (англ. ''AVL-Tree'') {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.<br />
<br />
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.<br />
<br />
== Высота дерева ==<br />
{{Теорема <br />
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.<br />
||proof=<br />
<br />
Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.<br />
<br />
{{Лемма<br />
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи. <br />
|proof=<br />
Если <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> докажем по индукции. <br />
<br />
База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>. <br />
<br />
Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно. <br />
<br />
Тогда <tex>m_{h+1} = m_h + m_{h-1} + 1 = F_{h+2} - 1 + F_{h+1} - 1 + 1 = F_{h+3} - 1</tex>. <br />
<br />
Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.<br />
}}<br />
<br />
<br />
<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \dfrac{ \sqrt{5}+1}{2}</tex>. То есть<br />
<br />
<tex>n \geqslant \varphi^{h}</tex><br />
<br />
Логарифмируя по основанию <tex>\varphi</tex>, получаем<br />
<br />
<tex>\log_{\varphi}n \geqslant h</tex><br />
<br />
Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.<br />
}}<br />
<br />
== Балансировка ==<br />
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \leqslant 1</tex>, иначе ничего не меняет.<br />
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex><br />
<br />
Для балансировки вершины используются один из 4 типов вращений:<br />
<br />
{| border="1" cellpadding="5" cellspacing="0"<br />
!Тип вращения<br />
!Иллюстрация<br />
!Когда используется<br />
!Расстановка балансов<br />
|-<br />
|'''Малое левое вращение''' (''Small left rotation'')<br />
| [[Файл:avl_u1.jpg|2000x200px]] <br />
|<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex><br />
<br />
<br />
<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex><br />
|-<br />
|'''Большое левое вращение''' (англ. Big left rotation'')<br />
| [[Файл:avl_u2.jpg|2000x200px]]<br />
|<br />
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
|}<br />
Малый левый поворот:<br />
rotateleft(node a) {<br />
node b = a.right<br />
a.right = b.left<br />
b.left = a<br />
fixheight(a)<br />
fixheight(b)<br />
}<br />
Большой правый поворот пишется проще:<br />
bigrotateleft(node a) {<br />
rotateright(a.right)<br />
rotateleft(a)<br />
}<br />
Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению.<br />
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на <tex>1</tex> и не может увеличиться.<br />
<br />
Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.<br />
<br />
== Операции ==<br />
=== Добавление вершины ===<br />
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным <tex>1</tex> или <tex>-1</tex>, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным <tex>2</tex> или <tex>-2</tex>, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.<br />
<br />
Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.<br />
<br />
=== Удаление вершины ===<br />
Для простоты опишем рекурсивный алгоритм удаления.<br />
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <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>, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.<br />
<br />
В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.<br />
<br />
=== Поиск вершины, минимум/максимум в дереве, etc. ===<br />
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.<br />
===Слияние двух AVL-деревьев===<br />
<br />
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \leqslant h(T_2)</tex>. <br />
<br />
В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.<br />
<br />
Дерево <tex>T_1</tex> и <tex>T_2</tex> до слияния<br />
<br />
<br />
[[File:avl_u3.jpg|340px]]<br />
<br />
Дерево <tex>T_2</tex> после слияния<br />
<br />
<br />
[[File:avl_u4.jpg|300px]]<br />
<br />
===Алгоритм разделения AVL-дерева на два===<br />
====Алгоритм первый====<br />
Пусть у нас есть дерево <tex>T</tex>. Мы должны разбить его на два дерева <tex>T_{1}</tex> и <tex>T_{2}</tex> такие, что <tex>T_{1} \leqslant x</tex> и <tex>x < T_{2}</tex>.<br />
<br />
Предположим, что корень нашего дерева <tex>\leqslant x</tex>, в таком случае все левое поддерево вместе с корнем после разделения отойдет в дерево <tex>T_{1}</tex>. Тогда рекурсивно спускаемся в правое поддерево и там проверяем это условие (так как часть правого поддерева тоже может содержать ключи <tex>\leqslant x</tex>). Если же корень оказался <tex>> x</tex>, то мы спускаемся той же рекурсией, но только в левое поддерево и ищем там.<br />
<br />
Пусть мы пришли в поддерево <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> (по ссылке, которую мы ранее запомнили) и обработать его.<br />
<br />
Если мы пришли в поддерево <tex>Q</tex>, корень которого <tex>> x</tex>, совершаем аналогичные действия: делаем NULL'ами ссылки на корень <tex>Q</tex>, запоминая ссылку на его левое поддерево. Делаем новую вершину со значением бывшего корня левым листом самой левой вершины <tex>Q</tex> и запускаем балансировку. Объединяем полученное АВЛ-дерево с уже построенным ранее <tex>T_{2}</tex> аналогичным первому случаю способом, только теперь мы ищем самое левое поддерево <tex>T_{2}</tex>.<br />
<br />
Рассмотри пример (рис. 1). Цветом выделены поддеревья, которые после разделения должны отойти в дерево <tex>T_{1}</tex>. <tex>x = 76</tex>.<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:AVL.jpg|thumb|left|525px|Рис. 1. Разделение АВЛ-дерева на два.]]<br />
|}<br />
<br />
Корень дерева <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).<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:АВВЛ2.jpg|thumb|left|525px|Рис. 2. Создание T'.]]<br />
|}<br />
{| cellpadding="2"<br />
| || [[Файл:AVL3.jpg|thumb|left|1050px|Рис. 3. Объединение T' и T1.]]<br />
|}<br />
<br />
Далее действуем по алгоритму и в итоге получаем (рис. 4):<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:End.jpg|thumb|left|525px|Рис. 4. АВЛ-деревья после разделения.]]<br />
|}<br />
<br />
Данный алгоритм имеет сложность <tex>O(\log^{2} n)</tex>.<br />
<br />
====Алгоритм второй====<br />
Рассмотрим решение, которое имеет сложность <tex>O(\log{n})</tex>.<br />
<br />
Вернемся к примеру (рис. 1). Теперь рекурсивно спустимся вниз и оттуда будем строить деревья <tex>T_{1}</tex> и <tex>T_{2}</tex>, передавая наверх корректные АВЛ-деревья. То есть для рис. 1 первым в дерево <tex>T_{1}</tex> придет вершина <tex>75</tex> с левым поддеревом (выделено светло-зеленым цветом), так как это корректное АВЛ-дерево, оно же и вернется из рекурсии. Далее мы попадем в вершину со значением <tex>70</tex> и должны слить ее и ее левое поддерево (выделено светло-синим) с тем, что нам пришло. И сделать это нужно так, чтобы передать наверх корректное АВЛ-дерево. Будем действовать по такому алгоритму, пока не дойдем до вершины.<br />
<br />
Пусть мы пришли в поддерево <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>, все аналогично.<br />
<br />
Разберем пример на рис. 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)<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:Ex.jpg|thumb|left|525px|Рис. 5.]]<br />
|}<br />
<br />
После мы поднимемся в вершину с ключом <tex>80</tex>. Она с правым поддеревом отойдет в дерево <tex>T_{2}</tex> (рис. 6). <br />
<br />
{| cellpadding="2"<br />
| || [[Файл:Ex2am.jpg|thumb|left|525px|Рис. 6.]]<br />
|}<br />
<br />
И на последней итерации мы поднимемся в корень дерева с ключом <tex>50</tex>, он с левым поддеревом отойдет в дерево <tex>T_{1}</tex>, после чего алгоритм завершится.<br />
<br />
Пусть поддеревьев с ключами <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>.<br />
<br />
Итоговая асимптотика алгоритма {{---}} <tex>O(\log{n})</tex>.<br />
== Источники информации ==<br />
* [http://habrahabr.ru/post/150732/ Habrahabr {{---}} АВЛ-деревья]<br />
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория:Деревья поиска]]</div>217.71.235.207http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&diff=47619АВЛ-дерево2015-06-05T16:22:10Z<p>217.71.235.207: /* Балансировка */</p>
<hr />
<div>'''АВЛ-дерево''' (''AVL-Tree'') {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.<br />
<br />
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.<br />
<br />
== Высота дерева ==<br />
{{Теорема <br />
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.<br />
||proof=<br />
<br />
Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.<br />
<br />
{{Лемма<br />
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи. <br />
|proof=<br />
Если <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> докажем по индукции. <br />
<br />
База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>. <br />
<br />
Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно. <br />
<br />
Тогда <tex>m_{h+1} = m_h + m_{h-1} + 1 = F_{h+2} - 1 + F_{h+1} - 1 + 1 = F_{h+3} - 1</tex>. <br />
<br />
Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.<br />
}}<br />
<br />
<br />
<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \dfrac{ \sqrt{5}+1}{2}</tex>. То есть<br />
<br />
<tex>n \geqslant \varphi^{h}</tex><br />
<br />
Логарифмируя по основанию <tex>\varphi</tex>, получаем<br />
<br />
<tex>\log_{\varphi}n \geqslant h</tex><br />
<br />
Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.<br />
}}<br />
<br />
== Балансировка ==<br />
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \leqslant 1</tex>, иначе ничего не меняет.<br />
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex><br />
<br />
Для балансировки вершины используются один из 4 типов вращений:<br />
<br />
{| border="1" cellpadding="5" cellspacing="0"<br />
!Тип вращения<br />
!Иллюстрация<br />
!Когда используется<br />
!Расстановка балансов<br />
|-<br />
|'''Малое левое вращение''' (''Small left rotation'')<br />
| [[Файл:avl_u1.jpg|2000x200px]] <br />
|<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex><br />
<br />
<br />
<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex><br />
|-<br />
|'''Большое левое вращение''' (Big left rotation'')<br />
| [[Файл:avl_u2.jpg|2000x200px]]<br />
|<br />
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
|}<br />
Малый левый поворот:<br />
rotateleft(node a) {<br />
node b = a.right<br />
a.right = b.left<br />
b.left = a<br />
fixheight(a)<br />
fixheight(b)<br />
}<br />
Большой правый поворот пишется проще:<br />
bigrotateleft(node a) {<br />
rotateright(a.right)<br />
rotateleft(a)<br />
}<br />
Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению.<br />
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на <tex>1</tex> и не может увеличиться.<br />
<br />
Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.<br />
<br />
== Операции ==<br />
=== Добавление вершины ===<br />
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным <tex>1</tex> или <tex>-1</tex>, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным <tex>2</tex> или <tex>-2</tex>, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.<br />
<br />
Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.<br />
<br />
=== Удаление вершины ===<br />
Для простоты опишем рекурсивный алгоритм удаления.<br />
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <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>, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.<br />
<br />
В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.<br />
<br />
=== Поиск вершины, минимум/максимум в дереве, etc. ===<br />
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.<br />
===Слияние двух AVL-деревьев===<br />
<br />
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \leqslant h(T_2)</tex>. <br />
<br />
В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.<br />
<br />
Дерево <tex>T_1</tex> и <tex>T_2</tex> до слияния<br />
<br />
<br />
[[File:avl_u3.jpg|340px]]<br />
<br />
Дерево <tex>T_2</tex> после слияния<br />
<br />
<br />
[[File:avl_u4.jpg|300px]]<br />
<br />
===Алгоритм разделения AVL-дерева на два===<br />
====Алгоритм первый====<br />
Пусть у нас есть дерево <tex>T</tex>. Мы должны разбить его на два дерева <tex>T_{1}</tex> и <tex>T_{2}</tex> такие, что <tex>T_{1} \leqslant x</tex> и <tex>x < T_{2}</tex>.<br />
<br />
Предположим, что корень нашего дерева <tex>\leqslant x</tex>, в таком случае все левое поддерево вместе с корнем после разделения отойдет в дерево <tex>T_{1}</tex>. Тогда рекурсивно спускаемся в правое поддерево и там проверяем это условие (так как часть правого поддерева тоже может содержать ключи <tex>\leqslant x</tex>). Если же корень оказался <tex>> x</tex>, то мы спускаемся той же рекурсией, но только в левое поддерево и ищем там.<br />
<br />
Пусть мы пришли в поддерево <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> (по ссылке, которую мы ранее запомнили) и обработать его.<br />
<br />
Если мы пришли в поддерево <tex>Q</tex>, корень которого <tex>> x</tex>, совершаем аналогичные действия: делаем NULL'ами ссылки на корень <tex>Q</tex>, запоминая ссылку на его левое поддерево. Делаем новую вершину со значением бывшего корня левым листом самой левой вершины <tex>Q</tex> и запускаем балансировку. Объединяем полученное АВЛ-дерево с уже построенным ранее <tex>T_{2}</tex> аналогичным первому случаю способом, только теперь мы ищем самое левое поддерево <tex>T_{2}</tex>.<br />
<br />
Рассмотри пример (рис. 1). Цветом выделены поддеревья, которые после разделения должны отойти в дерево <tex>T_{1}</tex>. <tex>x = 76</tex>.<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:AVL.jpg|thumb|left|525px|Рис. 1. Разделение АВЛ-дерева на два.]]<br />
|}<br />
<br />
Корень дерева <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).<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:АВВЛ2.jpg|thumb|left|525px|Рис. 2. Создание T'.]]<br />
|}<br />
{| cellpadding="2"<br />
| || [[Файл:AVL3.jpg|thumb|left|1050px|Рис. 3. Объединение T' и T1.]]<br />
|}<br />
<br />
Далее действуем по алгоритму и в итоге получаем (рис. 4):<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:End.jpg|thumb|left|525px|Рис. 4. АВЛ-деревья после разделения.]]<br />
|}<br />
<br />
Данный алгоритм имеет сложность <tex>O(\log^{2} n)</tex>.<br />
<br />
====Алгоритм второй====<br />
Рассмотрим решение, которое имеет сложность <tex>O(\log{n})</tex>.<br />
<br />
Вернемся к примеру (рис. 1). Теперь рекурсивно спустимся вниз и оттуда будем строить деревья <tex>T_{1}</tex> и <tex>T_{2}</tex>, передавая наверх корректные АВЛ-деревья. То есть для рис. 1 первым в дерево <tex>T_{1}</tex> придет вершина <tex>75</tex> с левым поддеревом (выделено светло-зеленым цветом), так как это корректное АВЛ-дерево, оно же и вернется из рекурсии. Далее мы попадем в вершину со значением <tex>70</tex> и должны слить ее и ее левое поддерево (выделено светло-синим) с тем, что нам пришло. И сделать это нужно так, чтобы передать наверх корректное АВЛ-дерево. Будем действовать по такому алгоритму, пока не дойдем до вершины.<br />
<br />
Пусть мы пришли в поддерево <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>, все аналогично.<br />
<br />
Разберем пример на рис. 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)<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:Ex.jpg|thumb|left|525px|Рис. 5.]]<br />
|}<br />
<br />
После мы поднимемся в вершину с ключом <tex>80</tex>. Она с правым поддеревом отойдет в дерево <tex>T_{2}</tex> (рис. 6). <br />
<br />
{| cellpadding="2"<br />
| || [[Файл:Ex2am.jpg|thumb|left|525px|Рис. 6.]]<br />
|}<br />
<br />
И на последней итерации мы поднимемся в корень дерева с ключом <tex>50</tex>, он с левым поддеревом отойдет в дерево <tex>T_{1}</tex>, после чего алгоритм завершится.<br />
<br />
Пусть поддеревьев с ключами <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>.<br />
<br />
Итоговая асимптотика алгоритма {{---}} <tex>O(\log{n})</tex>.<br />
== Источники информации ==<br />
* [http://habrahabr.ru/post/150732/ Habrahabr {{---}} АВЛ-деревья]<br />
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория:Деревья поиска]]</div>217.71.235.207http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&diff=47617АВЛ-дерево2015-06-05T16:17:09Z<p>217.71.235.207: /* Высота дерева */</p>
<hr />
<div>'''АВЛ-дерево''' (''AVL-Tree'') {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.<br />
<br />
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.<br />
<br />
== Высота дерева ==<br />
{{Теорема <br />
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.<br />
||proof=<br />
<br />
Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.<br />
<br />
{{Лемма<br />
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи. <br />
|proof=<br />
Если <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> докажем по индукции. <br />
<br />
База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>. <br />
<br />
Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно. <br />
<br />
Тогда <tex>m_{h+1} = m_h + m_{h-1} + 1 = F_{h+2} - 1 + F_{h+1} - 1 + 1 = F_{h+3} - 1</tex>. <br />
<br />
Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.<br />
}}<br />
<br />
<br />
<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \dfrac{ \sqrt{5}+1}{2}</tex>. То есть<br />
<br />
<tex>n \geqslant \varphi^{h}</tex><br />
<br />
Логарифмируя по основанию <tex>\varphi</tex>, получаем<br />
<br />
<tex>\log_{\varphi}n \geqslant h</tex><br />
<br />
Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.<br />
}}<br />
<br />
== Балансировка ==<br />
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \leqslant 1</tex>, иначе ничего не меняет.<br />
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex><br />
<br />
Для балансировки вершины используются один из 4 типов вращений:<br />
<br />
{| border="1" cellpadding="5" cellspacing="0"<br />
!Тип вращения<br />
!Иллюстрация<br />
!Когда используется<br />
!Расстановка балансов<br />
!Псевдокод<br />
|-<br />
|'''Малое левое вращение''' (''Small left rotation'')<br />
| [[Файл:avl_u1.jpg|2000x200px]] <br />
|<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex><br />
<br />
<br />
<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex><br />
|node* rotateleft(node* a) {<br />
node* b = a->right;<br />
a->right = b->left;<br />
b->left = a;<br />
fixheight(a);<br />
fixheight(b);<br />
return b;<br />
}<br />
|-<br />
|'''Большое левое вращение''' (Big left rotation'')<br />
| [[Файл:avl_u2.jpg|2000x200px]]<br />
|<br />
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
|node* bigrotateleft(node* a) {<br />
rotateright(a->right);<br />
rotateleft(a);<br />
return a;<br />
}<br />
|}<br />
Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению.<br />
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.<br />
<br />
Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.<br />
<br />
== Операции ==<br />
=== Добавление вершины ===<br />
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным <tex>1</tex> или <tex>-1</tex>, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным <tex>2</tex> или <tex>-2</tex>, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.<br />
<br />
Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.<br />
<br />
=== Удаление вершины ===<br />
Для простоты опишем рекурсивный алгоритм удаления.<br />
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <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>, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.<br />
<br />
В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.<br />
<br />
=== Поиск вершины, минимум/максимум в дереве, etc. ===<br />
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.<br />
===Слияние двух AVL-деревьев===<br />
<br />
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \leqslant h(T_2)</tex>. <br />
<br />
В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.<br />
<br />
Дерево <tex>T_1</tex> и <tex>T_2</tex> до слияния<br />
<br />
<br />
[[File:avl_u3.jpg|340px]]<br />
<br />
Дерево <tex>T_2</tex> после слияния<br />
<br />
<br />
[[File:avl_u4.jpg|300px]]<br />
<br />
===Алгоритм разделения AVL-дерева на два===<br />
====Алгоритм первый====<br />
Пусть у нас есть дерево <tex>T</tex>. Мы должны разбить его на два дерева <tex>T_{1}</tex> и <tex>T_{2}</tex> такие, что <tex>T_{1} \leqslant x</tex> и <tex>x < T_{2}</tex>.<br />
<br />
Предположим, что корень нашего дерева <tex>\leqslant x</tex>, в таком случае все левое поддерево вместе с корнем после разделения отойдет в дерево <tex>T_{1}</tex>. Тогда рекурсивно спускаемся в правое поддерево и там проверяем это условие (так как часть правого поддерева тоже может содержать ключи <tex>\leqslant x</tex>). Если же корень оказался <tex>> x</tex>, то мы спускаемся той же рекурсией, но только в левое поддерево и ищем там.<br />
<br />
Пусть мы пришли в поддерево <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> (по ссылке, которую мы ранее запомнили) и обработать его.<br />
<br />
Если мы пришли в поддерево <tex>Q</tex>, корень которого <tex>> x</tex>, совершаем аналогичные действия: делаем NULL'ами ссылки на корень <tex>Q</tex>, запоминая ссылку на его левое поддерево. Делаем новую вершину со значением бывшего корня левым листом самой левой вершины <tex>Q</tex> и запускаем балансировку. Объединяем полученное АВЛ-дерево с уже построенным ранее <tex>T_{2}</tex> аналогичным первому случаю способом, только теперь мы ищем самое левое поддерево <tex>T_{2}</tex>.<br />
<br />
Рассмотри пример (рис. 1). Цветом выделены поддеревья, которые после разделения должны отойти в дерево <tex>T_{1}</tex>. <tex>x = 76</tex>.<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:AVL.jpg|thumb|left|525px|Рис. 1. Разделение АВЛ-дерева на два.]]<br />
|}<br />
<br />
Корень дерева <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).<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:АВВЛ2.jpg|thumb|left|525px|Рис. 2. Создание T'.]]<br />
|}<br />
{| cellpadding="2"<br />
| || [[Файл:AVL3.jpg|thumb|left|1050px|Рис. 3. Объединение T' и T1.]]<br />
|}<br />
<br />
Далее действуем по алгоритму и в итоге получаем (рис. 4):<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:End.jpg|thumb|left|525px|Рис. 4. АВЛ-деревья после разделения.]]<br />
|}<br />
<br />
Данный алгоритм имеет сложность <tex>O(\log^{2} n)</tex>.<br />
<br />
====Алгоритм второй====<br />
Рассмотрим решение, которое имеет сложность <tex>O(\log{n})</tex>.<br />
<br />
Вернемся к примеру (рис. 1). Теперь рекурсивно спустимся вниз и оттуда будем строить деревья <tex>T_{1}</tex> и <tex>T_{2}</tex>, передавая наверх корректные АВЛ-деревья. То есть для рис. 1 первым в дерево <tex>T_{1}</tex> придет вершина <tex>75</tex> с левым поддеревом (выделено светло-зеленым цветом), так как это корректное АВЛ-дерево, оно же и вернется из рекурсии. Далее мы попадем в вершину со значением <tex>70</tex> и должны слить ее и ее левое поддерево (выделено светло-синим) с тем, что нам пришло. И сделать это нужно так, чтобы передать наверх корректное АВЛ-дерево. Будем действовать по такому алгоритму, пока не дойдем до вершины.<br />
<br />
Пусть мы пришли в поддерево <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>, все аналогично.<br />
<br />
Разберем пример на рис. 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)<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:Ex.jpg|thumb|left|525px|Рис. 5.]]<br />
|}<br />
<br />
После мы поднимемся в вершину с ключом <tex>80</tex>. Она с правым поддеревом отойдет в дерево <tex>T_{2}</tex> (рис. 6). <br />
<br />
{| cellpadding="2"<br />
| || [[Файл:Ex2am.jpg|thumb|left|525px|Рис. 6.]]<br />
|}<br />
<br />
И на последней итерации мы поднимемся в корень дерева с ключом <tex>50</tex>, он с левым поддеревом отойдет в дерево <tex>T_{1}</tex>, после чего алгоритм завершится.<br />
<br />
Пусть поддеревьев с ключами <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>.<br />
<br />
Итоговая асимптотика алгоритма {{---}} <tex>O(\log{n})</tex>.<br />
== Источники информации ==<br />
* [http://habrahabr.ru/post/150732/ Habrahabr {{---}} АВЛ-деревья]<br />
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория:Деревья поиска]]</div>217.71.235.207http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&diff=47404АВЛ-дерево2015-06-04T08:31:40Z<p>217.71.235.207: </p>
<hr />
<div>'''АВЛ-дерево''' (''AVL-Tree'') {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.<br />
<br />
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.<br />
<br />
== Высота дерева ==<br />
{{Теорема <br />
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.<br />
||proof=<br />
<br />
Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.<br />
<br />
{{Лемма<br />
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи. <br />
|proof=<br />
Если <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> докажем по индукции. <br />
<br />
База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>. <br />
<br />
Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно. <br />
<br />
Тогда <tex>m_{h+1} = m_h + m_{h-1} + 1 = F_{h+2} - 1 + F_{h+1} - 1 + 1 = F_{h+3} - 1</tex>. <br />
<br />
Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.<br />
}}<br />
<br />
<br />
<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть<br />
<br />
<tex>n \geqslant \varphi^{h}</tex><br />
<br />
Логарифмируя по основанию <tex>\varphi</tex>, получаем<br />
<br />
<tex>\log_{\varphi}n \geqslant h</tex><br />
<br />
Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.<br />
}}<br />
<br />
== Балансировка ==<br />
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \leqslant 1</tex>, иначе ничего не меняет.<br />
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex><br />
<br />
Для балансировки вершины используются один из 4 типов вращений:<br />
<br />
{| border="1" cellpadding="5" cellspacing="0"<br />
!Тип вращения<br />
!Иллюстрация<br />
!Когда используется<br />
!Расстановка балансов<br />
!Псевдокод<br />
|-<br />
|'''Малое левое вращение''' (''Small left rotation'')<br />
| [[Файл:avl_u1.jpg|2000x200px]] <br />
|<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex><br />
<br />
<br />
<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex><br />
|node* rotateleft(node* a) {<br />
node* b = a->right;<br />
a->right = b->left;<br />
b->left = a;<br />
fixheight(a);<br />
fixheight(b);<br />
return b;<br />
}<br />
|-<br />
|'''Большое левое вращение''' (Big left rotation'')<br />
| [[Файл:avl_u2.jpg|2000x200px]]<br />
|<br />
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
|node* bigrotateleft(node* a) {<br />
rotateright(a->right);<br />
rotateleft(a);<br />
return a;<br />
}<br />
|}<br />
Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению.<br />
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.<br />
<br />
Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.<br />
<br />
== Операции ==<br />
=== Добавление вершины ===<br />
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным <tex>1</tex> или <tex>-1</tex>, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным <tex>2</tex> или <tex>-2</tex>, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.<br />
<br />
Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.<br />
<br />
=== Удаление вершины ===<br />
Для простоты опишем рекурсивный алгоритм удаления.<br />
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <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>, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.<br />
<br />
В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.<br />
<br />
=== Поиск вершины, минимум/максимум в дереве, etc. ===<br />
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.<br />
===Слияние двух AVL-деревьев===<br />
<br />
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \leqslant h(T_2)</tex>. <br />
<br />
В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.<br />
<br />
Дерево <tex>T_1</tex> и <tex>T_2</tex> до слияния<br />
<br />
<br />
[[File:avl_u3.jpg|340px]]<br />
<br />
Дерево <tex>T_2</tex> после слияния<br />
<br />
<br />
[[File:avl_u4.jpg|300px]]<br />
<br />
===Алгоритм разделения AVL-дерева на два===<br />
====Алгоритм первый====<br />
Пусть у нас есть дерево <tex>T</tex>. Мы должны разбить его на два дерева <tex>T_{1}</tex> и <tex>T_{2}</tex> такие, что <tex>T_{1} \leqslant x</tex> и <tex>x < T_{2}</tex>.<br />
<br />
Предположим, что корень нашего дерева <tex>\leqslant x</tex>, в таком случае все левое поддерево вместе с корнем после разделения отойдет в дерево <tex>T_{1}</tex>. Тогда рекурсивно спускаемся в правое поддерево и там проверяем это условие (так как часть правого поддерева тоже может содержать ключи <tex>\leqslant x</tex>). Если же корень оказался <tex>> x</tex>, то мы спускаемся той же рекурсией, но только в левое поддерево и ищем там.<br />
<br />
Пусть мы пришли в поддерево <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> (по ссылке, которую мы ранее запомнили) и обработать его.<br />
<br />
Если мы пришли в поддерево <tex>Q</tex>, корень которого <tex>> x</tex>, совершаем аналогичные действия: делаем NULL'ами ссылки на корень <tex>Q</tex>, запоминая ссылку на его левое поддерево. Делаем новую вершину со значением бывшего корня левым листом самой левой вершины <tex>Q</tex> и запускаем балансировку. Объединяем полученное АВЛ-дерево с уже построенным ранее <tex>T_{2}</tex> аналогичным первому случаю способом, только теперь мы ищем самое левое поддерево <tex>T_{2}</tex>.<br />
<br />
Рассмотри пример (рис. 1). Цветом выделены поддеревья, которые после разделения должны отойти в дерево <tex>T_{1}</tex>. <tex>x = 76</tex>.<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:AVL.jpg|thumb|left|525px|Рис. 1. Разделение АВЛ-дерева на два.]]<br />
|}<br />
<br />
Корень дерева <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).<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:АВВЛ2.jpg|thumb|left|525px|Рис. 2. Создание T'.]]<br />
|}<br />
{| cellpadding="2"<br />
| || [[Файл:AVL3.jpg|thumb|left|1050px|Рис. 3. Объединение T' и T1.]]<br />
|}<br />
<br />
Далее действуем по алгоритму и в итоге получаем (рис. 4):<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:End.jpg|thumb|left|525px|Рис. 4. АВЛ-деревья после разделения.]]<br />
|}<br />
<br />
Данный алгоритм имеет сложность <tex>O(\log^{2} n)</tex>.<br />
<br />
====Алгоритм второй====<br />
Рассмотрим решение, которое имеет сложность <tex>O(\log{n})</tex>.<br />
<br />
Вернемся к примеру (рис. 1). Теперь рекурсивно спустимся вниз и оттуда будем строить деревья <tex>T_{1}</tex> и <tex>T_{2}</tex>, передавая наверх корректные АВЛ-деревья. То есть для рис. 1 первым в дерево <tex>T_{1}</tex> придет вершина <tex>75</tex> с левым поддеревом (выделено светло-зеленым цветом), так как это корректное АВЛ-дерево, оно же и вернется из рекурсии. Далее мы попадем в вершину со значением <tex>70</tex> и должны слить ее и ее левое поддерево (выделено светло-синим) с тем, что нам пришло. И сделать это нужно так, чтобы передать наверх корректное АВЛ-дерево. Будем действовать по такому алгоритму, пока не дойдем до вершины.<br />
<br />
Пусть мы пришли в поддерево <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>, все аналогично.<br />
<br />
Разберем пример на рис. 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)<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:Ex.jpg|thumb|left|525px|Рис. 5.]]<br />
|}<br />
<br />
После мы поднимемся в вершину с ключом <tex>80</tex>. Она с правым поддеревом отойдет в дерево <tex>T_{2}</tex> (рис. 6). <br />
<br />
{| cellpadding="2"<br />
| || [[Файл:Ex2am.jpg|thumb|left|525px|Рис. 6.]]<br />
|}<br />
<br />
И на последней итерации мы поднимемся в корень дерева с ключом <tex>50</tex>, он с левым поддеревом отойдет в дерево <tex>T_{1}</tex>, после чего алгоритм завершится.<br />
<br />
Пусть поддеревьев с ключами <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>.<br />
<br />
Итоговая асимптотика алгоритма {{---}} <tex>O(\log{n})</tex>.<br />
== Источники информации ==<br />
* [http://habrahabr.ru/post/150732/ Habrahabr {{---}} АВЛ-деревья]<br />
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория:Деревья поиска]]</div>217.71.235.207http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&diff=47403АВЛ-дерево2015-06-04T08:30:57Z<p>217.71.235.207: /* Балансировка */</p>
<hr />
<div>'''АВЛ-дерево''' (''AVL-Tree'') {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.<br />
<br />
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.<br />
<br />
== Высота дерева ==<br />
{{Теорема <br />
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.<br />
||proof=<br />
<br />
Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.<br />
<br />
{{Лемма<br />
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи. <br />
|proof=<br />
Если <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> докажем по индукции. <br />
<br />
База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>. <br />
<br />
Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно. <br />
<br />
Тогда <tex>m_{h+1} = m_h + m_{h-1} + 1 = F_{h+2} - 1 + F_{h+1} - 1 + 1 = F_{h+3} - 1</tex>. <br />
<br />
Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.<br />
}}<br />
<br />
<br />
<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть<br />
<br />
<tex>n \geqslant \varphi^{h}</tex><br />
<br />
Логарифмируя по основанию <tex>\varphi</tex>, получаем<br />
<br />
<tex>\log_{\varphi}n \geqslant h</tex><br />
<br />
Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.<br />
}}<br />
<br />
== Балансировка ==<br />
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \leqslant 1</tex>, иначе ничего не меняет.<br />
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex><br />
<br />
Для балансировки вершины используются один из 4 типов вращений:<br />
<br />
{| border="1" cellpadding="5" cellspacing="0"<br />
!Тип вращения<br />
!Иллюстрация<br />
!Когда используется<br />
!Расстановка балансов<br />
!Псевдокод<br />
|-<br />
|'''Малое левое вращение''' (''Small left rotation'')<br />
| [[Файл:avl_u1.jpg|2000x200px]] <br />
|<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex><br />
<br />
<br />
<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex><br />
|node* rotateleft(node* a) {<br />
node* b = a->right;<br />
a->right = b->left;<br />
b->left = a;<br />
fixheight(a);<br />
fixheight(b);<br />
return b;<br />
}<br />
|-<br />
|'''Большое левое вращение''' (Big left rotation'')<br />
| [[Файл:avl_u2.jpg|2000x200px]]<br />
|<br />
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
|node* bigrotateleft(node* a) {<br />
rotateright(a->right);<br />
rotateleft(a);<br />
return a;<br />
}<br />
|}<br />
Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению.<br />
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.<br />
<br />
Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.<br />
<br />
== Операции ==<br />
=== Добавление вершины ===<br />
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным <tex>1</tex> или <tex>-1</tex>, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным <tex>2</tex> или <tex>-2</tex>, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.<br />
<br />
Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.<br />
<br />
=== Удаление вершины ===<br />
Для простоты опишем рекурсивный алгоритм удаления.<br />
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <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>, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.<br />
<br />
В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.<br />
<br />
=== Поиск вершины, минимум/максимум в дереве, etc. ===<br />
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.<br />
===Слияние двух AVL-деревьев===<br />
<br />
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \leqslant h(T_2)</tex>. <br />
<br />
В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.<br />
<br />
Дерево <tex>T_1</tex> и <tex>T_2</tex> до слияния<br />
<br />
<br />
[[File:avl_u3.jpg|340px]]<br />
<br />
Дерево <tex>T_2</tex> после слияния<br />
<br />
<br />
[[File:avl_u4.jpg|300px]]<br />
<br />
===Алгоритм разделения AVL-дерева на два===<br />
====Алгоритм первый====<br />
Пусть у нас есть дерево <tex>T</tex>. Мы должны разбить его на два дерева <tex>T_{1}</tex> и <tex>T_{2}</tex> такие, что <tex>T_{1} \leqslant x</tex> и <tex>x < T_{2}</tex>.<br />
<br />
Предположим, что корень нашего дерева <tex>\leqslant x</tex>, в таком случае все левое поддерево вместе с корнем после разделения отойдет в дерево <tex>T_{1}</tex>. Тогда рекурсивно спускаемся в правое поддерево и там проверяем это условие (так как часть правого поддерева тоже может содержать ключи <tex>\leqslant x</tex>). Если же корень оказался <tex>> x</tex>, то мы спускаемся той же рекурсией, но только в левое поддерево и ищем там.<br />
<br />
Пусть мы пришли в поддерево <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> (по ссылке, которую мы ранее запомнили) и обработать его.<br />
<br />
Если мы пришли в поддерево <tex>Q</tex>, корень которого <tex>> x</tex>, совершаем аналогичные действия: делаем NULL'ами ссылки на корень <tex>Q</tex>, запоминая ссылку на его левое поддерево. Делаем новую вершину со значением бывшего корня левым листом самой левой вершины <tex>Q</tex> и запускаем балансировку. Объединяем полученное АВЛ-дерево с уже построенным ранее <tex>T_{2}</tex> аналогичным первому случаю способом, только теперь мы ищем самое левое поддерево <tex>T_{2}</tex>.<br />
<br />
Рассмотри пример (рис. 1). Цветом выделены поддеревья, которые после разделения должны отойти в дерево <tex>T_{1}</tex>. <tex>x = 76</tex>.<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:AVL.jpg|thumb|left|525px|Рис. 1. Разделение АВЛ-дерева на два.]]<br />
|}<br />
<br />
Корень дерева <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).<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:АВВЛ2.jpg|thumb|left|525px|Рис. 2. Создание T'.]]<br />
|}<br />
{| cellpadding="2"<br />
| || [[Файл:AVL3.jpg|thumb|left|1050px|Рис. 3. Объединение T' и T1.]]<br />
|}<br />
<br />
Далее действуем по алгоритму и в итоге получаем (рис. 4):<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:End.jpg|thumb|left|525px|Рис. 4. АВЛ-деревья после разделения.]]<br />
|}<br />
<br />
Данный алгоритм имеет сложность <tex>O(\log^{2} n)</tex>.<br />
<br />
====Алгоритм второй====<br />
Рассмотрим решение, которое имеет сложность <tex>O(\log{n})</tex>.<br />
<br />
Вернемся к примеру (рис. 1). Теперь рекурсивно спустимся вниз и оттуда будем строить деревья <tex>T_{1}</tex> и <tex>T_{2}</tex>, передавая наверх корректные АВЛ-деревья. То есть для рис. 1 первым в дерево <tex>T_{1}</tex> придет вершина <tex>75</tex> с левым поддеревом (выделено светло-зеленым цветом), так как это корректное АВЛ-дерево, оно же и вернется из рекурсии. Далее мы попадем в вершину со значением <tex>70</tex> и должны слить ее и ее левое поддерево (выделено светло-синим) с тем, что нам пришло. И сделать это нужно так, чтобы передать наверх корректное АВЛ-дерево. Будем действовать по такому алгоритму, пока не дойдем до вершины.<br />
<br />
Пусть мы пришли в поддерево <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>, все аналогично.<br />
<br />
Разберем пример на рис. 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)<br />
<br />
{| cellpadding="2"<br />
| || [[Файл:Ex.jpg|thumb|left|525px|Рис. 5.]]<br />
|}<br />
<br />
После мы поднимемся в вершину с ключом <tex>80</tex>. Она с правым поддеревом отойдет в дерево <tex>T_{2}</tex> (рис. 6). <br />
<br />
{| cellpadding="2"<br />
| || [[Файл:Ex2am.jpg|thumb|left|525px|Рис. 6.]]<br />
|}<br />
<br />
И на последней итерации мы поднимемся в корень дерева с ключом <tex>50</tex>, он с левым поддеревом отойдет в дерево <tex>T_{1}</tex>, после чего алгоритм завершится.<br />
<br />
Пусть поддеревьев с ключами <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>.<br />
<br />
Итоговая асимптотика алгоритма {{---}} <tex>O(\log{n})</tex>.<br />
<br />
== Ссылки ==<br />
* [http://habrahabr.ru/post/150732/ Habrahabr {{---}} АВЛ-деревья]<br />
== Источники информации ==<br />
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория:Деревья поиска]]</div>217.71.235.207http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&diff=46168АВЛ-дерево2015-05-10T05:41:44Z<p>217.71.235.207: /* Слияние двух AVL-деревьев */</p>
<hr />
<div>'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.<br />
<br />
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.<br />
<br />
== Высота дерева ==<br />
{{Теорема <br />
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.<br />
||proof=<br />
<br />
Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.<br />
<br />
{{Лемма<br />
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи. <br />
|proof=<br />
Если <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> докажем по индукции. <br />
<br />
База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>. <br />
<br />
Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно. <br />
<br />
Тогда <tex>m_{h+1} = m_h + m_{h-1} + 1 = F_{h+2} - 1 + F_{h+1} - 1 + 1 = F_{h+3} - 1</tex>. <br />
<br />
Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.<br />
}}<br />
<br />
<br />
<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть<br />
<br />
<tex>n \geqslant \varphi^{h}</tex><br />
<br />
Логарифмируя по основанию <tex>\varphi</tex>, получаем<br />
<br />
<tex>\log_{\varphi}n \geqslant h</tex><br />
<br />
Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.<br />
}}<br />
<br />
== Балансировка ==<br />
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \leqslant 1</tex>, иначе ничего не меняет.<br />
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex><br />
<br />
Для балансировки вершины используются один из 4 типов вращений:<br />
<br />
{| border="1" cellpadding="5" cellspacing="0"<br />
!Тип вращения<br />
!Иллюстрация<br />
!Когда используется<br />
!Расстановка балансов<br />
|-<br />
|'''Малое левое вращение'''<br />
| [[Файл:avl_u1.jpg|2000x200px]] <br />
|<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex><br />
<br />
<br />
<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex><br />
<br />
|-<br />
|'''Большое левое вращение'''<br />
| [[Файл:avl_u2.jpg|2000x200px]]<br />
|<br />
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
<br />
|}<br />
Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению.<br />
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.<br />
<br />
Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.<br />
<br />
== Операции ==<br />
=== Добавление вершины ===<br />
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным <tex>1</tex> или <tex>-1</tex>, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным <tex>2</tex> или <tex>-2</tex>, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.<br />
<br />
Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.<br />
<br />
=== Удаление вершины ===<br />
Для простоты опишем рекурсивный алгоритм удаления.<br />
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <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>, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.<br />
<br />
В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.<br />
<br />
=== Поиск вершины, минимум/максимум в дереве, etc. ===<br />
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.<br />
===Слияние двух AVL-деревьев===<br />
<br />
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \leqslant h(T_2)</tex>. <br />
<br />
В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.<br />
<br />
Дерево <tex>T_1</tex> и <tex>T_2</tex> до слияния<br />
<br />
<br />
[[File:avl_u3.jpg|340px]]<br />
<br />
Дерево <tex>T_2</tex> после слияния<br />
<br />
<br />
[[File:avl_u4.jpg|300px]]<br />
<br />
== Источники информации ==<br />
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория:Деревья поиска]]</div>217.71.235.207http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&diff=46167АВЛ-дерево2015-05-10T05:41:21Z<p>217.71.235.207: /* Балансировка */</p>
<hr />
<div>'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.<br />
<br />
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.<br />
<br />
== Высота дерева ==<br />
{{Теорема <br />
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.<br />
||proof=<br />
<br />
Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.<br />
<br />
{{Лемма<br />
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи. <br />
|proof=<br />
Если <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> докажем по индукции. <br />
<br />
База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>. <br />
<br />
Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно. <br />
<br />
Тогда <tex>m_{h+1} = m_h + m_{h-1} + 1 = F_{h+2} - 1 + F_{h+1} - 1 + 1 = F_{h+3} - 1</tex>. <br />
<br />
Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.<br />
}}<br />
<br />
<br />
<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть<br />
<br />
<tex>n \geqslant \varphi^{h}</tex><br />
<br />
Логарифмируя по основанию <tex>\varphi</tex>, получаем<br />
<br />
<tex>\log_{\varphi}n \geqslant h</tex><br />
<br />
Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.<br />
}}<br />
<br />
== Балансировка ==<br />
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \leqslant 1</tex>, иначе ничего не меняет.<br />
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex><br />
<br />
Для балансировки вершины используются один из 4 типов вращений:<br />
<br />
{| border="1" cellpadding="5" cellspacing="0"<br />
!Тип вращения<br />
!Иллюстрация<br />
!Когда используется<br />
!Расстановка балансов<br />
|-<br />
|'''Малое левое вращение'''<br />
| [[Файл:avl_u1.jpg|2000x200px]] <br />
|<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex><br />
<br />
<br />
<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex><br />
<br />
|-<br />
|'''Большое левое вращение'''<br />
| [[Файл:avl_u2.jpg|2000x200px]]<br />
|<br />
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
<br />
|}<br />
Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению.<br />
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.<br />
<br />
Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.<br />
<br />
== Операции ==<br />
=== Добавление вершины ===<br />
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным <tex>1</tex> или <tex>-1</tex>, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным <tex>2</tex> или <tex>-2</tex>, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.<br />
<br />
Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.<br />
<br />
=== Удаление вершины ===<br />
Для простоты опишем рекурсивный алгоритм удаления.<br />
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <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>, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.<br />
<br />
В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.<br />
<br />
=== Поиск вершины, минимум/максимум в дереве, etc. ===<br />
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.<br />
===Слияние двух AVL-деревьев===<br />
<br />
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>. <br />
<br />
В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.<br />
<br />
Дерево <tex>T_1</tex> и <tex>T_2</tex> до слияния<br />
<br />
<br />
[[File:avl_u3.jpg|340px]]<br />
<br />
Дерево <tex>T_2</tex> после слияния<br />
<br />
<br />
[[File:avl_u4.jpg|300px]]<br />
<br />
<br />
== Источники информации ==<br />
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория:Деревья поиска]]</div>217.71.235.207http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%B5%D1%80%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D1%81%D1%82%D0%B5%D0%BA&diff=46163Персистентный стек2015-05-09T12:07:04Z<p>217.71.235.207: /* Пример */ тикет 4-3</p>
<hr />
<div>== Эффективная реализация ==<br />
<br />
Попробуем решить задачу эффективнее. Заведем массив запросов, модифицирующих стек.<br><br />
У каждого элемента массива будет 2 поля: значение в вершине стека и индекс предыдущей версии стека.<br><br />
Тогда операции push и pop будут иметь следующий вид:<br><br />
* <tex> \mathrm{push}(i, x)</tex> {{---}} добавляет элемент х в стек с номером i, результирующий стек будет иметь номер <tex> n + 1 </tex>.<br />
function push(i : uint, x : T):<br />
s.top = s.top + 1;<br />
s[s.top].value = x;<br />
s[s.top].prev = i; <br />
* <tex>\mathrm{pop}(i)</tex> {{---}} возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.<br />
результирующий стек будет иметь номер <tex> n + 1 </tex>.<br />
T pop(i : uint):<br />
T k = s[i];<br />
k = s[k.prev];<br />
push(k.prev, k.value);<br />
<br />
== Пример ==<br />
<br />
* Пусть изначально у нас есть один пустой стек. Запишем его в массив.<br />
[[Файл:стек1.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|}<br />
<br />
<br />
* Далее выполним <tex>\mathrm{push}(1, 3)</tex>. Создается новая вершина со значением 3, ссылающаяся на 1-ую, помещаем ее во 2-ую ячейку массива:<br />
[[Файл:стек2.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|}<br />
<br />
<br />
* Аналогично выполним <tex>\mathrm{push}(2, 5)</tex>:<br />
[[Файл:стек3.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|5<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|2<br />
|}<br />
<br />
<br />
* Выполним <tex>\mathrm{pop}(3)</tex>. он возвращает 5 и копирует 2-ую вершину.<br />
[[Файл:стек4.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|5<br />
|3<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|2<br />
|1<br />
|}<br />
<br />
<br />
* Так будет выглядеть массив после последовательности операций <tex>\mathrm{push}(3, 6), \mathrm{push}(5, 1), \mathrm{pop}(4), \mathrm{pop}(5), \mathrm{push}(7, 9):</tex><br />
[[Файл:стек.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;5&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;6&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;7&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;8&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;9&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|5<br />
|3<br />
|6<br />
|1<br />
|<tex>null</tex><br />
|5<br />
|9<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|2<br />
|1<br />
|3<br />
|5<br />
|<tex>null</tex><br />
|2<br />
|7<br />
|}<br />
<br />
<br />
В итоге мы имеем доступ ко всем версиям стека за <tex>O(1)</tex> времени и <tex>O(n)</tex> памяти.<br />
<br />
== См. также==<br />
<br />
* [[Стек]]<br />
* [[Персистентный дек]]<br />
<br />
== Источники информации ==<br />
<br />
* [http://habrahabr.ru/blogs/algorithm/113585/ Habrahabr - Персистентный стек]<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
<br />
[[Категория: Амортизационный анализ]]</div>217.71.235.207http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%B5%D1%80%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D1%81%D1%82%D0%B5%D0%BA&diff=46161Персистентный стек2015-05-09T12:02:16Z<p>217.71.235.207: /* Эффективная реализация */</p>
<hr />
<div>== Эффективная реализация ==<br />
<br />
Попробуем решить задачу эффективнее. Заведем массив запросов, модифицирующих стек.<br><br />
У каждого элемента массива будет 2 поля: значение в вершине стека и индекс предыдущей версии стека.<br><br />
Тогда операции push и pop будут иметь следующий вид:<br><br />
* <tex> \mathrm{push}(i, x)</tex> {{---}} добавляет элемент х в стек с номером i, результирующий стек будет иметь номер <tex> n + 1 </tex>.<br />
function push(i : uint, x : T):<br />
s.top = s.top + 1;<br />
s[s.top].value = x;<br />
s[s.top].prev = i; <br />
* <tex>\mathrm{pop}(i)</tex> {{---}} возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.<br />
результирующий стек будет иметь номер <tex> n + 1 </tex>.<br />
T pop(i : uint):<br />
T k = s[i];<br />
k = s[k.prev];<br />
push(k.prev, k.value);<br />
<br />
== Пример ==<br />
<br />
* Пусть изначально у нас есть один пустой стек. Запишем его в массив.<br />
[[Файл:стек1.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|}<br />
<br />
<br />
* Далее выполним <tex>push(1, 3)</tex>. Создается новая вершина со значением 3, ссылающаяся на 1-ую, помещаем ее во 2-ую ячейку массива:<br />
[[Файл:стек2.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|}<br />
<br />
<br />
* Аналогично выполним <tex>push(2, 5)</tex>:<br />
[[Файл:стек3.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|5<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|2<br />
|}<br />
<br />
<br />
* Выполним <tex>pop(3)</tex>. он возвращает 5 и копирует 2-ую вершину.<br />
[[Файл:стек4.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|5<br />
|3<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|2<br />
|1<br />
|}<br />
<br />
<br />
* Так будет выглядеть массив после последовательности операций <tex>push(3, 6), push(5, 1), pop(4), pop(5), push(7, 9):</tex><br />
[[Файл:стек.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;5&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;6&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;7&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;8&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;9&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|5<br />
|3<br />
|6<br />
|1<br />
|<tex>null</tex><br />
|5<br />
|9<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|2<br />
|1<br />
|3<br />
|5<br />
|<tex>null</tex><br />
|2<br />
|7<br />
|}<br />
<br />
<br />
В итоге мы имеем доступ ко всем версиям стека за <tex>O(1)</tex> времени и <tex>O(n)</tex> памяти.<br />
<br />
<br />
<br />
== См. также==<br />
<br />
* [[Стек]]<br />
* [[Персистентный дек]]<br />
<br />
== Источники информации ==<br />
<br />
* [http://habrahabr.ru/blogs/algorithm/113585/ Habrahabr - Персистентный стек]<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
<br />
[[Категория: Амортизационный анализ]]</div>217.71.235.207http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%B5%D1%80%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D1%81%D1%82%D0%B5%D0%BA&diff=46160Персистентный стек2015-05-09T12:00:21Z<p>217.71.235.207: /* Эффективная реализация */</p>
<hr />
<div>== Эффективная реализация ==<br />
<br />
Попробуем решить задачу эффективнее. Заведем массив запросов, модифицирующих стек.<br><br />
У каждого элемента массива будет 2 поля: значение в вершине стека и индекс предыдущей версии стека.<br><br />
Тогда операции push и pop будут иметь следующий вид:<br><br />
* <tex>push(i, x)</tex> {{---}} добавляет элемент х в стек с номером i, результирующий стек будет иметь номер <tex> n + 1 </tex>.<br />
function push(i : uint, x : T):<br />
s.top = s.top + 1;<br />
s[s.top].value = x;<br />
s[s.top].prev = i; <br />
* <tex>pop(i)</tex> {{---}} возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.<br />
результирующий стек будет иметь номер <tex> n + 1 </tex>.<br />
T pop(i : uint):<br />
T k = s[i];<br />
k = s[k.prev];<br />
push(k.prev, k.value);<br />
<br />
== Пример ==<br />
<br />
* Пусть изначально у нас есть один пустой стек. Запишем его в массив.<br />
[[Файл:стек1.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|}<br />
<br />
<br />
* Далее выполним <tex>push(1, 3)</tex>. Создается новая вершина со значением 3, ссылающаяся на 1-ую, помещаем ее во 2-ую ячейку массива:<br />
[[Файл:стек2.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|}<br />
<br />
<br />
* Аналогично выполним <tex>push(2, 5)</tex>:<br />
[[Файл:стек3.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|5<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|2<br />
|}<br />
<br />
<br />
* Выполним <tex>pop(3)</tex>. он возвращает 5 и копирует 2-ую вершину.<br />
[[Файл:стек4.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|5<br />
|3<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|2<br />
|1<br />
|}<br />
<br />
<br />
* Так будет выглядеть массив после последовательности операций <tex>push(3, 6), push(5, 1), pop(4), pop(5), push(7, 9):</tex><br />
[[Файл:стек.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;5&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;6&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;7&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;8&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;9&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|5<br />
|3<br />
|6<br />
|1<br />
|<tex>null</tex><br />
|5<br />
|9<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|2<br />
|1<br />
|3<br />
|5<br />
|<tex>null</tex><br />
|2<br />
|7<br />
|}<br />
<br />
<br />
В итоге мы имеем доступ ко всем версиям стека за <tex>O(1)</tex> времени и <tex>O(n)</tex> памяти.<br />
<br />
<br />
<br />
== См. также==<br />
<br />
* [[Стек]]<br />
* [[Персистентный дек]]<br />
<br />
== Источники информации ==<br />
<br />
* [http://habrahabr.ru/blogs/algorithm/113585/ Habrahabr - Персистентный стек]<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
<br />
[[Категория: Амортизационный анализ]]</div>217.71.235.207http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%B5%D1%80%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D1%81%D1%82%D0%B5%D0%BA&diff=46159Персистентный стек2015-05-09T11:58:19Z<p>217.71.235.207: /* Эффективная реализация */</p>
<hr />
<div>== Эффективная реализация ==<br />
<br />
Попробуем решить задачу эффективнее. Заведем массив запросов, модифицирующих стек.<br><br />
У каждого элемента массива будет 2 поля: значение в вершине стека и индекс предыдущей версии стека.<br><br />
Тогда операции push и pop будут иметь следующий вид:<br><br />
* <tex>push(i, x)</tex> — добавляет элемент х в стек с номером i, результирующий стек будет иметь номер <tex> n + 1 </tex>.<br />
function push(i : uint, x : T):<br />
s.top = s.top + 1;<br />
s[s.top].value = x;<br />
s[s.top].prev = i; <br />
* <tex>pop(i)</tex> — возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.<br />
результирующий стек будет иметь номер <tex> n + 1 </tex>.<br />
T pop(i : uint):<br />
T k = s[i];<br />
k = s[k.prev];<br />
push(k.prev, k.value);<br />
<br />
== Пример ==<br />
<br />
* Пусть изначально у нас есть один пустой стек. Запишем его в массив.<br />
[[Файл:стек1.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|}<br />
<br />
<br />
* Далее выполним <tex>push(1, 3)</tex>. Создается новая вершина со значением 3, ссылающаяся на 1-ую, помещаем ее во 2-ую ячейку массива:<br />
[[Файл:стек2.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|}<br />
<br />
<br />
* Аналогично выполним <tex>push(2, 5)</tex>:<br />
[[Файл:стек3.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|5<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|2<br />
|}<br />
<br />
<br />
* Выполним <tex>pop(3)</tex>. он возвращает 5 и копирует 2-ую вершину.<br />
[[Файл:стек4.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|5<br />
|3<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|2<br />
|1<br />
|}<br />
<br />
<br />
* Так будет выглядеть массив после последовательности операций <tex>push(3, 6), push(5, 1), pop(4), pop(5), push(7, 9):</tex><br />
[[Файл:стек.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;5&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;6&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;7&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;8&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;9&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|5<br />
|3<br />
|6<br />
|1<br />
|<tex>null</tex><br />
|5<br />
|9<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|2<br />
|1<br />
|3<br />
|5<br />
|<tex>null</tex><br />
|2<br />
|7<br />
|}<br />
<br />
<br />
В итоге мы имеем доступ ко всем версиям стека за <tex>O(1)</tex> времени и <tex>O(n)</tex> памяти.<br />
<br />
<br />
<br />
== См. также==<br />
<br />
* [[Стек]]<br />
* [[Персистентный дек]]<br />
<br />
== Источники информации ==<br />
<br />
* [http://habrahabr.ru/blogs/algorithm/113585/ Habrahabr - Персистентный стек]<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
<br />
[[Категория: Амортизационный анализ]]</div>217.71.235.207http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%B5%D1%80%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D1%81%D1%82%D0%B5%D0%BA&diff=46158Персистентный стек2015-05-09T11:47:33Z<p>217.71.235.207: тикет 4-3</p>
<hr />
<div>== Эффективная реализация ==<br />
<br />
Попробуем решить задачу эффективнее. Заведем массив запросов, модифицирующих стек.<br><br />
У каждого элемента массива будет 2 поля: значение в вершине стека и индекс предыдущей версии стека.<br><br />
Тогда операции push и pop будут иметь следующий вид:<br><br />
* <tex>push(i, x)</tex> — добавляет элемент х в стек с номером i, результирующий стек будет иметь номер <tex> n + 1 </tex>.<br />
arr.push (x, i)<br />
* <tex>pop(i)</tex> — возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.<br />
результирующий стек будет иметь номер <tex> n + 1 </tex>.<br />
a = arr[прошлый элемент для i-ого];<br />
arr.push(a);<br />
<br />
== Пример ==<br />
<br />
* Пусть изначально у нас есть один пустой стек. Запишем его в массив.<br />
[[Файл:стек1.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|}<br />
<br />
<br />
* Далее выполним <tex>push(1, 3)</tex>. Создается новая вершина со значением 3, ссылающаяся на 1-ую, помещаем ее во 2-ую ячейку массива:<br />
[[Файл:стек2.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|}<br />
<br />
<br />
* Аналогично выполним <tex>push(2, 5)</tex>:<br />
[[Файл:стек3.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|5<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|2<br />
|}<br />
<br />
<br />
* Выполним <tex>pop(3)</tex>. он возвращает 5 и копирует 2-ую вершину.<br />
[[Файл:стек4.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|5<br />
|3<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|2<br />
|1<br />
|}<br />
<br />
<br />
* Так будет выглядеть массив после последовательности операций <tex>push(3, 6), push(5, 1), pop(4), pop(5), push(7, 9):</tex><br />
[[Файл:стек.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;5&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;6&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;7&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;8&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;9&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|5<br />
|3<br />
|6<br />
|1<br />
|<tex>null</tex><br />
|5<br />
|9<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|2<br />
|1<br />
|3<br />
|5<br />
|<tex>null</tex><br />
|2<br />
|7<br />
|}<br />
<br />
<br />
В итоге мы имеем доступ ко всем версиям стека за <tex>O(1)</tex> времени и <tex>O(n)</tex> памяти.<br />
<br />
<br />
<br />
== См. также==<br />
<br />
* [[Стек]]<br />
* [[Персистентный дек]]<br />
<br />
== Источники информации ==<br />
<br />
* [http://habrahabr.ru/blogs/algorithm/113585/ Habrahabr - Персистентный стек]<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
<br />
[[Категория: Амортизационный анализ]]</div>217.71.235.207http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%B5%D1%80%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D1%81%D1%82%D0%B5%D0%BA&diff=46157Персистентный стек2015-05-09T11:46:45Z<p>217.71.235.207: /* Ссылки */ тикет 4-3</p>
<hr />
<div>''Персистентными структурами данных'' называются структуры, хранящие все свои промежуточные версии.<br />
<br />
<br />
Рассмотрим такую структуру на примере [[стек|стека]].<br />
<br />
<br />
== Наивная реализация ==<br />
<br />
Самое простое и очевидное решение этой задачи — честное копирование стека при каждой операции. <br><br />
Очевидно, это не самое эффективное решение. Сложность одной операции составляет <tex>O(n)</tex> и количество требуемой памяти — <tex>O(n^2)</tex>.<br />
<br />
== Эффективная реализация ==<br />
<br />
Попробуем решить задачу эффективнее. Заведем массив запросов, модифицирующих стек.<br><br />
У каждого элемента массива будет 2 поля: значение в вершине стека и индекс предыдущей версии стека.<br><br />
Тогда операции push и pop будут иметь следующий вид:<br><br />
* <tex>push(i, x)</tex> — добавляет элемент х в стек с номером i, результирующий стек будет иметь номер <tex> n + 1 </tex>.<br />
arr.push (x, i)<br />
* <tex>pop(i)</tex> — возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.<br />
результирующий стек будет иметь номер <tex> n + 1 </tex>.<br />
a = arr[прошлый элемент для i-ого];<br />
arr.push(a);<br />
<br />
== Пример ==<br />
<br />
* Пусть изначально у нас есть один пустой стек. Запишем его в массив.<br />
[[Файл:стек1.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|}<br />
<br />
<br />
* Далее выполним <tex>push(1, 3)</tex>. Создается новая вершина со значением 3, ссылающаяся на 1-ую, помещаем ее во 2-ую ячейку массива:<br />
[[Файл:стек2.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|}<br />
<br />
<br />
* Аналогично выполним <tex>push(2, 5)</tex>:<br />
[[Файл:стек3.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|5<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|2<br />
|}<br />
<br />
<br />
* Выполним <tex>pop(3)</tex>. он возвращает 5 и копирует 2-ую вершину.<br />
[[Файл:стек4.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|5<br />
|3<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|2<br />
|1<br />
|}<br />
<br />
<br />
* Так будет выглядеть массив после последовательности операций <tex>push(3, 6), push(5, 1), pop(4), pop(5), push(7, 9):</tex><br />
[[Файл:стек.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;5&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;6&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;7&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;8&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;9&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|5<br />
|3<br />
|6<br />
|1<br />
|<tex>null</tex><br />
|5<br />
|9<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|2<br />
|1<br />
|3<br />
|5<br />
|<tex>null</tex><br />
|2<br />
|7<br />
|}<br />
<br />
<br />
В итоге мы имеем доступ ко всем версиям стека за <tex>O(1)</tex> времени и <tex>O(n)</tex> памяти.<br />
<br />
<br />
<br />
== См. также==<br />
<br />
* [[Стек]]<br />
* [[Персистентный дек]]<br />
<br />
== Источники информации ==<br />
<br />
* [http://habrahabr.ru/blogs/algorithm/113585/ Habrahabr - Персистентный стек]<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
<br />
[[Категория: Амортизационный анализ]]</div>217.71.235.207http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&diff=46156АВЛ-дерево2015-05-09T11:40:51Z<p>217.71.235.207: /* Литература */ тикет 4-3</p>
<hr />
<div>'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.<br />
<br />
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.<br />
<br />
== Высота дерева ==<br />
{{Теорема <br />
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.<br />
||proof=<br />
<br />
Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.<br />
<br />
{{Лемма<br />
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи. <br />
|proof=<br />
Если <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> докажем по индукции. <br />
<br />
База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>. <br />
<br />
Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно. <br />
<br />
Тогда <tex>m_{h+1} = m_h + m_{h-1} + 1 = F_{h+2} - 1 + F_{h+1} - 1 + 1 = F_{h+3} - 1</tex>. <br />
<br />
Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.<br />
}}<br />
<br />
<br />
<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть<br />
<br />
<tex>n \geqslant \varphi^{h}</tex><br />
<br />
Логарифмируя по основанию <tex>\varphi</tex>, получаем<br />
<br />
<tex>\log_{\varphi}n \geqslant h</tex><br />
<br />
Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.<br />
}}<br />
<br />
== Балансировка ==<br />
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.<br />
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex><br />
<br />
Для балансировки вершины используются один из 4 типов вращений:<br />
<br />
{| border="1" cellpadding="5" cellspacing="0"<br />
!Тип вращения<br />
!Иллюстрация<br />
!Когда используется<br />
!Расстановка балансов<br />
|-<br />
|'''Малое левое вращение'''<br />
| [[Файл:avl_u1.jpg|2000x200px]] <br />
|<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex><br />
<br />
<br />
<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex><br />
<br />
|-<br />
|'''Большое левое вращение'''<br />
| [[Файл:avl_u2.jpg|2000x200px]]<br />
|<br />
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
<br />
|}<br />
Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению.<br />
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.<br />
<br />
Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.<br />
<br />
== Операции ==<br />
=== Добавление вершины ===<br />
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным <tex>1</tex> или <tex>-1</tex>, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным <tex>2</tex> или <tex>-2</tex>, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.<br />
<br />
Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.<br />
<br />
=== Удаление вершины ===<br />
Для простоты опишем рекурсивный алгоритм удаления.<br />
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <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>, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.<br />
<br />
В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.<br />
<br />
=== Поиск вершины, минимум/максимум в дереве, etc. ===<br />
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.<br />
===Слияние двух AVL-деревьев===<br />
<br />
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>. <br />
<br />
В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.<br />
<br />
Дерево <tex>T_1</tex> и <tex>T_2</tex> до слияния<br />
<br />
<br />
[[File:avl_u3.jpg|340px]]<br />
<br />
Дерево <tex>T_2</tex> после слияния<br />
<br />
<br />
[[File:avl_u4.jpg|300px]]<br />
<br />
<br />
== Источники информации ==<br />
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория:Деревья поиска]]</div>217.71.235.207http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&diff=46155АВЛ-дерево2015-05-09T11:40:05Z<p>217.71.235.207: /* Удаление вершины */ тикет 4-3</p>
<hr />
<div>'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.<br />
<br />
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.<br />
<br />
== Высота дерева ==<br />
{{Теорема <br />
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.<br />
||proof=<br />
<br />
Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.<br />
<br />
{{Лемма<br />
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи. <br />
|proof=<br />
Если <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> докажем по индукции. <br />
<br />
База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>. <br />
<br />
Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно. <br />
<br />
Тогда <tex>m_{h+1} = m_h + m_{h-1} + 1 = F_{h+2} - 1 + F_{h+1} - 1 + 1 = F_{h+3} - 1</tex>. <br />
<br />
Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.<br />
}}<br />
<br />
<br />
<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть<br />
<br />
<tex>n \geqslant \varphi^{h}</tex><br />
<br />
Логарифмируя по основанию <tex>\varphi</tex>, получаем<br />
<br />
<tex>\log_{\varphi}n \geqslant h</tex><br />
<br />
Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.<br />
}}<br />
<br />
== Балансировка ==<br />
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.<br />
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex><br />
<br />
Для балансировки вершины используются один из 4 типов вращений:<br />
<br />
{| border="1" cellpadding="5" cellspacing="0"<br />
!Тип вращения<br />
!Иллюстрация<br />
!Когда используется<br />
!Расстановка балансов<br />
|-<br />
|'''Малое левое вращение'''<br />
| [[Файл:avl_u1.jpg|2000x200px]] <br />
|<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex><br />
<br />
<br />
<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex><br />
<br />
|-<br />
|'''Большое левое вращение'''<br />
| [[Файл:avl_u2.jpg|2000x200px]]<br />
|<br />
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
<br />
|}<br />
Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению.<br />
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.<br />
<br />
Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.<br />
<br />
== Операции ==<br />
=== Добавление вершины ===<br />
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным <tex>1</tex> или <tex>-1</tex>, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным <tex>2</tex> или <tex>-2</tex>, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.<br />
<br />
Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.<br />
<br />
=== Удаление вершины ===<br />
Для простоты опишем рекурсивный алгоритм удаления.<br />
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <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>, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.<br />
<br />
В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.<br />
<br />
=== Поиск вершины, минимум/максимум в дереве, etc. ===<br />
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.<br />
===Слияние двух AVL-деревьев===<br />
<br />
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>. <br />
<br />
В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.<br />
<br />
Дерево <tex>T_1</tex> и <tex>T_2</tex> до слияния<br />
<br />
<br />
[[File:avl_u3.jpg|340px]]<br />
<br />
Дерево <tex>T_2</tex> после слияния<br />
<br />
<br />
[[File:avl_u4.jpg|300px]]<br />
<br />
<br />
== Литература ==<br />
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория:Деревья поиска]]</div>217.71.235.207http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&diff=46154АВЛ-дерево2015-05-09T11:39:13Z<p>217.71.235.207: /* Добавление вершины */ тикет 4-3</p>
<hr />
<div>'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.<br />
<br />
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.<br />
<br />
== Высота дерева ==<br />
{{Теорема <br />
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.<br />
||proof=<br />
<br />
Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.<br />
<br />
{{Лемма<br />
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи. <br />
|proof=<br />
Если <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> докажем по индукции. <br />
<br />
База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>. <br />
<br />
Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно. <br />
<br />
Тогда <tex>m_{h+1} = m_h + m_{h-1} + 1 = F_{h+2} - 1 + F_{h+1} - 1 + 1 = F_{h+3} - 1</tex>. <br />
<br />
Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.<br />
}}<br />
<br />
<br />
<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть<br />
<br />
<tex>n \geqslant \varphi^{h}</tex><br />
<br />
Логарифмируя по основанию <tex>\varphi</tex>, получаем<br />
<br />
<tex>\log_{\varphi}n \geqslant h</tex><br />
<br />
Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.<br />
}}<br />
<br />
== Балансировка ==<br />
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.<br />
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex><br />
<br />
Для балансировки вершины используются один из 4 типов вращений:<br />
<br />
{| border="1" cellpadding="5" cellspacing="0"<br />
!Тип вращения<br />
!Иллюстрация<br />
!Когда используется<br />
!Расстановка балансов<br />
|-<br />
|'''Малое левое вращение'''<br />
| [[Файл:avl_u1.jpg|2000x200px]] <br />
|<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex><br />
<br />
<br />
<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex><br />
<br />
|-<br />
|'''Большое левое вращение'''<br />
| [[Файл:avl_u2.jpg|2000x200px]]<br />
|<br />
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex><br />
<br />
или<br />
<br />
<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.<br />
|<br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
<br />
<br />
<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex><br />
<br />
|}<br />
Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению.<br />
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.<br />
<br />
Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.<br />
<br />
== Операции ==<br />
=== Добавление вершины ===<br />
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным <tex>1</tex> или <tex>-1</tex>, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным <tex>2</tex> или <tex>-2</tex>, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.<br />
<br />
Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.<br />
<br />
=== Удаление вершины ===<br />
Для простоты опишем рекурсивный алгоритм удаления.<br />
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <tex>a</tex>, переместим её на место удаляемой вершины и [[Дерево поиска, наивная реализация#Удаление|удалим]] вершину <tex>a</tex>. От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> уменьшается на единицу, если из правого, то увеличивается на единицу. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит, что высота этого поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс стал равным 2 или -2, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.<br />
<br />
В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.<br />
<br />
=== Поиск вершины, минимум/максимум в дереве, etc. ===<br />
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.<br />
===Слияние двух AVL-деревьев===<br />
<br />
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>. <br />
<br />
В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.<br />
<br />
Дерево <tex>T_1</tex> и <tex>T_2</tex> до слияния<br />
<br />
<br />
[[File:avl_u3.jpg|340px]]<br />
<br />
Дерево <tex>T_2</tex> после слияния<br />
<br />
<br />
[[File:avl_u4.jpg|300px]]<br />
<br />
<br />
== Литература ==<br />
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория:Деревья поиска]]</div>217.71.235.207http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%B5%D1%80%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D1%81%D1%82%D0%B5%D0%BA&diff=46151Персистентный стек2015-05-09T11:33:03Z<p>217.71.235.207: /* Эффективная реализация */ тикет 1-1</p>
<hr />
<div>''Персистентными структурами данных'' называются структуры, хранящие все свои промежуточные версии.<br />
<br />
<br />
Рассмотрим такую структуру на примере [[стек|стека]].<br />
<br />
<br />
== Наивная реализация ==<br />
<br />
Самое простое и очевидное решение этой задачи — честное копирование стека при каждой операции. <br><br />
Очевидно, это не самое эффективное решение. Сложность одной операции составляет <tex>O(n)</tex> и количество требуемой памяти — <tex>O(n^2)</tex>.<br />
<br />
== Эффективная реализация ==<br />
<br />
Попробуем решить задачу эффективнее. Заведем массив запросов, модифицирующих стек.<br><br />
У каждого элемента массива будет 2 поля: значение в вершине стека и индекс предыдущей версии стека.<br><br />
Тогда операции push и pop будут иметь следующий вид:<br><br />
* <tex>push(i, x)</tex> — добавляет элемент х в стек с номером i, результирующий стек будет иметь номер <tex> n + 1 </tex>.<br />
arr.push (x, i)<br />
* <tex>pop(i)</tex> — возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.<br />
результирующий стек будет иметь номер <tex> n + 1 </tex>.<br />
a = arr[прошлый элемент для i-ого];<br />
arr.push(a);<br />
<br />
== Пример ==<br />
<br />
* Пусть изначально у нас есть один пустой стек. Запишем его в массив.<br />
[[Файл:стек1.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|}<br />
<br />
<br />
* Далее выполним <tex>push(1, 3)</tex>. Создается новая вершина со значением 3, ссылающаяся на 1-ую, помещаем ее во 2-ую ячейку массива:<br />
[[Файл:стек2.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|}<br />
<br />
<br />
* Аналогично выполним <tex>push(2, 5)</tex>:<br />
[[Файл:стек3.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|5<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|2<br />
|}<br />
<br />
<br />
* Выполним <tex>pop(3)</tex>. он возвращает 5 и копирует 2-ую вершину.<br />
[[Файл:стек4.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|5<br />
|3<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|2<br />
|1<br />
|}<br />
<br />
<br />
* Так будет выглядеть массив после последовательности операций <tex>push(3, 6), push(5, 1), pop(4), pop(5), push(7, 9):</tex><br />
[[Файл:стек.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;5&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;6&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;7&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;8&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;9&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|5<br />
|3<br />
|6<br />
|1<br />
|<tex>null</tex><br />
|5<br />
|9<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|2<br />
|1<br />
|3<br />
|5<br />
|<tex>null</tex><br />
|2<br />
|7<br />
|}<br />
<br />
<br />
В итоге мы имеем доступ ко всем версиям стека за <tex>O(1)</tex> времени и <tex>O(n)</tex> памяти.<br />
<br />
<br />
<br />
== См. также==<br />
<br />
* [[Стек]]<br />
* [[Персистентный дек]]<br />
<br />
== Ссылки ==<br />
<br />
* [http://habrahabr.ru/blogs/algorithm/113585/ Habrahabr - Персистентный стек]<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
<br />
[[Категория: Амортизационный анализ]]</div>217.71.235.207http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%B5%D1%80%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D1%81%D1%82%D0%B5%D0%BA&diff=45847Персистентный стек2015-04-28T17:19:35Z<p>217.71.235.207: Тикет 1-1-3</p>
<hr />
<div>''Персистентными структурами данных'' называются структуры, хранящие все свои промежуточные версии.<br />
<br />
<br />
Рассмотрим такую структуру на примере [[стек|стека]].<br />
<br />
<br />
== Наивная реализация ==<br />
<br />
Самое простое и очевидное решение этой задачи — честное копирование стека при каждой операции. <br><br />
Очевидно, это не самое эффективное решение. Сложность одной операции составляет <tex>O(n)</tex> и количество требуемой памяти — <tex>O(n^2)</tex>.<br />
<br />
== Эффективная реализация ==<br />
<br />
Попробуем решить задачу эффективнее. Заведем массив запросов, модифицирующих стек.<br><br />
У каждого элемента массива будет 2 поля: значение в вершине стека и индекс предыдущей версии стека.<br><br />
Тогда операции push и pop будут иметь следующий вид:<br><br />
* <tex>push(i, x)</tex> — добавляет элемент х в стек с номером i, результирующий стек будет иметь номер <tex> n + 1 </tex>.<br />
mas.push_back(value = x, prev = i)<br />
* <tex>pop(i)</tex> — возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.<br />
результирующий стек будет иметь номер <tex> n + 1 </tex>.<br />
mas.push_back( copy_of(mas[i.prev]) )<br />
<br />
== Пример ==<br />
<br />
* Пусть изначально у нас есть один пустой стек. Запишем его в массив.<br />
[[Файл:стек1.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|}<br />
<br />
<br />
* Далее выполним <tex>push(1, 3)</tex>. Создается новая вершина со значением 3, ссылающаяся на 1-ую, помещаем ее во 2-ую ячейку массива:<br />
[[Файл:стек2.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|}<br />
<br />
<br />
* Аналогично выполним <tex>push(2, 5)</tex>:<br />
[[Файл:стек3.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|5<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|2<br />
|}<br />
<br />
<br />
* Выполним <tex>pop(3)</tex>. он возвращает 5 и копирует 2-ую вершину.<br />
[[Файл:стек4.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|5<br />
|3<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|2<br />
|1<br />
|}<br />
<br />
<br />
* Так будет выглядеть массив после последовательности операций <tex>push(3, 6), push(5, 1), pop(4), pop(5), push(7, 9):</tex><br />
[[Файл:стек.png|500px|nothumb|right|]]<br />
{| border = 1; cellspacing = 0; class="wikitable"<br />
|- align = "center"<br />
!index<br />
!1<br />
!&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;5&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;6&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;7&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;8&nbsp;&nbsp;&nbsp;&nbsp;<br />
!&nbsp;&nbsp;&nbsp;&nbsp;9&nbsp;&nbsp;&nbsp;&nbsp;<br />
|-align = "center"<br />
!value<br />
|<tex>null</tex><br />
|3<br />
|5<br />
|3<br />
|6<br />
|1<br />
|<tex>null</tex><br />
|5<br />
|9<br />
|-align = "center"<br />
!prev<br />
|<tex>null</tex><br />
|1<br />
|2<br />
|1<br />
|3<br />
|5<br />
|<tex>null</tex><br />
|2<br />
|7<br />
|}<br />
<br />
<br />
В итоге мы имеем доступ ко всем версиям стека за <tex>O(1)</tex> времени и <tex>O(n)</tex> памяти.<br />
<br />
<br />
<br />
== См. также==<br />
<br />
* [[Стек]]<br />
* [[Персистентный дек]]<br />
<br />
== Ссылки ==<br />
<br />
* [http://habrahabr.ru/blogs/algorithm/113585/ Habrahabr - Персистентный стек]<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
<br />
[[Категория: Амортизационный анализ]]</div>217.71.235.207