红黑树伪code冗余 [英] Red black tree pseudocode redundancy

问题描述

在算法导论第三版他们有红黑树删除伪code实现。这是...

In introduction to Algorithms Third Edition they have a pseudocode implementation of red-black tree deletion. Here it is...

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)

树最小只是发现在一棵树的最小值，RB移植需要的第二个参数的父母已经将其指向第三个参数，并有第三个参数的父母是第二个参数的父。

TREE-MINIMUM just finds the smallest value in a tree, RB-TRANSPLANT takes the parent of the second parameter and has it point to the third parameter, and has the third parameter's parent be the second parameter's parent.

通过我的评论，他们测试是否YP为z，如果是一套XP为y。但X是已经y.right，所以这好像是说y.right.p = Y，但y.right.p已经是Y！他们为什么这样做？

By my comment, they test if y.p is z and if so set x.p to y. But x is already y.right, so this is like saying y.right.p = y, but y.right.p is already y! Why are they doing this?

下面是他们的解释......

Here is their explanation...

y的原来的母公司为z，但是，我们不希望XP指向为y原有的母公司，因为我们卸下从树节点。由于节点Y将向上移动采取树Z的位置，设置XP为y在第13行的原因XP指向为y的父的原始位置，甚至如果x == T.nil。

"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 ...

So they want to keep x's parent to be y...it already is y...

推荐答案

他们指出在X可以是还无，即当y.right是无文字。这似乎是无本code也重新由节点psented $ P $，他们不想留下悬摆指针。

They state in the text that x can be also Nil, i.e. when y.right is Nil. It seems Nil is in this code also represented by a node, and they don't want to leave a dangling pointer.

这篇关于红黑树伪code冗余的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！