红黑树伪代码冗余性

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！他们为什么要这样做？这是他们的解释：“当y的原始父节点是z时，我们不希望x.p指向y的原始父节点，因为我们正在从树中删除该节点。因为节点y将上移以占据树中z的位置，在第13行将x.p设置为y会导致x.p指向y的父节点的原始位置，即使x == T.nil。”所以他们想保持x的父级为y...它已经是y了...

- confused

---

对于“RB-TRANSPLANT将第二个参数的父节点指向第三个参数”，不，它将第三个参数的父节点指向第二个参数。 - VimNing

Answer 1

文本中提到x也可以为Nil，即当y.right为Nil时。在此代码中，Nil似乎也被表示为一个节点，他们不想留下游离指针。

- Antti Huima

---

啊，我懂了！灯泡亮了。他们说要利用 T.nil 节点具有左、右和父属性的事实，这就是他们的意思。谢谢！ - confused

为了向其他人澄清，T.nil 是代表树中所有叶节点的节点。没有它，您将拥有 O(2^h) 个 nil 叶节点，这是一种浪费空间的做法。 T.nil 的属性 left、right 和 parent 是任意的。因此，当 x = y.right 时，如果 x = T.nil，则 x 的父节点将不是 y。如果最后一次调用 RB-DELETE-FIXUP(T, x) 要正常工作，需要将其设置为 y。 - confused