Red black tree pseudocode redundancy

Question

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)

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.

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

“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.”

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

For "RB-TRANSPLANT takes the parent of the second parameter and has it point to the third parameter", no, it takes the parent of the third parameter to point to the second's. — Rainning

Antti Huima Antti Huima · Accepted Answer · 2011-04-21T15:17:31

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.

Red black tree pseudocode redundancy

1 Answers