AVL Insertion
This lesson will cover the insertion operation in AVL trees, discussing all the 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, we need to perform a ‘rotation’, but before going deep, let’s look at AVL tree rebalancing case-by-case.
Let’s look at the terms that we 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, we will perform rotations on the subtree with Node U being 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
Case 1: Left-Left #
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.