Exercise 12.3.6

When node $z$ in TREE-DELETE has two children, we could choose node $y$ as its predecessor rather than its successor. What other changes to TREE-DELETE would be necessary if we did so? Some have argued that a fair strategy, giving equal priority to predecessor and successor, yields better empirical performance. How might TREE-DELETE be changed to implement such a fair strategy?

We need to write a symmetrical function:

TREE-DELETE(T, z)
    if z.left = NIL
        TRANSPLANT(T, z, z.right)
    else if z.right == NIL
        TRANSPLANT(T, z, z.left)
    else
        y = TREE-MAXIMUM(z.left)

        if y.p != z
            TRANSPLANT(T, y, y.left)
            y.left = z.left
            y.left.p = y

        TRANSPLANT(T, z, y)
        y.right = z.right
        y.right.p = y

Basically, call TREE-MAXIMUM and swap left and right.

Beware of the code above; I've not even proven it correct, let alone tested it.

As for implementing a fair strategy – we can have both versions of the function and then randomly decide which node to choose.