BST Operation: Remove (How it works)
The remove operation in a BST implementation of OrderedSet ADT is a somewhat involved process! We will break it down to three scenarios.
-
Node to be removed is leaf: Simply remove from the tree.
50 50 / \ remove(20) / \ 30 70 ---------> 30 70 / \ / \ \ / \ 20 40 60 80 40 60 80 -
Node to be removed has only one child: Copy the child to the node and delete the child
50 50 / \ remove(30) / \ 30 70 ---------> 40 70 \ / \ / \ 40 60 80 60 80 -
Node to be removed has two children:
- Find smallest key in the right subtree (in-order successor) of the node.
- Copy key of the in-order successor to the node and delete the in-order successor.
50 60 / \ remove(50) / \ 40 70 ---------> 40 70 / \ \ 60 80 80- Note that the largest key in the left subtree (in-order predecessor) can also be used.
Exercise Remove $17$ from the following BST.
Solution
Either replace $17$ with the smallest value in its right subtree:
Or replace $17$ with the largest value in its left subtree:
