“In a binary search tree, deleting a node is a challenge. Unlike insert where we do a plain check for in-order property to insert elements. That is, we add from left to right. But even after deleting, we need to get the in-order property to be satisfied”
In Binary search tree, deletion is a tricky algorithm and must be understood well to understand self-balancing trees. Binary search trees has a small problem when it comes to insertion and deletions. We won’t get a balanced tree ever!!
Heap is balanced by default since we construct it from across with the single property that root is greater than the leaves. But BST property makes it grow either in left or the right side if the insertion of a sorted array is done.
Consider the insertion code we already have. Try giving,
The above array will yield a tree which grows towards the right!!.. So, when we search such a binary tree, we get a worst case time if the tree is too huge!!..
This is where self-balancing trees came into picture.
But what does deletion needs to do in a BST, it needs to follow the in-order sorted property. It also never balances a BST if it is right inclined. But there are proofs that random insertion and deletion gives somewhat balanced BST.
Deletion involves three cases. Consider you have given a node for deletion. For any node in a BST, there are 3 cases. Node can have 0, 1 or 2 children.
Case 1: node has no children = remove
Case 2: node has 1 children = move right or left, ignore node
Case 3: node has 2 children = find the successor and swap content
This is explained clearly in many books. So, please refer Cormen to get clear picture.
- please study more about finding the successor.
- deletion algorithm does all the 3 cases in a mixed way
- we free(y) blindly!!.. but doesn’t break the tree structure.