АВЛ-дерево: баланс по высоте

Если ты знаешь правило АВЛ (баланс каждого узла в пределах ±1), четыре случая перекоса LL/RR/LR/RL и какой поворот их чинит, и понимаешь, почему это держит высоту Θ(log n), листай до «Теперь сам».

Как думаешь, какое правило заставит дерево оставаться низким

Вращение умеет чинить перекос, но КОГДА его применять? Нужно правило-сторож: признак, по которому дерево понимает «я слишком перекосилось, пора поворачивать». Самый прямой признак - ВЫСОТА поддеревьев. Если у какого-то узла одно поддерево намного выше другого, дерево в этом месте вытягивается. Значит правило должно ограничивать РАЗНИЦУ высот. Насколько строго? Потребуем разницу 0 - это невыполнимо уже при двух узлах. Не ограничим вовсе - вернётся вырождение. Золотая середина - разрешить разницу не больше 1: дерево остаётся почти идеальным (высота Θ(log n)), а чинить надо лишь изредка. Это и есть правило АВЛ.

На что это похоже

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

Механизм: баланс узла и четыре случая

В каждом узле хранят его ВЫСОТУ: высота(узел) = 1 + max(высота левого, высота правого), у пустого поддерева 0 (или сразу баланс). После вставки нового листа поднимаемся к корню, обновляя высоты; в первом узле, где баланс стал +2 или −2, чиним поворотом. Четыре случая (по тому, с какой стороны и как пришёл перекос):

LL (лево-лево):  перекос влево, и у левого ребёнка тяжёлое ЛЕВО  -> ОДНО правое вращение
RR (право-право): перекос вправо, у правого ребёнка тяжёлое ПРАВО -> ОДНО левое вращение
LR (лево-право): перекос влево, но у левого ребёнка тяжёлое ПРАВО ->
                 сперва левое вращение ребёнка, потом правое узла  (ДВОЙНОЙ)
RL (право-лево): перекос вправо, у правого ребёнка тяжёлое ЛЕВО   ->
                 сперва правое вращение ребёнка, потом левое узла  (ДВОЙНОЙ)

Простое правило распознавания: если перекос «прямой» (обе тяжёлые стороны в одну сторону, LL или RR) - хватает ОДНОГО поворота. Если «ломаный» (перекос узла в одну сторону, а ребёнка в другую, LR или RL) - нужен ДВОЙНОЙ: сначала выпрямляем ребёнка одним поворотом (превращая ломаный случай в прямой), потом чиним узел. Одна вставка требует не более ОДНОГО поворота (пусть и двойного); удаление - до O(log n) поворотов по пути вверх. Всё - O(log n).

Правило

АВЛ-дерево держит в КАЖДОМ узле разницу высот левого и правого поддеревьев в пределах ±1 (баланс −1, 0, +1). Это гарантирует высоту Θ(log n), а значит все операции Θ(log n). После вставки/удаления идут вверх к корню, обновляя высоты, и в первом разбалансированном узле (±2) чинят ВРАЩЕНИЕМ: прямые перекосы LL/RR - одинарным, ломаные LR/RL - двойным (сперва выпрямить ребёнка, потом узел). Вставка - не больше одного (двойного) поворота, удаление - до O(log n) поворотов. Строгий баланс = очень малая высота = самый быстрый поиск среди сбалансированных деревьев.

Разбор: почему баланс ±1 гарантирует высоту Θ(log n)

Докажем, что строгое правило не даёт дереву вытянуться. Спросим наоборот: каково МИНИМАЛЬНОЕ число узлов в АВЛ-дереве высоты h? Обозначим его N(h). Самое «худое» допустимое дерево высоты h имеет корень, одно поддерево высоты h−1 и другое высоты h−2 (разница ровно 1 - максимум, что позволено). Значит N(h) = 1 + N(h−1) + N(h−2) (N(1) = 1, N(2) = 2) - почти рекуррентность ФИБОНАЧЧИ: N(h) = F(h+2) − 1. Числа Фибоначчи растут ЭКСПОНЕНЦИАЛЬНО (как φ^h, где φ ≈ 1.618 - золотое сечение), и отсюда n ≥ N(h) ≥ φ^(h−1): самое худое дерево высоты h всё равно содержит экспоненциально много узлов. Значит h ≤ log_φ n + 1 ≈ 1.44·log₂ n + 1. То есть высота АВЛ-дерева не больше примерно 1.44·log₂ n - всего на 44% выше идеальной. Правило «разница ≤ 1» через Фибоначчи запирает высоту в Θ(log n): перекос просто не успевает накопиться, каждый уровень обязан быть достаточно «полным».

Разбор: почему для АВЛ хватает четырёх случаев и почему LR/RL - двойные

Кажется, перекосов должно быть много, но их ровно четыре, потому что описываются двумя двоичными выборами: с какой стороны перекошен УЗЕЛ (лево/право) и с какой стороны тяжелее у его РЕБЁНКА (лево/право). Совпали направления (лево-лево, право-право) - перекос «прямой», как наклонённая палка: одно вращение ставит её вертикально. Разошлись (лево-право, право-лево) - перекос «ломаный», как согнутое колено: одним поворотом не выпрямить, потому что тяжёлое поддерево ребёнка при повороте узла осталось бы посередине и снова перекосило бы. Поэтому сперва поворачивают РЕБЁНКА - это распрямляет колено, превращая LR в LL (или RL в RR), - и только потом поворачивают узел. Двойной поворот - не отдельная магия, а два одинарных подряд; важно лишь распознать, что случай ломаный, и повернуть в правильном порядке.

Что ломается без этого

Первая ошибка - применить ОДИНАРНЫЙ поворот к ломаному случаю (LR/RL): перекос не исчезнет, а переедет на другую сторону - дерево останется разбалансированным. Ломаные случаи требуют двойного поворота, и распознать их надо по направлению перекоса ребёнка. Вторая - забыть ОБНОВИТЬ высоты узлов после вставки и после поворотов: баланс будет считаться по старым высотам, и сторож перестанет срабатывать. Третья - чинить не в ПЕРВОМ разбалансированном узле снизу, а где попало: чинить надо в ближайшем к листу нарушенном узле, поднимаясь вверх. Четвёртая - думать, что при удалении хватит одного поворота, как при вставке: удаление может потребовать поворотов на всём пути вверх (до O(log n)), а не одного.

Зачем это в работе

АВЛ-деревья - выбор там, где ПОИСКОВ гораздо больше, чем вставок/удалений: строгий баланс даёт минимальную высоту (≤ 1.44·log₂ n + 1), а значит самый быстрый поиск среди сбалансированных деревьев. Их берут для индексов, читаемых часто и меняемых редко, и в задачах, где важна предсказуемо малая высота. Но у строгости есть цена: АВЛ поворачивает чаще (после многих удалений - до O(log n) поворотов), поэтому для нагрузок с частыми изменениями чаще берут красно-чёрное дерево (следующий урок) - оно балансирует слабее, зато вращает реже. Понимать АВЛ важно и само по себе, и как эталон «строгого» баланса, с которым сравнивают все остальные: это первый ответ на вырождение из прошлой главы - правило ±1 плюс вращения превращают Θ(n) худшего случая в гарантированные Θ(log n).

Теперь сам

В АВЛ-дерево вставляют по очереди 3, 2, 1. После какой вставки нарушится баланс, в каком узле, какой это случай и какой поворот его чинит?