Что такое сбалансированное дерево

Сбалансированное бинарное дерево из отсортированного массива

Бинарное дерево поиска — дерево в котором узлы располагаются таким образом, что каждый узел с меньшим значением (относительно родителя) находится в левой части дерева, соответственно с большим — в правой.

Дерево поиска с минимальной высотой как раз и называется сбалансированным, т.е. таким, в котором высота левого и правого поддеревьев отличаются не более чем на единицу.

Сбалансированное оно, видимо, потому что в таком дереве в среднем требуется наименьшее количество операций для поиска.

Чтобы дерево имело минимальную высоту, количество узлов левого и правого поддеревьев должны максимально приближаться друг к другу. Построим дерево по этому принципу: середина каждого подраздела массива становится корневым узлом, а левая и правая части — соответствующими для него поддеревьями. Т.к. массив отсортирован, то полученное дерево соответствует определению бинарного дерева поиска.

�� Веду телеграм-канал с еженедельными разборами задач для собеседований.

Каким образом реализовать алгоритм?

Можно каждый раз начинать вставку нового элемента с корня, рекурсивно обходя все дерево для поиска места для нового узла.

Этот способ не слишком эффективен — обход дерева требует O(log N) операций, чтобы вставить каждый узел потребуется O(n * log N) времени.

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

Алгоритм получился примерно такой:

• выбрать средний элемент массива в качестве корня
• начинать создавать левое поддерево из левой части массива
• начинать создавать правое поддерево из правой части массива
• повторить рекурсивно, пока не закончатся элементы в массиве

Реализация получилась довольно простой. Единственное на что нужно обратить внимание — смещение на единицу при выборе границ частей массива.

Это решения задач из книги Cracking the Coding Interview. Все опубликованные мною решения можно найти по фильтру.

АВЛ-дерево

АВЛ-дерево (англ. AVL-Tree) — сбалансированное двоичное дерево поиска, в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

Высота дерева

АВЛ-дерево с [math]n[/math] ключами имеет высоту [math]h = O(\log n)[/math] .

Высоту поддерева с корнем [math]x[/math] будем обозначать как [math]h(x)[/math] , высоту поддерева [math]T[/math] — как [math]h(T)[/math] .

Пусть [math]m_h[/math] — минимальное число вершин в AVL-дереве высоты [math]h[/math] , тогда [math]m_h = F_ — 1[/math] , где [math]F_h — h[/math] -ое число Фибоначчи.

Если [math]m_h[/math] — минимальное число вершин в AVL-дереве высоты [math]h[/math] . Тогда как легко видеть, [math]m_ = m_ + m_h + 1[/math] . Равенство [math]m_h = F_ — 1[/math] докажем по индукции.

База индукции [math]m_1 = F_3 — 1[/math] — верно, [math]m_1 = 1, F_3 = 2[/math] .

Допустим [math]m_h = F_ — 1[/math] — верно.

Тогда [math]m_ = m_h + m_ + 1 = F_ — 1 + F_ — 1 + 1 = F_ — 1[/math] .

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

[math]n \geqslant \varphi^[/math]

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

[math]\log_n \geqslant h[/math]

Балансировка

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

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

[math]diff[a] = -2[/math] и [math]diff[b] = -1[/math]

[math]diff[a] = -2[/math] и [math]diff[b] = 0[/math] .

[math]diff[a] = 0[/math] и [math]diff[b] = 0[/math]

[math]diff[a] = -1[/math] и [math]diff[b] = 1[/math]

[math]diff[a] = -2[/math] , [math]diff[b] = 1[/math] и [math]diff[c] = 1[/math]

[math]diff[a] = -2[/math] , [math]diff[b] = 1[/math] и [math]diff[c] = -1[/math]

[math]diff[a] = -2[/math] , [math]diff[b] = 1[/math] и [math]diff[c] = 0[/math] .

