AVL Insertion

Learn about the insertion operation in AVL trees and all four insertion cases.

We'll cover the following

Introduction

Insertion in AVL trees is done the same way that BST insertion is done. However, when a node is inserted into a BST, it usually becomes unbalanced, i.e., the tree has a node that has a left-right subtree height difference greater than 1. So, AVL trees have to be rebalanced after insertion unlike BSTs. To rebalance the tree, you need to perform a ‘rotation’. But before going deep, let’s look at AVL tree rebalancing case-by-case.

Look at the terms that you will be using while rebalancing 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, you will perform rotations on the subtree with node U being the root node. There are two types of rotations (left and right). You 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 80+ hands-on prep courses.