Вращение: перестроить дерево, не тронув порядок

Если ты умеешь сделать правое и левое вращение, знаешь, какое поддерево перевешивается и почему инвариант BST при этом цел, и понимаешь, что вращение - это O(1), листай до «Теперь сам».

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

Дерево перекосилось - одна ветка длинная, другая короткая. Пересобрать всё заново (вынуть все ключи, вставить в хорошем порядке) - это Θ(n) на каждую вставку, недопустимо дорого. Нужен ЛОКАЛЬНЫЙ приём: подправить пару узлов у места перекоса за константу, подняв глубокую ветку выше. Но есть жёсткое ограничение: нельзя нарушить порядок - после перестройки это всё ещё должно быть дерево поиска, иначе поиск сломается. Значит нужна операция, которая переставляет узлы, СОХРАНЯЯ инвариант «левое меньше, правое больше». Такая операция есть, и она всего одна (в двух зеркальных вариантах) - вращение.

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

Детские качели-балансир (перекладина на опоре). Если один конец перевесил и уткнулся в землю, ты сдвигаешь точку опоры - и тяжёлый конец поднимается, лёгкий опускается, не меняя, кто на каком конце сидит. Вращение дерева - ровно смена «точки опоры»: узел, который был корнем поддерева, опускается, а его ребёнок поднимается на его место. Порядок сидящих (кто больше, кто меньше) не меняется - меняется только, кто сверху. Один щелчок опоры - и перекос исправлен, никого не пересаживая.

Механизм: правое вращение

Пусть узел P перекошен влево: его левый ребёнок Q тяжёлый. Правое вращение вокруг P поднимает Q на место P:

правое_вращение(P):           # было: P сверху, Q = P.лево
    Q = P.лево
    P.лево = Q.право          # СЕРЕДИННОЕ поддерево (B) перевешиваем к P слева
    Q.право = P               # P опускается направо под Q
    вернуть Q                 # Q - новый корень поддерева

Разберём по ключам. Было: Q (с поддеревьями A слева, B справа) - левый ребёнок P (с поддеревом C справа). Порядок: A < Q < B < P < C. После правого вращения Q наверху: слева A, справа P; у P слева B, справа C. Порядок читается тот же: A < Q < (B < P < C) - инвариант цел. Единственное «движущееся» поддерево - B (серединное, между Q и P): оно было правым у Q, стало левым у P. Именно потому, что Q < B < P, его можно подвесить левым к P без нарушений. Меняются три ссылки: P.лево, Q.право и ссылка РОДИТЕЛЯ P, которая теперь должна указывать на Q (её присваивает тот, кто вызвал вращение) - O(1). Левое вращение - зеркально (для перекоса вправо).

Правило

Вращение - локальная перестройка O(1), меняющая форму (высоту) дерева, но сохраняющая инвариант BST. ПРАВОЕ вращение вокруг узла поднимает его левого ребёнка на его место (узел опускается направо); ЛЕВОЕ - зеркально. Порядок сохраняется потому, что СЕРЕДИННОЕ поддерево (между поднимаемым и опускаемым узлом) перевешивается на освободившееся место и по значению туда как раз подходит. Меняются лишь три-четыре ссылки. Из вращений собраны все балансировки: после вставки/удаления дерево делает несколько поворотов и восстанавливает малую высоту.

Разбор: почему именно серединное поддерево перевешивается, и почему это не ломает порядок

Вся корректность вращения держится на судьбе ОДНОГО поддерева - серединного. Обозначим ключи: поднимаем Q, опускаем P, Q < P. У Q есть правое поддерево B - его ключи между Q и P (Q < B < P). После вращения Q встаёт наверх, P - его правым ребёнком (это место занимал B), а у P освобождается ЛЕВОЕ место (раньше там был Q). Куда деть B? Оно должно оказаться там, где ключи Q < … < P - это ЛЕВОЕ поддерево P (всё левее P, но правее Q). Туда B и переезжает. Остальные поддеревья (A левее Q, C правее P) не двигаются - они и так на своих местах относительно нового расклада. Проверка порядка слева направо: A, Q, B, P, C - и до, и после вращения одно и то же. Поэтому вращение - не «перетасовка», а точная переклейка ровно одной ветки в единственно правильное место. Перепутаешь, куда её подвесить, - и получишь не BST.

Разбор: почему вращение - это O(1), а не O(h)

Легко подумать, что перестройка дерева дорога. Но вращение НЕ трогает содержимое поддеревьев A, B, C - оно лишь переставляет несколько ССЫЛОК: Q.право, P.лево, и ссылку родителя P (теперь она указывает на Q). Три-четыре присваивания, независимо от того, насколько велики поддеревья. Поэтому одно вращение - O(1). Это принципиально для балансировки: после вставки дерево может потребовать перебалансировки на всём пути от нового листа до корня, но на каждом уровне это лишь O(1)-вращения, а уровней O(h) = O(log n) - значит вся перебалансировка O(log n), не дороже самой вставки. Дешевизна вращения - вот что делает сбалансированные деревья практичными: держать баланс почти бесплатно.

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

Первая ошибка - при вращении «забыть» серединное поддерево (потерять B или подвесить его не туда): нарушишь порядок, дерево перестанет быть BST, поиск начнёт промахиваться. Серединное поддерево всегда переезжает на освободившееся место между двумя узлами. Вторая - не обновить ссылку у РОДИТЕЛЯ вращаемого узла: новый корень поддерева (Q) повиснет в воздухе, а родитель продолжит указывать на старый (P). Третья - путать левое и правое вращение: правое лечит перекос ВЛЕВО (поднимает левого ребёнка), левое - перекос вправо; выбрать не то - и перекос усилится. Четвёртая - думать, что одно вращение всегда чинит баланс: иногда нужен ДВОЙНОЙ поворот (следующий урок про АВЛ) - сперва у ребёнка, потом у узла.

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

Вращение - атом всех самобалансирующихся деревьев. АВЛ-деревья, красно-чёрные деревья (эта глава), декартовы деревья (дальше в разделе) - все восстанавливают баланс ИСКЛЮЧИТЕЛЬНО вращениями; отличаются лишь тем, КОГДА и какие повороты делать. Понимать вращение - значит понимать механику, общую для std::map, TreeMap и индексов БД: после каждой вставки/удаления дерево делает O(log n) локальных O(1)-поворотов и держит высоту малой. Это и ответ на вопрос «почему сбалансированное дерево лишь ненамного медленнее обычного BST»: балансировка почти бесплатна, потому что её кирпич - вращение - стоит константу и сохраняет порядок даром. Разберёшься с одним поворотом - и все балансировки дальше станут вариациями на эту тему.

Теперь сам

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