[math]diff[a] = 0[/math] , [math]diff[b] = -1[/math] и [math]diff[c] = 0[/math]

[math]diff[a] = 1[/math] , [math]diff[b] = 0[/math] и [math]diff[c] = 0[/math]

[math]diff[a] = 0[/math] , [math]diff[b] = 0[/math] и [math]diff[c] = 0[/math]

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

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

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

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

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

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

Операции

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

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

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

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

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

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

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

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

Слияние двух AVL-деревьев

Дано два дерева [math]T_1[/math] и [math]T_2[/math] , все ключи в [math]T_1[/math] меньше ключей в [math]T_2[/math] , [math]h(T_1) \leqslant h(T_2)[/math] .

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

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

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

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

Алгоритм первый

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

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

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

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

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

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

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

Рис. 2. Создание T’.

Рис. 3. Объединение T’ и T1.

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

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

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

Алгоритм второй

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

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

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

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

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

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

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

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

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

Идея

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

Операции

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

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

Балансировка

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

АВЛ-деревья

Если в одном из моих прошлых постов речь шла о довольно современном подходе к построению сбалансированных деревьев поиска, то этот пост посвящен реализации АВЛ-деревьев — наверное, самого первого вида сбалансированных двоичных деревьев поиска, придуманных еще в 1962 году нашими (тогда советскими) учеными Адельсон-Вельским и Ландисом. В сети можно найти много реализаций АВЛ-деревьев (например, тут), но все, что лично я видел, не внушает особенного оптимизма, особенно, если пытаешься разобраться во всем с нуля. Везде утверждается, что АВЛ-деревья проще красно-черных деревьев, но глядя на прилагаемый к этому код, начинаешь сомневаться в данном утверждении. Собственно, желание объяснить на пальцах, как устроены АВЛ-деревья, и послужило мотивацией к написанию данного поста. Изложение иллюстрируется кодом на С++.

Понятие АВЛ-дерева

АВЛ-дерево — это прежде всего двоичное дерево поиска, ключи которого удовлетворяют стандартному свойству: ключ любого узла дерева не меньше любого ключа в левом поддереве данного узла и не больше любого ключа в правом поддереве этого узла. Это значит, что для поиска нужного ключа в АВЛ-дереве можно использовать стандартный алгоритм. Для простоты дальнейшего изложения будем считать, что все ключи в дереве целочисленны и не повторяются.

Особенностью АВЛ-дерева является то, что оно является сбалансированным в следующем смысле: для любого узла дерева высота его правого поддерева отличается от высоты левого поддерева не более чем на единицу. Доказано, что этого свойства достаточно для того, чтобы высота дерева логарифмически зависела от числа его узлов: высота h АВЛ-дерева с n ключами лежит в диапазоне от log₂(n + 1) до 1.44 log₂(n + 2) − 0.328. А так как основные операции над двоичными деревьями поиска (поиск, вставка и удаление узлов) линейно зависят от его высоты, то получаем гарантированную логарифмическую зависимость времени работы этих алгоритмов от числа ключей, хранимых в дереве. Напомним, что рандомизированные деревья поиска обеспечивают сбалансированность только в вероятностном смысле: вероятность получения сильно несбалансированного дерева при больших n хотя и является пренебрежимо малой, но остается не равной нулю.

Структура узлов

Будем представлять узлы АВЛ-дерева следующей структурой:

struct node // структура для представления узлов дерева < int key; unsigned char height; node* left; node* right; node(int k) < key = k; left = right = 0; height = 1; >>; 

Поле key хранит ключ узла, поле height — высоту поддерева с корнем в данном узле, поля left и right — указатели на левое и правое поддеревья. Простой конструктор создает новый узел (высоты 1) с заданным ключом k.

