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

Модуль "Деревья поиска" • урок 3 из 8 • ~7 минут

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

Проблема вырождения деревьев

Основное преимущество дерева поиска заключается в скорости операций: поиск, вставка и удаление выполняются за время, пропорциональное высоте дерева O(log N). Однако это справедливо только в том случае, если ветви дерева имеют примерно одинаковую длину. Если элементы поступают в дерево уже отсортированными по возрастанию, каждый новый элемент будет добавляться всегда в правое поддерево. В таком случае дерево "вырождается" в однонаправленный линейный список, и время всех операций катастрофически деградирует до O(N).

Вырождение дерева поиска: семь ключей вперемешку дают дерево высоты 3 с поиском за O(log N), а те же ключи по возрастанию - список высоты 7
Ключи те же самые - разница только в порядке, в котором они пришли

Сбалансированные деревья поиска: критерий АВЛ

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

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

Баланс узла

Для контроля баланса в каждый узел дерева добавляется служебное поле - баланс узла (в английских источниках balance factor). Он вычисляется как разница между высотой правого и левого поддерева: Balance(node) = Height(Right) - Height(Left). В АВЛ-дереве допустимыми значениями баланса для любого узла являются только -1, 0 или +1.

Если после вставки или удаления узла баланс становится равным +2 или -2, дерево считается несбалансированным, и к нему немедленно применяются специальные операции - повороты, которые мы рассмотрим в следующем уроке, чтобы восстановить критерий АВЛ.

Визуализация: баланс каждого узла

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

Сбалансированные деревья поиска: баланс узла равен высоте правого поддерева минус высота левого и принимает значения -1, 0 и +1
Баланс считается для каждого узла, а не для дерева целиком
А как в Python? В C++ контейнеры std::set и std::map гарантируют логарифмическую сложность именно за счет строгой внутренней балансировки (обычно используются красно-черные деревья, которые похожи на АВЛ, но имеют чуть менее строгий критерий). В Python, для задач, критичных к строгой сортировке и гарантированному O(log N) времени, используются сторонние модули. Реализация АВЛ-балансировки на чистом Python требует написания рекурсивного пересчета высот и выполнения поворотов после каждой операции insert или delete.

Коротко: главное

  • Сбалансированные деревья предотвращают вырождение дерева в список, сохраняя скорость поиска O(log N).
  • Критерий АВЛ: для КАЖДОЙ вершины высота правого и левого поддеревьев отличается не более чем на 1.
  • Баланс узла может принимать значения -1, 0 и +1. Значения +2 и -2 сигнализируют о необходимости применить повороты для ребалансировки.

Проверьте себя

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

Как вам урок? Спасибо за отзыв!