红黑树插入案例

Question

这可能是一个非常简单的问题，但我找不到满意的答案。一个节点插入red-black树后，会遇到三种不同的情况：

新增节点=z

案例 1 : z = red, parent of z = red, uncle of z = red

案例 2：z = 红色，parent of z = red，z = right child，uncle of z = black

案例 3：z = 红色，parent of z = red，z = left child，uncle of z = black

但是，我认为我们不能直接进入案例2或案例3，因为假设x和y是兄弟姐妹，分别是红色和黑色。当我们在节点 x 下插入 z 时，可以观察到情况 2 或情况 3，而无需进入情况 1。但是，这意味着在添加节点 z 之前，red-black 树是不平衡的，因为 black-height规则已经被打破。

            Grandparent
             /       \
        x(red)       y(black)
        /   \         /   \
    nil(b) nil(b)  nil(b)  nil(b)

节点z可以添加到节点x的nil指针之一，但是树不可能是这样的。每次插入后，red-black树必须平衡。

但是，我的算法教授否定了这个理论；因此，我无法确保这种情况。没有case 1的情况下是否可以涉及case 2或case 3？

Answer 1

记住空值是黑色的。

事情是这样的：

           Grandparent
            /       \
        x(red)      nil(b)
        /   \     
    nil(b) nil(b) <-- z goes here

Red Black Tree Insertion Cases