procedure Transplant(T,u,v) if u.p == NIL T.root = v else if u == u.p.left u.p.left = v else u.p.right = v if v != NIL v.p = u.p 

procedure TreeDelete(T,z) if z.left == NIL Transplant(T,z,z.right) else if z.right == NIL Transplant(T,z,z.left) else y = TreeMinimum(z.right) if y.p != z Transplant(T,y,y.right) y.right = z.right y.right.p = y Transplant(T,z,y) y.left = z.left y.left.p = y 

Problem 78. Let T be the following tree. Starting with this tree, show the result of TreeDelete(T,z1) followed by TreeDelete(T,z2). Similarly, show the result of TreeDelete(T,z2) followed by TreeDelete(T,z1). Do the results differ?

 z1 / \ z2 a / \ b c \ / \ d e f