121 2/1/2017 8:06:45 AM


:

Deleting vertices that have only one child is straightforward.

The only difficulty arises when you are deleting a vertex with two children. If v is such a vertex, replace v by the leftmost (minimum) element u of the right subtree of v and replace u with the right subtree of u (it doesn't have a left subtree).