Binary Search Tree Proof

The procedure for deleting a node in a binary search tree relies on a fact that was given without proof:

Lemma: If a node X in a binary search tree has two children, then its successor S has no left child and its predecessor P has no right child.

In this exercise you will prove this lemma. Although the proof can be generalized to duplicate keys, for simplicity assume no duplicate keys. The proofs are symmetric. (Hints: Rule out where the successor cannot be to narrow down to where it must be. Drawing pictures will help!)

(a) Prove by contradiction that the successor S cannot be an ancestor or cousin of X, so S must be in a subtree rooted at X.

(b) Identify and prove the subtree of X that successor S must be in.

(c) Show by contradiction that successor S cannot have a left child.

(d) Change the above steps so that it will prove the Lemma for the predecessor.

Deletion in Binary Search Trees

Consider Tree-Delete

(a) How does this code rely on the Lemma you proved in problem #4?

(b) When node z has two children, we arbitrarily decided to replace it with its successor. We could just as well replace it with its predecessor. (Some have argued that if we choose randomly between the two options we will get more balanced trees.) Rewrite TREE-DELETE to use the predecessor rather than the successor. Modify the above code just as you need toand underline or boldface the changed portions.

TREE-DELETE (T, z) 1 if z.leftNIL 2. TRANSPLANT (T, z, z.right) TRANSPLANT (T, z, z.left) y TREE-MINIMUM (z.right) // successor 3 else if z.right NIL 4 5 else 6 7 if y.p !- z TRANSPLANT (T, y, y.right) y.right -z.right y. right . p = y 10 12 13 TRANSPLANT (T, z, y) y.left - z.left y.left.p = y TREE-DELETE (T, z) 1 if z.leftNIL 2. TRANSPLANT (T, z, z.right) TRANSPLANT (T, z, z.left) y TREE-MINIMUM (z.right) // successor 3 else if z.right NIL 4 5 else 6 7 if y.p !- z TRANSPLANT (T, y, y.right) y.right -z.right y. right . p = y 10 12 13 TRANSPLANT (T, z, y) y.left - z.left y.left.p = y