红黑树插入问题：为什么需要旋转？

Question

红黑树插入问题：为什么需要旋转？

3

我有一棵如下的红黑树：

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的任何属性。

注：源Web应用程序是一个需要1.7版本的Java Web应用程序。来源：http://gauss.ececs.uc.edu/RedBlackTester/redblack.html

- pmac89

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- pulasthi · Accepted Answer

每个节点要么是红色的，要么是黑色的。
根节点和叶子节点(NIL节点)都是黑色的。
如果一个节点是红色的，则其父节点是黑色的。
从任何节点x到一个后代叶节点的所有简单路径都具有相同数量的黑色节点=黑高度(x)。

因此，如果7是红色的，当6被添加时也是红色的，那么就违反了第3条属性，因此需要旋转并进行更改以消除违规行为。