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 ...