Традиционно, узлы АВЛ-дерева хранят не высоту, а разницу высот правого и левого поддеревьев (так называемый balance factor), которая может принимать только три значения -1, 0 и 1. Однако, заметим, что эта разница все равно хранится в переменной, размер которой равен минимум одному байту (если не придумывать каких-то хитрых схем «эффективной» упаковки таких величин). Вспомним, что высота h < 1.44 log₂(n + 2), это значит, например, что при n=10 9 (один миллиард ключей, больше 10 гигабайт памяти под хранение узлов) высота дерева не превысит величины h=44, которая с успехом помещается в тот же один байт памяти, что и balance factor. Таким образом, хранение высот с одной стороны не увеличивает объем памяти, отводимой под узлы дерева, а с другой стороны существенно упрощает реализацию некоторых операций.

Определим три вспомогательные функции, связанные с высотой. Первая является оберткой для поля height, она может работать и с нулевыми указателями (с пустыми деревьями):

unsigned char height(node* p) < return p?p->height:0; > 

Вторая вычисляет balance factor заданного узла (и работает только с ненулевыми указателями):

int bfactor(node* p) < return height(p->right)-height(p->left); > 

Третья функция восстанавливает корректное значение поля height заданного узла (при условии, что значения этого поля в правом и левом дочерних узлах являются корректными):

void fixheight(node* p) < unsigned char hl = height(p->left); unsigned char hr = height(p->right); p->height = (hl>hr?hl:hr)+1; > 

Заметим, что все три функции являются нерекурсивными, т.е. время их работы есть величина О(1).

Балансировка узлов

В процессе добавления или удаления узлов в АВЛ-дереве возможно возникновение ситуации, когда balance factor некоторых узлов оказывается равными 2 или -2, т.е. возникает расбалансировка поддерева. Для выправления ситуации применяются хорошо нам известные повороты вокруг тех или иных узлов дерева. Напомню, что простой поворот вправо (влево) производит следующую трансформацию дерева:

Код, реализующий правый поворот, выглядит следующим образом (как обычно, каждая функция, изменяющая дерево, возвращает новый корень полученного дерева):

node* rotateright(node* p) // правый поворот вокруг p < node* q = p->left; p->left = q->right; q->right = p; fixheight(p); fixheight(q); return q; > 

Левый поворот является симметричной копией правого:

node* rotateleft(node* q) // левый поворот вокруг q < node* p = q->right; q->right = p->left; p->left = q; fixheight(q); fixheight(p); return p; > 

Рассмотрим теперь ситуацию дисбаланса, когда высота правого поддерева узла p на 2 больше высоты левого поддерева (обратный случай является симметричным и реализуется аналогично). Пусть q — правый дочерний узел узла p, а s — левый дочерний узел узла q.

Анализ возможных случаев в рамках данной ситуации показывает, что для исправления расбалансировки в узле p достаточно выполнить либо простой поворот влево вокруг p, либо так называемый большой поворот влево вокруг того же p. Простой поворот выполняется при условии, что высота левого поддерева узла q больше высоты его правого поддерева: h(s)≤h(D).

Большой поворот применяется при условии h(s)>h(D) и сводится в данном случае к двум простым — сначала правый поворот вокруг q и затем левый вокруг p.

Код, выполняющий балансировку, сводится к проверке условий и выполнению поворотов:

node* balance(node* p) // балансировка узла p < fixheight(p); if( bfactor(p)==2 ) < if( bfactor(p->right) < 0 ) p->right = rotateright(p->right); return rotateleft(p); > if( bfactor(p)==-2 ) < if( bfactor(p->left) > 0 ) p->left = rotateleft(p->left); return rotateright(p); > return p; // балансировка не нужна > 

Описанные функции поворотов и балансировки также не содержат ни циклов, ни рекурсии, а значит выполняются за постоянное время, не зависящее от размера АВЛ-дерева.

Вставка ключей

