AVL Deletion

This lesson will cover the deletion operation in AVL trees, discussing all four deletion cases.

We'll cover the following

Deletion in AVL Trees

Deletion is almost the same as the insertion operation in AVLs with just one exception. The deletion operation adds an extra step after the rotation and balancing of the first unbalanced node in the insertion method. After fixing the first unbalanced node through rotations, you would 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 node in the same way as in BST deletion. At this point, the tree will become unbalanced. To rebalance the tree, we would need to perform some kind of rotation either​ left or right. At first, we need to define the structure of the 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 until you find the first unbalanced node. Let’s look at some of the terms which 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

3. Rebalance the Tree

In order to rebalance the tree, we will perform rotations on the subtree where U is the root node. There are two types of rotations, left and 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 left-child of Node C

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

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

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

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

Case 1: Left-Left

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.