Что такое операция поворота дерева и как она работает

Что проверяют

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

Как отвечать

Поворот это локальная перестройка трёх ссылок, которая меняет высоту поддерева, но сохраняет порядок обхода in-order. Стоимость константная, число узлов не меняется.

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

Node rightRotate(Node y) {
    Node x = y.left;
    y.left = x.right;
    x.right = y;
    updateHeight(y);
    updateHeight(x);
    return x;
}

Порядок пересчёта обязателен: сначала узел, который опустился, потом поднявшийся, иначе высоты разъезжаются и балансировка принимает решения по устаревшим данным.

Дальше про применение. В AVL четыре случая: перекос по одной прямой лечится одним поворотом, изломанный одним двойным, то есть парой поворотов в разные стороны. В красно-чёрном дереве повороты идут в связке с перекрашиванием при вставке и удалении. В Java это не абстракция: TreeMap и TreeSet построены на красно-чёрном дереве, и тяжёлая корзина HashMap тоже превращается в дерево.

Где спотыкаются

Пишут поворот, но забывают пересчитать высоты или делают это в обратном порядке. Дерево остаётся валидным по значениям, и поэтому дефект всплывает позже, деградацией поиска до линейного на длинных вставках.

Не присваивают результат ссылке родителя. Функция честно возвращает новый корень поддерева, вызывающий код его игнорирует, и половина дерева отваливается без единого исключения.

Не могут объяснить, почему порядок элементов не нарушается. Ответ короткий: перевешивается только среднее поддерево, и его ключи по значению лежат между двумя участвующими узлами, поэтому обход остаётся отсортированным.