Вставка нового ключа в АВЛ-дерево выполняется, по большому счету, так же, как это делается в простых деревьях поиска: спускаемся вниз по дереву, выбирая правое или левое направление движения в зависимости от результата сравнения ключа в текущем узле и вставляемого ключа. Единственное отличие заключается в том, что при возвращении из рекурсии (т.е. после того, как ключ вставлен либо в правое, либо в левое поддерево, и это дерево сбалансировано) выполняется балансировка текущего узла. Строго доказывается, что возникающий при такой вставке дисбаланс в любом узле по пути движения не превышает двух, а значит применение вышеописанной функции балансировки является корректным.

node* insert(node* p, int k) // вставка ключа k в дерево с корнем p < if( !p ) return new node(k); if( kkey ) p->left = insert(p->left,k); else p->right = insert(p->right,k); return balance(p); > 

Чтобы проверить соответствие реализованного алгоритма вставки теоретическим оценкам для высоты АВЛ-деревьев, был проведен несложный вычислительный эксперимент. Генерировался массив из случайно расположенных чисел от 1 до 10000, далее эти числа последовательно вставлялись в изначально пустое АВЛ-дерево и измерялась высота дерева после каждой вставки. Полученные результаты были усреднены по 1000 расчетам. На следующем графике показана зависимость от n средней высоты (красная линия); минимальной высоты (зеленая линия); максимальной высоты (синяя линия). Кроме того, показаны верхняя и нижняя теоретические оценки.

Видно, что для случайных последовательностей ключей экспериментально найденные высоты попадают в теоретические границы даже с небольшим запасом. Нижняя граница достижима (по крайней мере в некоторых точках), если исходная последовательность ключей является упорядоченной по возрастанию.

Удаление ключей

С удалением узлов из АВЛ-дерева, к сожалению, все не так шоколадно, как с рандомизированными деревьями поиска. Способа, основанного на слиянии (join) двух деревьев, ни найти, ни придумать не удалось. Поэтому за основу был взят вариант, описываемый практически везде (и который обычно применяется и при удалении узлов из стандартного двоичного дерева поиска). Идея следующая: находим узел p с заданным ключом k (если не находим, то делать ничего не надо), в правом поддереве находим узел min с наименьшим ключом и заменяем удаляемый узел p на найденный узел min.

При реализации возникает несколько нюансов. Прежде всего, если у найденный узел p не имеет правого поддерева, то по свойству АВЛ-дерева слева у этого узла может быть только один единственный дочерний узел (дерево высоты 1), либо узел p вообще лист. В обоих этих случаях надо просто удалить узел p и вернуть в качестве результата указатель на левый дочерний узел узла p.

Пусть теперь правое поддерево у p есть. Находим минимальный ключ в этом поддереве. По свойству двоичного дерева поиска этот ключ находится в конце левой ветки, начиная от корня дерева. Применяем рекурсивную функцию:

node* findmin(node* p) // поиск узла с минимальным ключом в дереве p < return p->left?findmin(p->left):p; > 

Еще одна служебная функция у нас будет заниматься удалением минимального элемента из заданного дерева. Опять же, по свойству АВЛ-дерева у минимального элемента справа либо подвешен единственный узел, либо там пусто. В обоих случаях надо просто вернуть указатель на правый узел и по пути назад (при возвращении из рекурсии) выполнить балансировку. Сам минимальный узел не удаляется, т.к. он нам еще пригодится.

node* removemin(node* p) // удаление узла с минимальным ключом из дерева p < if( p->left==0 ) return p->right; p->left = removemin(p->left); return balance(p); > 

Теперь все готово для реализации удаления ключа из АВЛ-дерева. Сначала находим нужный узел, выполняя те же действия, что и при вставке ключа:

node* remove(node* p, int k) // удаление ключа k из дерева p < if( !p ) return 0; if( k < p->key ) p->left = remove(p->left,k); else if( k > p->key ) p->right = remove(p->right,k); 

