Modify the algorithm TREE-DELETE so that when the node z to be deleted has two c

Question

Modify the algorithm TREE-DELETE so that when the node z to be deleted has two children, the algorithm will choose node y as the predecessor instead of the successor of z. Make minimal but necessary changes to ensure the correctness of the algorithm.

TTREE DDELETE CTT, z) 1 if left [z NIL or right [zj NIL then y z else y FREE SUCCESSOR Cz 4 if left [y] NIL then x left else x right [y] if x. NIL. then p 1 I Dy if p [y] 1 O then root [T] 1 1 else if y left JJ then left IPL. 1 2 13 else right [p[y JJ 14 if y z then key Dz] keep Eyl 1 S 16 copy y's satellite data into z 17 return

Explanation / Answer

TREE-DELETE(T, z)
   if left[z] = NIL or right[z] = NIL
       then y <- z
       else y <- TREE-PREDECESOR(z)
   if left[y] NIL
       then x <- left[y]
       else x <- right[y]
   if x NIL
       then p[x] <- p[y]
   if p[y] == NIL
       then root[T] <- x
       else if y == left[p[y]]
               then left[p[y]] <- x
               else right[p[y]] <- x
   if y z
       then key[z] <- key[y]
           copy y's satellite data into z
   return y

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.