АВЛ-деревья

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

История

Идея сбалансированного дерева поиска возникла как ответ на проблему вырождения обычных двоичных деревьев поиска. При неупорядоченной вставке элементов дерево может выродиться в линейный список, что приводит к снижению производительности операций до O(n). В 1962 году советские математики Георгий Максимович Адельсон-Вельский и Евгений Михайлович Ландис, работавшие в Институте теоретической и экспериментальной физики (ИТЭФ), предложили механизм автоматической балансировки дерева после каждой операции вставки и удаления.

Свою работу они опубликовали в статье «An algorithm for the organization of information» в журнале «Доклады Академии наук СССР» (том 146, 1962 год). В ней впервые были формально определены условия балансировки и описаны повороты — операции, восстанавливающие баланс. АВЛ-деревья стали первым известным типом самобалансирующихся деревьев поиска, предшествуя красно-чёрным деревьям (1978) и другим структурам.

Основные свойства

Определение баланса

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

• Баланс-фактор (balance factor) вершины вычисляется как разность высоты левого поддерева и высоты правого поддерева: bf = h(left) - h(right).
• Для любой вершины АВЛ-дерева |bf| ≤ 1.

Высота дерева определяется как максимальное количество рёбер от корня до листа. Пустое дерево (null) имеет высоту -1 или 0 в зависимости от соглашения; в классической реализации высота пустого поддерева принимается равной -1.

Гарантированная высота

Благодаря условию балансировки высота АВЛ-дерева с n вершинами никогда не превышает 1.44 * log2(n + 2) — 0.328 (точная верхняя граница). Это означает, что все операции поиска, вставки и удаления выполняются за O(log n) в худшем случае.

Операции

Поиск

Поиск элемента в АВЛ-дереве выполняется так же, как в обычном двоичном дереве поиска, без дополнительных действий по балансировке. Сложность — O(log n).

Вставка

Вставка нового узла в АВЛ-дерево состоит из двух этапов:

1. Стандартная вставка в двоичное дерево поиска (рекурсивный спуск до листа).
2. Восстановление баланса — обратный проход от вставленного узла к корню с пересчётом высот и, при необходимости, выполнением поворотов.

Для восстановления баланса используются четыре типа поворотов:

• Левый поворот (Left Rotation) — выполняется, когда баланс-фактор вершины равен -2, а у правого дочернего узла баланс-фактор ≤ 0.
• Правый поворот (Right Rotation) — выполняется, когда баланс-фактор вершины равен 2, а у левого дочернего узла баланс-фактор ≥ 0.
• Левый-правый поворот (Left-Right Rotation) — комбинация левого поворота левого дочернего узла и последующего правого поворота исходной вершины.
• Правый-левый поворот (Right-Left Rotation) — комбинация правого поворота правого дочернего узла и последующего левого поворота исходной вершины.

Каждый поворот изменяет структуру дерева локально, переставляя не более трёх вершин, и выполняется за O(1). После вставки может потребоваться не более одного поворота на каждом уровне подъёма, но в среднем достаточно одного-двух поворотов.

Удаление

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

1. Стандартное удаление из двоичного дерева поиска (с заменой на максимальный элемент левого поддерева или минимальный элемент правого поддерева).
2. Обратный проход к корню с пересчётом высот и выполнением поворотов при нарушении баланса.

В отличие от вставки, при удалении может потребоваться несколько поворотов на разных уровнях, но общее количество поворотов остаётся O(log n).

Реализация

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

Типичная реализация узла АВЛ-дерева на языке программирования (например, C++ или Python) включает:

• ключ (key);
• значение (value) — опционально;
• указатели на левого и правого потомка;
• высоту (height) или баланс-фактор.

Пример на псевдокоде (вставка)

``` function insert(node, key): if node is null: return new node(key) if key < node.key: node.left = insert(node.left, key) else if key > node.key: node.right = insert(node.right, key) else: return node // ключ уже существует

node.height = 1 + max(height(node.left), height(node.right)) balance = get_balance(node)

// Левый-левый случай if balance > 1 and key < node.left.key: return right_rotate(node) // Правый-правый случай if balance < -1 and key > node.right.key: return left_rotate(node) // Левый-правый случай if balance > 1 and key > node.left.key: node.left = left_rotate(node.left) return right_rotate(node) // Правый-левый случай if balance < -1 and key < node.right.key: node.right = right_rotate(node.right) return left_rotate(node)

return node ```

Преимущества и недостатки

Преимущества

• Гарантированная логарифмическая сложность операций в худшем случае.
• Простота реализации по сравнению с более сложными структурами (например, B-деревьями).
• Эффективность для операций, требующих частого поиска при редких вставках и удалениях.

Недостатки

• Более строгие условия балансировки по сравнению с красно-чёрными деревьями, что приводит к большему количеству поворотов при вставке и удалении.
• Дополнительная память для хранения высоты или баланс-фактора в каждом узле (обычно 1-2 байта).
• При очень частых вставках и удалениях может быть менее эффективным, чем красно-чёрные деревья, из-за большего числа поворотов.

Применение

АВЛ-деревья широко используются в системах, где требуется быстрый поиск данных с гарантированной производительностью:

• Базы данных — как часть реализации индексов (хотя чаще применяются B-деревья).
• Файловые системы — для организации каталогов.
• Компиляторы — для хранения таблиц символов.
• Библиотеки стандартных контейнеров — например, в Java TreeMap и TreeSet реализованы на основе красно-чёрных деревьев, но АВЛ-деревья используются в некоторых реализациях std::map и std::set в C++ (хотя стандарт не требует конкретной структуры).
• Графические алгоритмы — для обработки сцен и определения видимости.

Сравнение с другими самобалансирующимися деревьями

АВЛ-деревья предпочтительнее, когда операции поиска преобладают над операциями модификации. Красно-чёрные деревья лучше подходят для сценариев с частыми вставками и удалениями.

Интересные факты

• Название «АВЛ» является аббревиатурой фамилий создателей: Адельсон-Вельский и Ландис.
• В оригинальной работе 1962 года авторы не использовали термин «поворот»; они описывали процедуру балансировки как «перестройку» дерева.
• АВЛ-деревья до сих пор используются в учебных курсах по алгоритмам и структурам данных как классический пример самобалансирующегося дерева.
• Существует модификация АВЛ-деревьев — «weight-balanced trees» (деревья, сбалансированные по весу), где балансировка основана на количестве узлов, а не на высоте.

Источники

• Адельсон-Вельский Г. М., Ландис Е. М. «An algorithm for the organization of information» // Доклады АН СССР, 1962.
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ» (CLRS), 3-е издание, глава 13.
• Седжвик Р. «Алгоритмы на C++», 5-е издание.
• Кнут Д. «Искусство программирования», том 3: «Сортировка и поиск».