AVL Deletion

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

Step 3: Rebalance the Tree

To rebalance the tree, we will perform rotations on the subtree where U is the root node.

There are two types of rotations:

• left
• right

We came across four different scenarios based on the arrangements of Nodes U, C and, G.

• Left-Left: Node C is the left-child of Node U, and Node G is the left-child of Node C.

• Left-Right: Node C is the left-child of Node U, and Node G is the right-child of Node C.

• Right-Right: Node C is the right-child of Node U, and Node G is the right-child of Node C.

• Right-Left: Node C is the right-child of Node U, and Node G is the left-child of Node C.

After performing a successful rotation for the first unbalanced Node U, traverse up and find the next unbalanced node and perform the same series of operations to balance. Keep on balancing the unbalanced nodes from first Node U to ancestors of Node U until we reach the root. After that point, we will have a fully balanced AVL Tree.

Case 1: Left-Left