Почему красное черное дерево вращается только тогда, когда дядя вставленного узла черный? Может кто-нибудь объяснить логи c за его свойствами?

Question

Итак, в последнее время я анализировал Красное черное дерево и его свойства и пытался выяснить, почему они такие, я понимаю, что эти ограничения используются для поддержания сбалансированности и эффективности дерева при сохранении его высоты, но все же я Не можете найти способ ясно понять, почему мы вращаем дерево только тогда, когда дядя недавно вставленного узла черный? и почему мы перекрашиваем его только тогда, когда он дядя красного цвета? Я пытаюсь понять логику c за всеми этими свойствами, кто-нибудь может объяснить, пожалуйста, их? Любая помощь очень ценится!

Answer 1

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

В простейшем случае

1b
 \
  2r
   \
    3r

1 и 2 имеют один листовой узел (не показан), а 3 имеет два листовых узла (также не показан). На мгновение не обращая внимания на цвета узлов, легко увидеть, что вращение необходимо для того, чтобы это дерево сбалансировалось, перекрашивания, которые go вместе с этим вращением, используются для восстановления красно-черных свойств. Когда второй красный узел не выровнен (правый дочерний элемент левого дочернего элемента или левый дочерний элемент правого дочернего элемента), необходим второй поворот, поскольку такой узел логически находится «между» своим родителем и прародителем.

С tree:

   2b
  /  \
1r    3r
        \
         4r

Свойство red node перемещается вверх по дереву, потому что здесь никакое вращение не исправит дерево, любой дисбаланс в структуре дерева должен быть на уровне выше, чем показано здесь.