Deleting Arbitrary Nodes in a Binary Search Tree
For all of its meritsm the binary search tree data structure has one glaring fault: deleting an arbitrary node is somewhat complicated process. Insertion, searching, even rotations are all accomplished in a straight forward and rather intuitive manner. Unfortunately, removing a node must handle so many corner cases that it results in an algorithm that is anything but intuitive, as anyone who has read my previous article on the subject can see for themselves.
Join based algorithms, while being somewhat simpler to implement don’t fair much better. The book “Mastering Algorithms with C” found the process so cumbersome they opted to go the lazy deletion route, or whats sometimes referred to as “tombstone deletion” – you leave the node where it is in the tree, but “marked” as deleted so its simply skipped over. This is FAR from an ideal situation, and requires periodic rebuilding of the entire tree to remove the tombstoned nodes.
There is a somewhat simple way to delete arbitrary nodes from a BST however: Hibbard deletion. It works by swapping a node with its successor and then removing the successor node. While straightforward it is not without its own drawbacks: excessive deletions causes imbalance in the tree. What follows is a simple recursive method for removing arbitrary values from a binary search tree.
Hibbard Deletion
To implement Hibbard deletion, we first have to implement a function that deletes the minimum value in a tree. This is how we ultimately remove an arbitrary element, as we can remove any given node by swapping with it with the minimum value in the given subtree and then setting the link to null effectively removing it from the tree. As the node being removed will always be a leaf, we avoid the multitude of edge cases.
Deleting the minimum value works by recursively traversing the left link of the tree until we reach a node whose left link points to null. If that link has no children, we simply set that node to null, if it has a right child, we swap them:
I’ve also included the code to retrieve the node with the minimum key as well, as the code to delete it. We will utilize both of those functions for the deletion or arbitrary values:
And thats it!
Conclusion
In wrapping up i do wish to point out again that this algorithm is not without its flaws, excessive deletions can cause severe imbalance in the tree, which as we know cause a degredation in performance. One situation where this might not make as much of a difference would be in an AVL tree, where future insertions should rebalance the tree, though keep in mind that balance factors would need to be adjusted during the deletion. I have not investigated this though, so don’t take my word for it, i’m just musing.
Happy Hacking
-Max
The full implementation used in this article is available on my github at:
https://github.com/maxgoren/DataStructures/blob/main/BinarySearchTree.java
