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

АВЛ-деревья

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

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

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

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

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

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

Поле 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, она может работать и с нулевыми указателями (с пустыми деревьями):

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Русские Блоги

, Добавление и удаление элементов может потребоваться заимствовать один или несколько разВращение дереваДля достижения ребалансировки дерева. Дерево AVL названо в честь его изобретателяG. M. Adelson-Velsky с Evgenii LandisОни опубликовали эту структуру данных в статье 1962 года «Алгоритм организации информации».

1 Почему должно быть сбалансированное бинарное дерево?

Дерево двоичного поиска может в некоторой степени повысить эффективность поиска, но когда упорядочена исходная последовательность, например, последовательность A = , дерево двоичного поиска строится, как показано на рисунке 1.1. Двоичное дерево поиска, построенное в соответствии с этой последовательностью, является деревом с прямым углом, и в то же время двоичное дерево вырождается в один связанный список, и эффективность поиска снижается до O (n).

Поиск элемента 6 в этом бинарном дереве поиска требует 6 поисков.

Эффективность поиска бинарного дерева поиска зависит от высоты дерева, поэтому поддержание минимальной высоты дерева может обеспечить эффективность поиска дерева. Та же самая последовательность A, которая хранится способом, показанным на рисунке 1.2, должна сравниваться только 3 раза при поиске элемента 6, и эффективность поиска удваивается.

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

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

2. Определение

Сбалансированное двоичное дерево поиска: Называется сбалансированным двоичным деревом. Математики из бывшего Советского СоюзаAdelse-Vэльскиль иLВысоко сбалансированное бинарное дерево, предложенное andis в 1962 году, также называется AVL-деревом в соответствии с английским именем ученого. Он имеет следующие свойства:

1. Может быть пустым деревом.
2. Если это не пустое дерево, то левое и правое поддеревья любого узла являются сбалансированными двоичными деревьями, и абсолютное значение разности высот не превышает 1.

Значение баланса, такого как баланс, означает, что компоненты с обеих сторон примерно одинаковы.

Например, рисунок 2.1 не является сбалансированным двоичным деревом, потому что левое поддерево узла 60 не является сбалансированным двоичным деревом.

Рисунок 2.2 также не является сбалансированным двоичным деревом, потому что, хотя левое и правое поддеревья любого узла являются сбалансированными двоичными деревьями, разница в высоте превысила 1.

Рисунок 2.3НеСбалансировать двоичное дерево.

3. Баланс фактор

определение:Разница между высотой (глубиной) левого и правого поддеревьев узла — это коэффициент баланса (BF) узла. В сбалансированном двоичном дереве нет узла с коэффициентом баланса больше 1. В сбалансированном двоичном дереве коэффициент баланса узла может быть только 0, 1 или -1, что соответствует равной высоте левого и правого поддеревьев, левого поддерева относительно высоко, а правого поддерева относительно высоко.

4. Узловая структура

Определите структуру узла сбалансированного двоичного дерева:

5. Дисбаланс и регулировка при вставке дерева AVL

Рисунок 5.1 — сбалансированное двоичное дерево

Вставив узел 99 в сбалансированное двоичное дерево здесь, структура дерева становится:

На рисунке 5.2 высота левого поддерева узла 66 равна 1, а высота правого поддерева равна 3. В это время коэффициент баланса равен -2, а дерево вышло из равновесия.

На рисунке 5.2 дерево с узлом 66 в качестве родительского узла называетсяМинимальный дисбаланс поддерева。

Минимальный дисбаланс поддерева: Поиск недавно вставленного узла с первым коэффициентом балансаАбсолютная величинаПоддерево, корень которого больше 1, называется наименьшим несбалансированным поддеревом. Другими словами, несбалансированное дерево может иметь несколько несбалансированных поддеревьев одновременно. В это время, пока мы настраиваем наименьшее несбалансированное поддерево, мы можем настроить несбалансированное дерево на сбалансированное дерево.

Корректировка дисбаланса сбалансированного двоичного дерева в основном достигается путем вращения наименьшего поддерева дисбаланса, Есть два метода обработки в зависимости от направления вращения,Левая рука против Правая рука 。

Целью поворота является уменьшение высоты и баланса путем уменьшения высоты всего дерева. Там, где дерево на другой стороне высоко, поверните дерево на той стороне вверх.

5.1 Левая рука

Взяв рисунок 5.1.1 в качестве примера, после добавления нового узла 99 высота левого поддерева узла 66 равна 1, а высота правого поддерева — 3. В это время коэффициент баланса равен -2. Чтобы обеспечить баланс дерева, необходимо повернуть узел 66 в это время, потому что высота правого поддерева выше, чем левое поддерево, и выполняется операция левой стороны узла. Процесс заключается в следующем:

(1) Правый потомок узла заменяет эту позицию узла (2) Левый потомок правого потомка становится правым поддеревом узла (3) Сам узел становится левым потомком правого потомка

Весь рабочий процесс показан на рисунке 5.1.2.

• Правый потомок узла заменяет это положение узла — правый потомок узла 66 — это узел 77, замените узел 77 положением узла 66
• Левое поддерево правого потомка становится правым поддеревом узла 77. Левое поддерево узла — это узел 75, переместите узел 75 в правое поддерево узла 66.
• Сам узел становится левым поддеревом правого дочернего узла 66, становится левым поддеревом узла 77