Как только ключ k найден, переходим к плану Б: запоминаем корни q и r левого и правого поддеревьев узла p; удаляем узел p; если правое поддерево пустое, то возвращаем указатель на левое поддерево; если правое поддерево не пустое, то находим там минимальный элемент min, потом его извлекаем оттуда, слева к min подвешиваем q, справа — то, что получилось из r, возвращаем min после его балансировки.

 else // k == p->key < node* q = p->left; node* r = p->right; delete p; if( !r ) return q; node* min = findmin(r); min->right = removemin(r); min->left = q; return balance(min); > 

При выходе из рекурсии не забываем выполнить балансировку:

 return balance(p); > 

Вот собственно и все! Поиск минимального узла и его извлечение, в принципе, можно реализовать в одной функции, при этом придется решать (не очень сложную) проблему с возвращением из функции пары указателей. Зато можно сэкономить на одном проходе по правому поддереву.

Очевидно, что операции вставки и удаления (а также более простая операция поиска) выполняются за время пропорциональное высоте дерева, т.к. в процессе выполнения этих операций производится спуск из корня к заданному узлу, и на каждом уровне выполняется некоторое фиксированное число действий. А в силу того, что АВЛ-дерево является сбалансированным, его высота зависит логарифмически от числа узлов. Таким образом, время выполнения всех трех базовых операций гарантированно логарифмически зависит от числа узлов дерева.

Всем спасибо за внимание!

Весь код

struct node // структура для представления узлов дерева < int key; unsigned char height; node* left; node* right; node(int k) < key = k; left = right = 0; height = 1; >>; unsigned char height(node* p) < return p?p->height:0; > int bfactor(node* p) < return height(p->right)-height(p->left); > void fixheight(node* p) < unsigned char hl = height(p->left); unsigned char hr = height(p->right); p->height = (hl>hr?hl:hr)+1; > node* rotateright(node* p) // правый поворот вокруг p < node* q = p->left; p->left = q->right; q->right = p; fixheight(p); fixheight(q); return q; > node* rotateleft(node* q) // левый поворот вокруг q < node* p = q->right; q->right = p->left; p->left = q; fixheight(q); fixheight(p); return p; > node* balance(node* p) // балансировка узла p < fixheight(p); if( bfactor(p)==2 ) < if( bfactor(p->right) < 0 ) p->right = rotateright(p->right); return rotateleft(p); > if( bfactor(p)==-2 ) < if( bfactor(p->left) > 0 ) p->left = rotateleft(p->left); return rotateright(p); > return p; // балансировка не нужна > node* insert(node* p, int k) // вставка ключа k в дерево с корнем p < if( !p ) return new node(k); if( kkey ) p->left = insert(p->left,k); else p->right = insert(p->right,k); return balance(p); > node* findmin(node* p) // поиск узла с минимальным ключом в дереве p < return p->left?findmin(p->left):p; > node* removemin(node* p) // удаление узла с минимальным ключом из дерева p < if( p->left==0 ) return p->right; p->left = removemin(p->left); return balance(p); > node* remove(node* p, int k) // удаление ключа k из дерева p < if( !p ) return 0; if( k < p->key ) p->left = remove(p->left,k); else if( k > p->key ) p->right = remove(p->right,k); else // k == p->key < node* q = p->left; node* r = p->right; delete p; if( !r ) return q; node* min = findmin(r); min->right = removemin(r); min->left = q; return balance(min); > return balance(p); > 

Источники

• B. Pfaff, An Introduction to Binary Search Trees and Balanced Trees — описание библиотеки libavl
• Н. Вирт, Алгоритмы и структуры данных — сбалансированные деревья по Вирту — это как раз АВЛ-деревья
• Т. Кормен и др., Алгоритмы: построение и анализ — про АВЛ-деревья говорится в упражнениях к главе про красно-черные деревья
• Д. Кнут, Искусство программирования — раздел 6.2.3 посвящен теоретическому анализу АВЛ-деревьев

