АВЛ-дерево

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

История

АВЛ-дерево было предложено в 1962 году в работе «Алгоритм организации информации» (авторы: Г. М. Адельсон-Вельский, Е. М. Ландис), опубликованной в журнале «Доклады Академии наук СССР». До этого основным способом организации данных в оперативной памяти были неотбалансированные бинарные деревья поиска, которые в худшем случае (например, при вставке отсортированных данных) вырождались в линейный список, сводя сложность операций к O(n). Разработка АВЛ-дерева решила эту проблему, введя строгий критерий баланса и механизм его восстановления.

В 1964 году Ландис и Адельсон-Вельский опубликовали расширенное описание, а впоследствии структура вошла во все классические учебники по алгоритмам и структурам данных. В 1970-х годах появились альтернативные самобалансирующиеся деревья (например, красно-чёрные деревья), которые менее строго контролируют баланс, но требуют меньше операций при вставке и удалении. Тем не менее АВЛ-дерево остаётся востребованным в приложениях, где критична скорость поиска.

Определение и свойства

Бинарное дерево поиска

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

• все ключи в левом поддереве меньше ключа данного узла;
• все ключи в правом поддереве больше ключа данного узла.

Коэффициент сбалансированности

Для каждого узла вводится характеристика — коэффициент сбалансированности (balance factor), вычисляемый как разность высот левого и правого поддеревьев: \[ BF = h(левое) - h(правое) \] Высота пустого поддерева принимается равной −1. В АВЛ-дереве для всех узлов выполняется условие: \[ BF \in \{-1, 0, 1\} \] Если после вставки или удаления узла это условие нарушается, дерево считается разбалансированным и требует перестройки.

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

Высота АВЛ-дерева с n узлами в худшем случае составляет примерно \( \log_{\varphi}(n+2) - 1 \), где \(\varphi\) — золотое сечение (≈1,618). Это даёт оценку \( O(\log n) \). Минимальная высота для n узлов — \( \lceil \log_2(n+1) \rceil \). Таким образом, все основные операции выполняются за логарифмическое время.

Операции

Поиск

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

Вставка

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

1. Стандартная вставка в бинарное дерево поиска: узел добавляется как лист в соответствующую позицию.
2. Балансировка: после вставки необходимо проверить коэффициенты сбалансированности всех узлов на пути от нового узла к корню. Если у какого-либо узла коэффициент выходит за пределы \([-1, 1]\), выполняется одно из четырёх вращений (см. ниже).

Удаление

Удаление узла также состоит из двух этапов:

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

Вращения

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

• Правый поворот (LL-поворот): выполняется, когда левое поддерево узла на два уровня выше правого (BF = 2), и левый потомок имеет BF = 0 или 1.
• Левый поворот (RR-поворот): выполняется, когда правое поддерево узла на два уровня выше левого (BF = −2), и правый потомок имеет BF = 0 или −1.
• Левый-правый поворот (LR-поворот): сначала левый поворот вокруг левого потомка, затем правый поворот вокруг исходного узла. Применяется при BF = 2 и BF левого потомка = −1.
• Правый-левый поворот (RL-поворот): сначала правый поворот вокруг правого потомка, затем левый поворот вокруг исходного узла. Применяется при BF = −2 и BF правого потомка = 1.

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

Сравнение с другими структурами

Красно-чёрное дерево

Красно-чёрное дерево — менее строго сбалансированная структура: оно гарантирует, что высота не превышает \( 2 \log_2(n+1) \). Вставка и удаление в красно-чёрном дереве требуют в среднем меньше поворотов (не более 2 при вставке, не более 3 при удалении), чем в АВЛ-дереве (до \( O(\log n) \) при удалении). Однако АВЛ-дерево обеспечивает более быстрый поиск, так как его высота ближе к минимально возможной.

Декартово дерево (treap)

Декартово дерево сочетает свойства бинарного дерева поиска и кучи, используя случайные приоритеты. Оно не требует явных поворотов для балансировки, но его высота в среднем \( O(\log n) \), а в худшем случае — \( O(n) \). АВЛ-дерево гарантирует логарифмическую высоту в любом случае.

B-деревья

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

Применение

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

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

Реализация

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

• insert(node, key) — вставка с рекурсивной балансировкой.
• delete(node, key) — удаление с рекурсивной балансировкой.
• search(node, key) — поиск.
• rotate_left(node) и rotate_right(node) — повороты.
• balance(node) — проверка и применение необходимого поворота.

Пример рекурсивной вставки на псевдокоде:

`` function insert(node, key): if node is None: return new_node(key) if key < node.key: node.left = insert(node.left, key) else: node.right = insert(node.right, key) node.height = 1 + max(height(node.left), height(node.right)) return balance(node) ``

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

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

Источники

• Адельсон-Вельский Г. М., Ландис Е. М. Алгоритм организации информации // Доклады АН СССР. — 1962. — Т. 146, № 2. — С. 263–266.
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013. — 1328 с. — ISBN 978-5-8459-1794-2.
• Седжвик Р. Фундаментальные алгоритмы на C++. — М.: ДиаСофт, 2002. — 688 с. — ISBN 5-93772-047-4.
• Кнут Д. Э. Искусство программирования. Том 3. Сортировка и поиск. — 2-е изд. — М.: Вильямс, 2007. — 832 с. — ISBN 978-5-8459-1314-2.