АВЛ-дерево — различия между версиями
(→Высота дерева) |
(→Балансировка) |
||
Строка 47: | Строка 47: | ||
!Когда используется | !Когда используется | ||
!Расстановка балансов | !Расстановка балансов | ||
− | |||
|- | |- | ||
|'''Малое левое вращение''' (''Small left rotation'') | |'''Малое левое вращение''' (''Small left rotation'') | ||
Строка 64: | Строка 63: | ||
<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex> | <tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
|- | |- | ||
|'''Большое левое вращение''' (Big left rotation'') | |'''Большое левое вращение''' (Big left rotation'') | ||
Строка 95: | Строка 86: | ||
<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex> | <tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
|} | |} | ||
+ | Малый левый поворот: | ||
+ | rotateleft(node a) { | ||
+ | node b = a.right | ||
+ | a.right = b.left | ||
+ | b.left = a | ||
+ | fixheight(a) | ||
+ | fixheight(b) | ||
+ | } | ||
+ | Большой правый поворот пишется проще: | ||
+ | bigrotateleft(node a) { | ||
+ | rotateright(a.right) | ||
+ | rotateleft(a) | ||
+ | } | ||
Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению. | Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению. | ||
− | В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться. | + | В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на <tex>1</tex> и не может увеличиться. |
Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций. | Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций. |
Версия 19:22, 5 июня 2015
АВЛ-дерево (AVL-Tree) — сбалансированное двоичное дерево поиска, в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.
Содержание
Высота дерева
Теорема: | ||||||
АВЛ-дерево с ключами имеет высоту . | ||||||
Доказательство: | ||||||
Высоту поддерева с корнем будем обозначать как , высоту поддерева — как .
Логарифмируя по основанию , получаемТаким образом, получаем, что высота AVL-дерева из n вершин — . | ||||||
Балансировка
Балансировкой вершины называется операция, которая в случае разницы высот левого и правого поддеревьев
, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева , иначе ничего не меняет. Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддереваДля балансировки вершины используются один из 4 типов вращений:
Тип вращения | Иллюстрация | Когда используется | Расстановка балансов |
---|---|---|---|
Малое левое вращение (Small left rotation) |
и или и . |
| |
Большое левое вращение (Big left rotation) |
, и или , и или , и . |
|
Малый левый поворот:
rotateleft(node a) { node b = a.right a.right = b.left b.left = a fixheight(a) fixheight(b) }
Большой правый поворот пишется проще:
bigrotateleft(node a) { rotateright(a.right) rotateleft(a) }
Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению. В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на
и не может увеличиться.Все операции вращения, очевидно, требуют
операций.Операции
Добавление вершины
Пусть нам надо добавить ключ
. Будем спускаться по дереву, как при поиске ключа . Если мы стоим в вершине и нам надо идти в поддерево, которого нет, то делаем ключ листом, а вершину его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину из левого поддерева, то увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным или , то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным или , то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.Так как в процессе добавления вершины мы рассматриваем не более, чем
вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет операций.Удаление вершины
Для простоты опишем рекурсивный алгоритм удаления. Если вершина - лист, то удалим её, иначе найдём самую близкую по значению вершину , переместим её на место удаляемой вершины и удалим вершину . От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину из левого поддерева, то уменьшается на единицу, если из правого, то увеличивается на единицу. Если пришли в вершину и её баланс стал равным или , то это значит, что высота этого поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс стал равным или , следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.
В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее,
операций. Таким образом, требуемое количество действий — .Поиск вершины, минимум/максимум в дереве, etc.
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в наивной реализации дерева поиска.
Слияние двух AVL-деревьев
Дано два дерева
и , все ключи в меньше ключей в , .В дереве
удаляем самую правую вершину, назовём её . Высота дерева может уменьшиться на единицу. В дереве идём от корня всегда в левое поддерево и, когда высота этого поддерева будет равна высоте дерева , делаем новое дерево , корнем будет вершина , левым поддеревом будет дерево , а правым дерево . Теперь в дереве у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево и запускаем балансировку. Таким образом, дерево будет результатом слияния двух АВЛ-деревьев.Дерево
и до слиянияДерево
после слиянияАлгоритм разделения AVL-дерева на два
Алгоритм первый
Пусть у нас есть дерево
. Мы должны разбить его на два дерева и такие, что и .Предположим, что корень нашего дерева
, в таком случае все левое поддерево вместе с корнем после разделения отойдет в дерево . Тогда рекурсивно спускаемся в правое поддерево и там проверяем это условие (так как часть правого поддерева тоже может содержать ключи ). Если же корень оказался , то мы спускаемся той же рекурсией, но только в левое поддерево и ищем там.Пусть мы пришли в поддерево
, корень которого . В таком случае этот корень со своим левым поддеревом должен отойти в дерево . Поэтому мы делаем следующее: запоминаем ссылку на правое поддерево , удаляем корень, запоминая его значение (не меняя конфигурацию дерева, то есть просто делаем ссылки на него NULL'ами). Таким образом, мы отделяем сбалансированное АВЛ-дерево (бывшее левое поддерево ). Делаем новую вершину со значением бывшего корня правым листом самой правой вершины и запускаем балансировку. Обозначим полученное дерево за . Теперь нам нужно объединить его с уже построенным ранее (оно может быть пустым, если мы первый раз нашли такое дерево ). Для этого мы ищем в дереве самое правое поддерево высоты, равной высоте (спускаясь от корня всегда в правые поддеревья). Делаем новое дерево , сливая и (очевидно, все ключи в меньше ключей в , поэтому мы можем это сделать). Теперь в дереве у отца вершины, в которой мы остановились при поиске дерева , правым поддеревом делаем дерево и запускаем балансировку. После нужно спуститься в правое поддерево бывшего дерева (по ссылке, которую мы ранее запомнили) и обработать его.Если мы пришли в поддерево
, корень которого , совершаем аналогичные действия: делаем NULL'ами ссылки на корень , запоминая ссылку на его левое поддерево. Делаем новую вершину со значением бывшего корня левым листом самой левой вершины и запускаем балансировку. Объединяем полученное АВЛ-дерево с уже построенным ранее аналогичным первому случаю способом, только теперь мы ищем самое левое поддерево .Рассмотри пример (рис. 1). Цветом выделены поддеревья, которые после разделения должны отойти в дерево
. .Корень дерева
, поэтому он со всем выделенным поддеревом должен отойти в дерево . По описанному выше алгоритму отделяем это поддерево с корнем и делаем из них сбалансированное АВЛ-дерево (рис. 2). Так как это первая ситуация, в которой корень рассматриваемого поддерева был , становится . Далее по сохраненной ссылке спускаемся в правое поддерево. Его корень . Следовательно, строим из него и его правого поддерева и спускаемся в левое поддерево. Снова корень . Строим новое и объединяем его с уже существующим (рис. 3).Далее действуем по алгоритму и в итоге получаем (рис. 4):
Данный алгоритм имеет сложность
.Алгоритм второй
Рассмотрим решение, которое имеет сложность
.Вернемся к примеру (рис. 1). Теперь рекурсивно спустимся вниз и оттуда будем строить деревья
и , передавая наверх корректные АВЛ-деревья. То есть для рис. 1 первым в дерево придет вершина с левым поддеревом (выделено светло-зеленым цветом), так как это корректное АВЛ-дерево, оно же и вернется из рекурсии. Далее мы попадем в вершину со значением и должны слить ее и ее левое поддерево (выделено светло-синим) с тем, что нам пришло. И сделать это нужно так, чтобы передать наверх корректное АВЛ-дерево. Будем действовать по такому алгоритму, пока не дойдем до вершины.Пусть мы пришли в поддерево
с корнем . Тогда сольем его с уже построенным на тот момент ( пришло снизу, а значит по условию рекурсии это корректное АВЛ-дерево, и ). Но так как обычная процедура слияния сливает два АВЛ-дерева, а не является корректным АВЛ-деревом, мы немного ее изменим. Пусть мы в дереве нашли самое правое поддерево , высота которого равна высоте . Тогда сделаем новое дерево , корнем которого будет вершина (без нее это дерево является сбалансированным), правым поддеревом — , левым — . И подвесим на то место, где мы остановились при поиске . Запустим балансировку. В случае, когда корень поддерева, в которое мы пришли, , все аналогично.Разберем пример на рис. 1. Пусть мы рекурсивно спустились до узла
. Ключ больше , поэтому эта вершина станет деревом и передастся наверх. Теперь мы поднялись в узел . Он со своим левым поддеревом станет деревом и мы снова поднимемся наверх в узел . Он со своим левым поддеревом снова должен отойти в дерево , и так как теперь дерево уже не пустое, то их надо слить. После слияния по описанному выше алгоритму получим (рис. 5)После мы поднимемся в вершину с ключом
. Она с правым поддеревом отойдет в дерево (рис. 6).И на последней итерации мы поднимемся в корень дерева с ключом
, он с левым поддеревом отойдет в дерево , после чего алгоритм завершится.Пусть поддеревьев с ключами
оказалось больше, чем поддеревьев с ключами . Докажем для них логарифмическую асимптотику. Дерево на последнем уровне имеет высоту (она может быть не равна , если мы придём в ). Его мы передаем наверх и вставляем в поддерево высотой . , так как разница высот поддеревьев у любой вершины не больше , и мы при переходе от к поднимаемся как минимум на одну вершину вверх. Слияние этих поддеревьев мы выполним за , получим в итоге дерево высоты не большей, чем . Его мы передадим наверх, поэтому в следующий раз слияние будет выполнено за и так далее. Таким образом мы получим .Итоговая асимптотика алгоритма —
.