АВЛ-дерево

АВЛ-дерево, или AVL tree, — древовидная структура данных с быстрым доступом к информации. Она представляет собой бинарное дерево — иерархическую схему из вершин и путей между ними, где у одной вершины может быть не более двух потомков. АВЛ-дерево – модифицированное, у него оптимизирована структура.

АВЛ-деревья придумали еще в 60-х годах советские ученые Адельсон-Вельский и Ландис. По первым буквам их фамилий и названа структура данных — АВЛ. Это модификация классического бинарного дерева поиска, благодаря которой структура лучше сбалансирована и практически не может выродиться. Вырождением называют ситуацию, когда у каждого узла оказывается только по одному потомку и структура фактически становится линейной — это неоптимально.

Освойте профессию «Аналитик данных»

Благодаря сбалансированности и борьбе с вырождением дерева информация в нем хранится более эффективно. Поэтому доступ к данным оказывается быстрее и найти их становится легче.

Кто пользуется АВЛ-деревьями

• Разработчики, которые работают с алгоритмами сортировки, хранения и поиска информации, реализуют те или иные сложные структуры. Сфера применения деревьев довольно широка, и про умение ими пользоваться могут спрашивать на собеседованиях в соответствующих отраслях.
• Аналитики данных, для которых работа с информацией — профессиональная сфера деятельности. АВЛ-деревья же — это один из методов эффективно хранить информацию и быстро получать из структуры конкретные данные. Также они могут пригодиться при реализации алгоритмов работы с данными.
• Математики, которые решают фундаментальные и практические задачи. АВЛ-деревья — подвид бинарных деревьев поиска, которые, в свою очередь, являются своеобразными графами. Все это относится к области дискретной математики: она частично пересекается с Computer Science и схожими направлениями.

Для чего нужны АВЛ-деревья

Для хранения данных. Эта структура позволяет хранить информацию в «узлах» дерева и перемещаться по ней с помощью путей, которые соединяют между собой узлы. Благодаря особому алгоритму данные хранятся относительно эффективно и с ними довольно удобно работать. Мы подробнее поговорим об этом ниже.

Профессия / 12 месяцев
Аналитик данных

Находите закономерности и делайте выводы, которые помогут бизнесу

Для поисковых алгоритмов. АВЛ-деревья и бинарные деревья поиска в принципе — важная составная часть разнообразных алгоритмов поиска информации. Их применяют при построении поисковых систем и интеллектуальных сервисов.

Для сортировки. Хранение информации в АВЛ-дереве позволяет быстрее отсортировать данные, а задача сортировки часто встречается в IT. С помощью деревьев можно хранить и сортировать информацию в базах данных, в особых участках памяти, в хэшах и других структурах.

Для программных проверок. АВЛ-дерево может использоваться для решения некоторых стандартных задач, например для быстрой проверки существования элемента в структуре.

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

Для других задач. Деревья могут понадобиться везде, где нужны связные структуры данных, оптимизированные под определенные операции. Например, они могут быть более функциональной альтернативой связанному списку — линейной структуре данных, где в каждом элементе есть ссылка на предыдущий и/или следующий.

Станьте аналитиком данных и получите востребованную специальность

Как устроено двоичное дерево поиска

АВЛ-дерево — модификация двоичного, или бинарного дерева поиска. Чтобы понять, в чем его особенность, нужно сначала разобраться с бинарными деревьями в целом.

Структура. Дерево представляет собой структуру, состоящую из узлов и путей между ними, — по сути, подвид графа. Особенность в том, что дерево иерархично: у всех узлов, кроме начального, есть «родитель» и сколько-либо «потомков». Получается древовидная структура — отсюда и название.

Распределение узлов. В двоичном дереве каждый узел имеет не больше двух потомков. А двоичное дерево поиска имеет еще несколько важных характеристик. Это дерево, в котором по-особому структурированы узлы:

