Deletion from BSTs
Insertion into a binary search tree is easy.
Deletion from a binary search tree is harder.
Four cases to consider ...
- empty tree ... new tree is also empty
- zero subtrees ... unlink node from parent
- one subtree ... replace by child
- two subtrees ... replace by successor
|