When node $z$ in
TREE-DELETEhas two children, we could choose node $y$ as its predecessor rather than its successor. What other changes to
TREE-DELETEwould 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-DELETEbe 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
TREE-MAXIMUM and swap
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.