• все левые потомки любого узла должны иметь значения, меньшие, чем значение самого этого узла;
• все правые потомки должны быть равны или больше по значению, чем родительский узел.

Это правило должно выполняться для любого поддерева в структуре.

Разновидности. Дерево может быть сбалансированным, то есть с оптимально распределенной древовидной структурой, идеально сбалансированным или вырожденным: в таком случае оно фактически становится линейным, так как у каждого узла есть только один потомок. Такие деревья иногда называют лозами. Скорость выполнения операций в них становится линейной, а в сбалансированных она ближе к логарифмической, что быстрее.

Есть и промежуточные варианты между сбалансированными и вырожденными деревьями. Чем лучше сбалансировано дерево, тем оно эффективнее. Сбалансированное дерево — такое, в котором все узлы, кроме конечных, имеют по два потомка, а все поддеревья одного уровня имеют одинаковую длину. Идеально сбалансированное дерево — как можно более широкое и низкое. Так его использование будет максимально продуктивным.

Особенности АВЛ-деревьев

АВЛ-дерево отличается от обычного бинарного дерева поиска несколькими особенностями:

• оно сбалансировано по высоте. Поддеревья, которые образованы левым и правым потомками каждого из узлов, должны различаться длиной не более чем на один уровень;
• из первой особенности вытекает еще одна — общая длина дерева и, соответственно, скорость операций с ним зависят от числа узлов логарифмически и гарантированно;
• вероятность получить сильно несбалансированное АВЛ-дерево крайне мала, а риск, что оно выродится, практически отсутствует.

Сбалансированность такого дерева гарантирована, в отличие от так называемых рандомизированных деревьев, которые сбалансированы вероятностно — то есть с небольшой вероятностью структура все еще может выродиться.

Что такое балансировка

Балансировкой называют операцию, которая делает дерево более сбалансированным. В случае с АВЛ-деревьями ее применяют, если нарушается главное правило структуры: поддеревья-потомки одного узла начинают различаться больше чем на один уровень. Если разница в количестве уровней становится равна 2 или –2, запускается балансировка: связи между предками и потомками изменяются и перестраиваются так, чтобы сохранить правильную структуру.

Обычно для этого какой-либо из узлов «поворачивается» влево или вправо, то есть меняет свое расположение. Поворот может быть простым, когда расположение изменяет только один узел, или большим: при нем два узла разворачиваются в разные стороны. Большой поворот эффективен там, где не сработает обычный.

Станьте аналитиком данных и получите востребованную специальность

Вставка узлов в дерево

Если в структуру данных нужно добавить новую информацию, это нужно сделать по определенному алгоритму. Он такой во всех бинарных деревьях поиска, но в случае с АВЛ-деревом алгоритм несколько дополняется: за вставкой следует обязательная балансировка.

Вставка. Чтобы вставить узел в дерево, нужно пройти от его начала вниз, на каждом шаге сравнивая значение нового узла с текущими. Алгоритм доходит до конца какого-либо поддерева и делает новый узел правым или левым его потомком в зависимости от значения. Так сохраняется главное правило двоичного дерева поиска — требование к расположению элементов по значению.

Балансировка. Особенность АВЛ-деревьев тут в том, что после вставки надо проверить соотношение длин поддеревьев и, если нужно, провести балансировку. Причем балансировку может понадобиться проводить для нескольких уровней дерева — это нормально. Алгоритм для балансирования может спускаться вниз из начального узла или подниматься вверх от свежедобавленного, по ходу движения пересчитывать разницу высот и совершать повороты, если где-то обнаружилась разница в два уровня. Балансировка продолжается, пока все значения высот не пересчитаются, а дисбаланс не будет устранен.

Удаление узлов из дерева

Удалить узел также можно по стандартным правилам, принятым для бинарного дерева поиска, но опять же с несколькими нюансами.

