AVL Insertion

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

We'll cover the following

Insertion in AVL Tree

Insertion for an AVL tree follows the same steps that we covered in BST insertion.

The main step comes after insertion when the tree gets unbalanced.

To re-balance the tree, we need to perform some kind of rotation (left or right). But before getting into the deeper concepts that’ll be a mess for you to understand at this point, let’s slowly cover one case at a time.

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

Insertion Cases

To rebalance the tree, we will perform rotations on the subtree with Node U as being 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.

Case 1: Left-Left

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