algorithm - 红黑树伪代码冗余

Question

在算法第三版简介中，他们有一个红黑树删除的伪代码实现。这是...

RB-DELETE(T, z)
    y = z
    y-original-color = y.color
    if z.left == T.nil
        x = z.right
        RB-TRANSPLANT(T, z, z.right)
    elseif z.right == T.nil
        x = z.left
        RB-TRANSPLANT(T, z, z.left)
    else
        y = TREE-MINIMUM(z.right)
        y-original-color = y.color
        x = y.right
        if y.p == z
                x.p = y       // <--------- why????
        else
                RB-TRANSPLANT(T, y, y.right)
                y.right = z.right
                y.right.p = y
        RB-TRANSPLANT(T, z, y)
        y.left = z.left
        y.left.p = y
        y.color = z.color
    if y-original-color == BLACK
        RB-DELETE-FIXUP(T, x)

TREE-MINIMUM 只是找到树中的最小值，RB-TRANSPLANT 将第二个参数的父节点指向第三个参数，并且第三个参数的父节点是第二个参数的父节点。

根据我的评论，他们测试 y.p 是否为 z，如果是，则将 x.p 设置为 y。但是 x 已经是 y.right，所以这就像说 y.right.p = y，但是 y.right.p 已经是 y!他们为什么要这样做？

这是他们的解释......

“When y's original parent is z, however, we do not want x.p to point to y's original parent, since we are removing that node from the tree. Because node y will move up to take z's position in the tree, setting x.p to y in line 13 causes x.p to point to the original position of y's parent, even if x == T.nil.”

所以他们想让 x 的父级保持为 y...它已经是 y...

Answer 1

他们在文本中声明 x 也可以为 Nil，即当 y.right 为 Nil 时。似乎 Nil 在此代码中也由一个节点表示，他们不想留下悬空指针。