红黑树插入案件

Question

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

新添加的节点= z

情况1：z =红色，z =红色的父亲，z =红色的叔叔

情况2：z =红色，z =红色的父母，z =右儿童，z =黑色的叔叔

情况3：z =红色，z =红色的父，z =左子，z =黑的叔叔

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

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

节点z可以添加到节点x的一个nil指针中，但树不可能像这样。每次插入后，必须平衡红黑树。

但是，我的算法教授拒绝了这个理论;因此，我无法确保这种情况。如果没有案例1，是否可以参与案例2或案例3？

Answer 1

请记住，空值是黑色的。

它发生如下：

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