BST Delete
In addition to inserting and finding things, sometimes we want to remove things from a BST!
Here's a BST:
No Children
Say we want to remove the key 29.
Well, that's quite straightforward. We just… remove it!
One Child
What if we now want to remove the key 10?
That's a little bit trickier because it has a child node, 3. The question is, what are we going to do with 3…? We don't want to detach it from the tree because we're only trying to remove 10. So we'll need to reattach it somewhere else.
We just move the child up to the deleted node's place!
We know it is safe to do this, because we know that 10 is a left child. Therefore every key in 10's subtree is less than its parent's key (19). So 10's child (on either side) is allowed to be the left child of 19.
Two Children
Now say we want to delete the key 51.
That's much more interesting!
Key Points:
- When removing a node with two children we need a new node to take its place.
- Specifically, we need to find a new parent node that can correctly be a parent to both children of the removed key, so it needs to be
- Bigger than the left child, and
- Smaller than the right child.
- A great choice is to pick a node that is closest in sorted order to the removed node, such as the one before it, namely the greatest node less than the removed node.
- That node is the rightmost descendent of the left child.
- (The smallest key that is bigger would also work, in which case it is the leftmost descendant of the right child).
- So we remove the replacement parent node (which has at most one child, so we can use one of the above techniques to remove it) and put it in place of the removed node.
Here is the resulting tree:
Now you try it! Say we want to remove the key 47…
(When logged in, completion status appears here.)