AVL Deletion

Deletion in AVL Trees

Deletion is almost similar to the insertion operation in AVLs with just one exception. The deletion operation adds an extra step after rotation and balancing the first unbalanced Node in the insertion method. After fixing the first unbalanced Node through rotations, start moving up and fix the next unbalanced Node. Keep fixing the unbalanced nodes until you reach the root.

Algorithm for Deletion

Here is a high-level description of the algorithm for deletion.

1. Delete the given Node

Delete the given in the same way as in BST deletion. At this point, the tree will become unbalanced and, to rebalance the tree, we would need to perform some kind of rotation (left or right). At first, we need to define the structure of AVL Tree and some nodes relative to the currentNode, which is inserted using step one.

2. Traverse Upwards

Start traversing from the given Node upwards till you find the first unbalanced Node. Let’s look at some of ...