为什么只有当插入的节点的叔叔是黑色时才旋转红黑树？有人可以解释其属性背后的逻辑吗？

Question

因此，最近我一直在分析Red black tree及其属性，并试图解释为什么它们如此。我理解这些约束条件用于保持树的平衡和有效，同时保持其高度，但是我仍然可以找不到一种方法来清楚地了解为什么仅当新插入的节点的叔叔是黑色时才旋转树吗？为什么只在叔叔是红色的时候才重新着色呢？我试图了解所有这些属性背后的逻辑，有人可以解释一下吗？非常感谢您的帮助！

Answer 1

[当叔叔是黑色的时候，在插入过程中至少需要旋转一次，因为在这种情况下会有违反红色的行为（连续两个红色节点），但是如果树不平衡，则无法重新着色。）

最简单的情况

1b
 \
  2r
   \
    3r

1和2每个都有一个叶子节点（未显示），而3有两个叶子节点（也未显示）。暂时忽略节点颜色，很容易看到需要旋转才能使该树平衡，该旋转伴随的重新着色用于修复红黑色属性。当第二个红色节点未对齐时（左子节点的右子节点或右子节点的左子节点），需要第二次旋转，因为这样的节点在逻辑上位于其父节点和祖父母节点之间。

与树：

   2b
  /  \
1r    3r
        \
         4r

红色节点属性被推到树上，因为这里没有旋转量可以固定树，树结构中的任何不平衡都必须高于此处显示的水平。