Consider Tree-Delete (page 298, and also copied below). TREE-DELETE (T, z) 1 if z.left == NIL...

Transcribed Image Text:

Consider Tree-Delete (page 298, and also copied below). TREE-DELETE (T, z) 1 if z.left == NIL 2 3 4 5 6 7 8 9 10 11 12 13 TRANSPLANT (T, z, z.right) else if z.right == NIL TRANSPLANT (T, z, z.left) else y = TREE-MINIMUM (z.right) // successor if y.p != z TRANSPLANT (T, y, y.right) y.right z.right y.right.p = y TRANSPLANT (T, z, y) y.left - 2.left y.left.p = y = (a) How does this code rely on the Lemma you proved in problem #4? Answer It takes advantage of using the successor to transplant nodes and subtrees upon deletion with the validity of the Lemma. | (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 to and underline or boldface the changed portions. Consider Tree-Delete (page 298, and also copied below). TREE-DELETE (T, z) 1 if z.left == NIL 2 3 4 5 6 7 8 9 10 11 12 13 TRANSPLANT (T, z, z.right) else if z.right == NIL TRANSPLANT (T, z, z.left) else y = TREE-MINIMUM (z.right) // successor if y.p != z TRANSPLANT (T, y, y.right) y.right z.right y.right.p = y TRANSPLANT (T, z, y) y.left - 2.left y.left.p = y = (a) How does this code rely on the Lemma you proved in problem #4? Answer It takes advantage of using the successor to transplant nodes and subtrees upon deletion with the validity of the Lemma. | (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 to and underline or boldface the changed portions.

Answer rating: 100% (QA)

It seems there might be a formatting issue with the code provided for TREEDELETE making it a bit dif... View the full answer