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?
Removing 10 is a 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 so 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 (from 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 be a parent to both the child nodes, so the new parent node has to be both
- Bigger than the left child, and
- Smaller than the right child.
- We want to pick a node that is closest in the sorted order to the removed node, such as the node located just before it in order—that is, the largest key that is less than the removed node.
- That node is the rightmost descendant of the left child.
- (The smallest key that is larger than the removed node would also work, in which case we'd choose the leftmost descendant of the right child).
- We then remove our replacement parent node (which has at most one child, so we can use one of the techniques we discussed above to remove it) and reattach it where the original node we were removing had been.
Here is the resulting tree:
Now you try it! Say we want to remove the key 47…
(When logged in, completion status appears here.)