Открыть сервис
Главная → Блог → AVL-дерево

AVL-дерево

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

История

Понятие сбалансированного дерева было предложено Адельсоном-Вельским и Ландисом в статье «Один алгоритм организации информации» (1962), опубликованной в журнале «Доклады Академии наук СССР». В этой работе авторы формализовали понятие «сбалансированности» как разности высот поддеревьев не более 1 и описали механизмы восстановления баланса — вращения. Изначально алгоритм был разработан для реализации эффективного поиска в больших наборах данных, хранящихся в оперативной памяти. В 1960-е годы, когда вычислительные ресурсы были ограничены, AVL-деревья стали важным шагом в развитии теории структур данных, доказав, что логарифмическая сложность операций возможна без дополнительных ограничений на входные данные. Позднее, в 1970-х, появились другие типы сбалансированных деревьев, такие как красно-чёрные деревья, но AVL-деревья остаются актуальными благодаря более строгому балансу, что даёт преимущество в операциях поиска.

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

Определение и инварианты

AVL-дерево является двоичным деревом поиска, то есть для каждого узла выполняется:

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

Дополнительно накладывается условие баланса: для любого узла v высота левого поддерева h_left(v) и высота правого поддерева h_right(v) удовлетворяют неравенству: `` |h_left(v) - h_right(v)| ≤ 1 `` Высота пустого поддерева (отсутствующего узла) принимается равной −1, а высота листа (узла без потомков) — 0.

Высота и количество узлов

Минимальное количество узлов в AVL-дереве высоты h описывается рекуррентным соотношением: `` N_min(h) = N_min(h-1) + N_min(h-2) + 1 ` с начальными условиями N_min(0) = 1, N_min(1) = 2. Это соотношение совпадает с числами Фибоначчи, смещёнными на единицу. Максимальное количество узлов при высоте h — это полное двоичное дерево, содержащее 2^(h+1) - 1 узлов. Из этих оценок следует, что высота AVL-дерева с n узлами не превышает 1.44 * log2(n + 2) - 0.328`, что гарантирует логарифмическую сложность операций.

Операции

Поиск

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

Вставка

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

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

Существует четыре типа вращений:

  • Левое вращение (LL): выполняется, когда дисбаланс вызван вставкой в левое поддерево левого потомка.
  • Правое вращение (RR): симметрично левому, для вставки в правое поддерево правого потомка.
  • Лево-правое вращение (LR): сначала левое вращение левого потомка, затем правое вращение исходного узла.
  • Право-левое вращение (RL): сначала правое вращение правого потомка, затем левое вращение исходного узла.

Каждое вращение выполняется за O(1), а количество узлов, требующих восстановления, ограничено высотой дерева, поэтому вставка в целом имеет сложность O(log n).

Удаление

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

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

Сложность удаления — O(log n).

Реализация

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

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

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

Коэффициент баланса balance_factor вычисляется как разность высот правого и левого поддеревьев: `` balance_factor = height(right) - height(left) ` В сбалансированном дереве balance_factor` может принимать значения −1, 0 или 1.

Алгоритм вставки (псевдокод)

``` function insert(node, key): if node is None: 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 ```

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

AVL-дерево и красно-чёрное дерево

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

  • AVL-деревья обеспечивают более быстрый поиск (в среднем на 10–20% быстрее) за счёт меньшей высоты;
  • красно-чёрные деревья быстрее при вставке и удалении, так как требуют меньше вращений (в среднем O(1) против O(log n) для AVL).

В системах реального времени, где важна предсказуемость времени поиска, AVL-деревья могут быть предпочтительнее. В библиотеках стандартных контейнеров (например, std::map в C++ или TreeMap в Java) чаще используются красно-чёрные деревья из-за лучшей производительности при модификациях.

AVL-дерево и B-дерево

B-деревья (и их варианты, такие как B+ деревья) предназначены для работы с данными, хранящимися на диске, где доступ к памяти является узким местом. Они имеют высокий коэффициент ветвления (десятки или сотни потомков на узел), что уменьшает количество операций ввода-вывода. AVL-деревья, напротив, оптимизированы для оперативной памяти и имеют коэффициент ветвления, равный 2.

Применение

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

  • Базы данных: в некоторых системах управления базами данных (СУБД) для индексации данных в оперативной памяти.
  • Компиляторы: для построения таблиц символов и синтаксических деревьев.
  • Алгоритмы обработки данных: в задачах, требующих поддержания упорядоченного множества с быстрым поиском, например, в системах управления памятью.
  • Графические приложения: для организации сцен и быстрого поиска объектов по координатам.

Критика и ограничения

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

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

  • Название «AVL» происходит от первых букв фамилий авторов: Адельсон-Вельский и Ландис.
  • В оригинальной статье 1962 года авторы не использовали термин «AVL-дерево»; он появился позже в англоязычной литературе.
  • Георгий Адельсон-Вельский (1922–2014) внёс вклад также в теорию игр и искусственный интеллект, а Евгений Ландис (1921–1997) известен работами по математической физике и теории автоматов.

Источники

  • Адельсон-Вельский Г. М., Ландис Е. М. Один алгоритм организации информации // Доклады АН СССР. — 1962. — Т. 146, № 2. — С. 263–266.
  • Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013. — Глава 12.
  • Кнут Д. Э. Искусство программирования. Том 3. Сортировка и поиск. — 2-е изд. — М.: Вильямс, 2007. — Раздел 6.2.3.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →

Похожие материалы