AVL Deletion
This lesson will cover the deletion operation in AVL trees, discussing all the four deletion cases.
Deletion in AVL Tree
Deletion is similar to AVL’s insertion operation with just one exception:
The deletion operation adds an extra step after the insertion method’s rotation and balancing of the first unbalanced node.
After fixing the first unbalanced node through rotations, start moving up and fix the next unbalanced node. Keep on fixing the unbalanced nodes until you reach the root.
Steps for Deletion
The following are the detailed steps for removing value from AVL Trees.
Step 1: Delete currentNode
Delete the currentNode in the same way as we did in BST deletion. At this point, the tree will become unbalanced, and we would need to perform some kind of rotation (left or right) to rebalance the tree.
Step 2: Traverse Upwards
Start traversing from currentNode upwards till you find the first unbalanced node.
Let’s look at some of the terms we will be using while re-balancing the tree.
- Node U — an unbalanced node
- Node C — child node of node U
- Node G — grandchild node of node U