Сначала в дереве ищется узел, который нужно удалить. Если такого узла нет, ничего не делается, а вот если он находится, все куда интереснее. Надо пройти по правому поддереву удаляемого узла и найти в нем узел с самым маленьким значением — назовем его min. После этого удаляемый узел нужно заменить на узел min, и структура дерева перестроится.

Если правого поддерева у удаляемого узла нет, вместо min на место узла подставляется его левый потомок. Если левого потомка тоже нет, значит, удаляемый узел — лист, то есть потомки у него отсутствуют в принципе. Тогда его можно просто удалить и ничего не подставлять на его место.

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

Как реализовать АВЛ-дерево

Реализация деревьев обычно сложнее, чем умозрительная структура. Но возможности для создания AVL trees есть практически в любых современных языках программирования: Java, C/C++, Python и других.

Сначала разработчик описывает структуру одного узла. Это может быть сущность, способная содержать в себе несколько переменных: в C++ для этого есть тип данных struct (структура), в Python для узла обычно создают свой класс, и так далее.

Программно описанный узел содержит в себе:

• какие-то данные, от значения которых, как говорилось выше, зависит расположение элемента — слева или справа от родителя;
• ссылки на левого и правого потомка;
• высота поддерева, которое начинается в этом узле, или разница высот между левым и правым поддеревьями.

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

Как сбалансировать АВЛ-дерево

Балансировка, добавление и удаление элементов — функции, которые прописываются отдельно. Обычно сначала разработчик реализует код, который совершает обычный поворот, а потом эта функция используется в другой, более крупной, отвечающей за балансировку.

Код функции балансировки сводится к проверке условий и выполнению поворотов, если проверка обнаружила дисбаланс. Сначала выполняется один простой поворот, потом, если это не помогло, — второй для другого потомка и в противоположную сторону. Так реализуется большой поворот.

Программная реализация поворота сводится к перестановке ссылок, соединяющих между собой элементы дерева. После этого пересчитываются числовые значения, которые показывают разницу между высотами.

Реализация вставки и удаления

Вставка. Функция, вставляющая элемент, обычно рекурсивная, то есть вызывает сама себя. Ее можно реализовать довольно изящно:

• вызываем функцию в начальном узле;
• если значение, которое надо вставить, меньше значения узла, где мы находимся, идем налево — вызываем ту же функцию для левого потомка;
• если значение равно или больше тому, где мы сейчас, идем направо — вызываем функцию для правого потомка;
• если мы попали в точку, где еще нет узла, создаем там узел и помещаем туда новое значение;
• вызываем функцию балансировки. Так как вставка рекурсивная, балансировка выполнится начиная с последнего открытого экземпляра функции вставки и заканчивая первым.

Удаление. Функция удаления также рекурсивная, но она сложнее. Сначала надо найти удаляемый элемент, затем перейти в его правого потомка, если он есть, и найти там минимальный узел. А потом начинаются нюансы:

• по логике структуры бинарного дерева поиска у минимального узла может быть максимум один потомок — справа. Поэтому функция, «удаляющая» минимальный узел, возвращает его правого потомка — он пригодится при замене;
• минимальный узел не удаляется безвозвратно, а подставляется на место удаляемого — опять же происходит замена ссылок;
• слева к минимальному узлу присоединяется левый потомок удаляемого узла, справа — то, что осталось от правого потомка после вычленения минимального;
• происходит балансировка.

Операции могут выглядеть сложными, особенно в части реализации. Но если вы разберетесь с тем, как работает логика деревьев, все станет понятнее. Чтобы узнать больше, можете воспользоваться нашим глоссарием или туториалами. А можете записаться на курсы и получить актуальные знания от профессионалов.

Аналитик данных

Аналитики влияют на рост бизнеса. Они выясняют, какой товар и в какое время больше покупают. Считают юнит-экономику. Оценивают окупаемость рекламной кампании. Поэтому компании ищут и переманивают таких специалистов.