Конспект: вращения, АВЛ и красно-чёрное

Понятия

Вращение - локальная перестройка O(1), меняющая ФОРМУ (высоту) поддерева и СОХРАНЯЮЩАЯ инвариант BST. ПРАВОЕ поднимает левого ребёнка (лечит перекос влево), ЛЕВОЕ - правого. Порядок цел, потому что СЕРЕДИННОЕ поддерево перевешивается на освободившееся между узлами место. Меняются 3-4 ссылки. Из вращений собраны ВСЕ балансировки.

АВЛ-дерево - баланс по ВЫСОТЕ: в каждом узле разница высот поддеревьев ≤ 1. Высота ≤ 1.44·log₂ n + 1 (через числа Фибоначчи). Четыре случая нарушения: - LL, RR (прямой перекос) - ОДИНАРНЫЙ поворот; - LR, RL (ломаный) - ДВОЙНОЙ (сперва выпрямить ребёнка, потом узел). Вставка - ≤ 1 (двойного) поворота, удаление - до O(log n).

Красно-чёрное дерево - баланс по ЦВЕТУ: чёрных узлов на всех путях вниз поровну (чёрная высота), у красного нет красных детей, корень чёрный, новый узел красный. Отсюда длинный путь ≤ 2× короткого, высота ≤ 2·log₂(n+1). Изменения дешевле: вставка ≤ 2 вращений, удаление ≤ 3, многое лечится ПЕРЕКРАСКОЙ (O(1)).

Что унести

Все сбалансированные деревья - это BST + вращения; отличаются правилом баланса и, как следствие, компромиссом «высота ↔ число правок».

Закон компромисса: строгость баланса покупается частотой правок - идеала «низко И редко чинить» не существует. Оба дают Θ(log n) на всё и обход по порядку за Θ(n); выбор решает профиль нагрузки. Стандартные библиотеки (std::map, TreeMap, ядро Linux) берут красно-чёрное как универсал. Оба несравнимо лучше голого BST, который вырождается до Θ(n).

Главное: вращение сохраняет порядок и стоит O(1) - потому балансировка почти бесплатна (O(log n) поворотов на операцию), и худший случай BST превращается в гарантированные Θ(log n).

Ловушки джокера

Потерять серединное поддерево при вращении или подвесить не туда - нарушишь порядок, дерево перестанет быть BST.

Не обновить ссылку у родителя вращаемого узла - новый корень поддерева повиснет.

Одинарный поворот для ломаного случая (LR/RL) - перекос переедет на другую сторону. Нужен двойной.

Не обновлять высоты в АВЛ после вставки и поворотов - сторож перестанет срабатывать.

Красить новый узел чёрным в красно-чёрном - собьёт чёрную высоту. Красят КРАСНЫМ.

Выбирать дерево «по привычке», не глядя на нагрузку - АВЛ под запись-интенсив (лишние вращения) или красно-чёрное там, где критичен поиск.

Брать голый BST «для простоты» - никакой гарантии высоты, вырождение.

Проверь себя

Что меняет вращение и почему сохраняет порядок?

В чём правило АВЛ и почему оно даёт высоту ≤ 1.44·log₂ n + 1?

Чем LL/RR отличаются от LR/RL и какой поворот их чинит?

Как красно-чёрное дерево через цвет добивается высоты Θ(log n)?

Когда брать АВЛ, а когда красно-чёрное, и почему «строже» значит «чаще правки»?