В интересах всех, кто читает эту ветку и не имеет доступа к книге, упомянутой в принятом ответе, я надеюсь, что это будет приемлемый описательный ответ.
Поворот переводит дерево в состояние, в котором оно соответствует критериям перекраски (у дочернего узла есть красный дядя). Есть два ключевых различия:
- какой узел является "дочерним" и какой узел является "дядей", изменилось;
- вместо того, чтобы перекрасить родителя и дядю в черный цвет, а прародителя - в красный, вы перекрасите родителя в красный, а прародителя - в черный.
Когда у дочернего узла нет красного дяди, вы должны повернуть, потому что, если узел дяди уже черный, то создание родительского черного увеличит высоту черного на 1 только с одной стороны бабушки и дедушки. Это нарушит свойство инвариантности высоты красно-черных деревьев и сделает дерево неуравновешенным.
Теперь давайте посмотрим, как вращение преобразует дерево, так что у нас есть дочерний узел с красным дядей и мы можем использовать перекрашивание. Я рекомендую нарисовать это, чтобы полностью понять это.
- Пусть x будет текущим красным узлом с красным родителем.
- Пусть p будет красным родителем x перед вращением (если бы родитель был черным, мы бы уже сделали).
- Пусть y будет черным дядей x перед вращением (если бы дядя был красным, нам бы не понадобилось вращение. Мы просто перекрасили бы родителя и дядю в черный цвет, а прародителя в красный).
- Пусть g будет черным прародителем x перед вращением (так как родитель красный, прародитель должен быть черным; иначе это не было красно-черное дерево с самого начала.)
- Если у вас есть левый-левый (LL) или правый-правый (RR) регистр (то есть x - левый потомок p, а p - левый потомок g ИЛИ x - правый потомок p и p является правым потомком g), после одного поворота (вправо, если LL, оставлено, если RR), y становится дочерним, а x - его дядей. Поскольку х - красный дядя, у вас теперь есть случай, когда вы можете перекрасить. Таким образом, перекрасьте родительский элемент дочернего элемента (так как дочерний элемент теперь равен y, его родительский элемент равен g) в красный, а прародитель дочернего элемента (теперь p) - в черный.
- Если у вас есть LR (x - левый дочерний элемент или p, а p - правый дочерний элемент g) или регистр RL (x - правый дочерний элемент p, а p - левый дочерний элемент g), после двойного поворота (затем направо, налево, если LR, затем направо, если RL), y становится ребенком, а p - дядей. Поскольку р красный дядя, у вас снова есть случай, когда вы можете перекрасить. Итак, перекрасьте родителя (так как дочерний элемент теперь у, его родительский g) в красный, а дедушка (в настоящее время х) в черный.
Перед вращением и перекрашиванием у вас был черный дедушка с 2 красными узлами и 0 черными узлами на стороне A (слева или справа) и 0 красными узлами и 1 черным узлом на стороне B (противоположной стороне A). После поворота и перекраски у вас есть черный дедушка с 1 красным узлом и 0 черными узлами на стороне A и 1 красным узлом и 1 черным узлом на стороне B. Таким образом, вы по существу переместили один из красных узлов на другое поддерево дедушка, не увеличивая черную высоту любого поддерева.
Это магия вращения. Это позволяет вам перемещать лишний красный узел в другую ветвь, не изменяя высоту черного, и при этом сохраняя отсортированное свойство обхода бинарного дерева поиска.