所以我有一棵红黑树如下:
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 的左孩子。在我关注的这个网络应用程序中,它会在 6 和 7 上旋转。为什么?从我所见,它似乎没有违反 RBT 的任何属性。
注:Source web app是Java web app,需要1.7 来源: http: //gauss.ececs.uc.edu/RedBlackTester/redblack.html