5.2 Правильно

Правая операция аналогична левой операции, и последовательность операций:

(1) Левый дочерний узел представляет этот узел. (2) Правое поддерево левого дочернего узла становится левым поддеревом узла. (3) Используйте этот узел в качестве правого поддерева левого дочернего узла.

6. Четыре способа вставить узлы в дерево AVL

Предполагая, что узлом дерева AVL является A, есть четыре операции, которые сделают разницу в высоте между левым и правым поддеревьями A больше 1, тем самым нарушая баланс исходного дерева AVL. Существует четыре типа узлов вставки сбалансированного двоичного дерева:

| Способ вставки | Описание | Способ вращения | | ——— | ——————————- ———————— | ———— | | LL | ВЛевое поддеревоКорневой узелЛевое поддеревоВставить узел сверху и разбить баланс | повернуть вправо | | RR | в AПравое поддеревоКорневой узелПравое поддеревоВставить узел сверху и разбить баланс | Повернуть влево | | LR |Левое поддеревоКорневой узелПравое поддеревоВставьте узел, чтобы нарушить баланс | левша, затем правша | | RL | в AПравое поддеревоКорневой узелЛевое поддеревоВставьте узел вверх, чтобы нарушить баланс | Правша, затем левша |

Конкретный анализ заключается в следующем:

6.1 Левый потомок левого потомка А вставляет узел (LL)

Вам нужно выполнить правый поворот только один раз.

Код реализации выглядит следующим образом:

6.2 Правый потомок правого потомка А вставляет узел (RR)

Вам нужно выполнить левый поворот только один раз.

Код реализации выглядит следующим образом:

6.3 Правый потомок левого потомка А вставляет узел (LR)

Если правое дочернее дерево E левого дочернего узла A вставлено в узел F, узел A становится несбалансированным, как показано на рисунке:

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

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

(1) Выполните левостороннюю операцию на левом дочернем элементе B неуравновешенного узла A, что является операцией в вышеописанном случае RR. (2) Правая операция выполняется на несбалансированном узле A, то есть операция в вышеупомянутом случае LL.

Процесс настройки выглядит следующим образом:

Другими словами, после этих двух шагов,Правый дочерний узел E левого дочернего узла исходного корневого узла становится новым корневым узлом。

6.4 Вставить узел (RL) левого поддерева правого потомка A

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

(1) Выполните правую операцию на правом дочернем элементе C неуравновешенного узла A, которая является операцией в описанной выше ситуации LL. (2) Выполните операцию левой руки на несбалансированном узле A, которая является операцией в случае RR выше.

Другими словами, после этих двух шагов,Левый дочерний узел D правого дочернего узла исходного корневого узла становится новым корневым узлом。

Вспомогательные коды, реализованные в вышеупомянутых четырех режимах вставки, следующие:

6.5 Резюме

1. При всех дисбалансах следуйте первомуНайдите самое маленькое неуравновешенное дерево, ЗатемНайти категорию дисбаланса, СноваУправляйте фиксированными программами в соответствии с 4 категориями。
2. LL, LR, RR, RL фактически предоставили нам последний узел в качестве нового корня, чтобы указать направление. Например, последний корневой узел типа LR является правым потомком исходного левого потомка, а последний корневой узел типа RL является левым потомком исходного правого потомка. Пока вы помните эти четыре ситуации, вы можете быстро вывести все ситуации.
3. Наиболее проблемной частью поддержания сбалансированного бинарного дерева является поддержание факторов баланса. Читателям рекомендуется рисовать собственные картинки на основе картинок и анимаций, предоставленных Сяо Ву, чтобы они могли более эмоционально понять эту операцию.

7. Четыре способа удаления узлов в дереве AVL

Операции удаления дерева AVL и дерева двоичного поиска одинаковы и делятся на четыре случая:

(1) Удалить листовой узел (2) Удаленный узел имеет только левое поддерево (3) Удаленный узел имеет только правое поддерево (4) Удаленный узел имеет как левое, так и правое поддерево

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

Основные шаги операции удаления следующие:

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

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

подводить итоги

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

АВЛ-дерево

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Двоичное дерево

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

Типы двоичных деревьев

Полное двоичное дерево

Полное двоичное дерево — особый тип бинарных деревьев, в котором у каждого узла либо 0 потомков, либо 2.

Совершенное двоичное дерево

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

Законченное двоичное дерево

Законченное двоичное дерево похоже на совершенное, но есть три большие отличия.

1. Все уровни должны быть заполнены.
2. Все листовые вершины склоняются влево.
3. У последней листовой вершины может не быть правого собрата. Это значит, что завершенное дерево необязательно полное.

Вырожденное двоичное дерево

Вырожденное двоичное дерево — дерево, в котором на каждый уровень приходится по одной вершине.

Скошенное вырожденное дерево

Скошенное вырожденное дерево — вырожденное дерево, в котором есть либо только левые, либо только правые узлы. Таким образом, есть два типа скошенных деревьев — скошенные влево вырожденные деревья и скошенные вправо вырожденные деревья.

Сбалансированное двоичное дерево

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

Представление двоичного дерева

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