red-black-tree - 红黑树插入问题为什么要旋转？

Question

所以我有一个红黑树如下:

2 = Root Black
Children = 1 (Black/Left), 4 (Red/Right)
Children of 1 = NIL & NIL => Height of Black Subtree is then 2 
Children of 4 = 3 (Black/Left), 5 (Black/Right)
Children of 3 = NIL & NIL, Height of Black Subtree is then 2 
Children of 5 = 7 (Red/Right)& NIL, Height is still then of course 2. 

因此，当我插入 6(当然颜色是红色)时，它将成为 7 的左子节点。在我关注的这个 Web 应用程序中，它在 6 和 7 上进行旋转。为什么？从我所见，它似乎没有违反 RBT 的任何属性。

注意:Source web app 是需要 1.7 的 Java web app来源:http://gauss.ececs.uc.edu/RedBlackTester/redblack.html

Answer 1

RBT 的属性是。

1. 每个节点要么是红色要么是黑色。
2. 根和叶 (NIL) 是黑色的。
3. 如果一个节点是红色的，那么它的父节点是黑色的。
4. 从任何节点 x 到 a 的所有简单路径后代叶子有相同的编号黑色节点数 = 黑色高度 (x)。

因此，如果 7 是红色的，并且当添加 6 时它也是红色的，这违反了第三个属性，因此旋转和更改以消除违规。