AVL Tree

AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

This tree beside is a normal BST (Skewed BST) where all the nodes are on the right side because 2>5>7>9>11. Suppose now we want to search for node 11. This search will take O(n) time to do the searching. This is very time consuming and has no difference with Linked Lists. But if we use the concepts of AVL tree it's gonna cost us O(log n) time. Let's look at an example:

We are gonna insert 2, 5, 7, 9, and 11 as the nodes.

First, when we insert 2 the tree us going to look like this:

Next, the tree will look like this when we insert 5:

Now, when we insert 7 this is how the tree will look:

Here the tree becomes unbalanced, when a node is inserted into the right subtree of the right subtree, then we perform a single left rotation. We make 2 the left subtree of 5. Same goes with right rotation.

Double Rotation

Suppose we have a tree which looks like this :

First, we perform the right rotation along 5 node, making 5 the right subtree of its own left subtree 3. Now, 3 becomes the right subtree of 2. Node 2 is still unbalanced because of the right subtree of its right subtree and requires a left rotation. Left rotation is performed by making 3 the new root node of the subtree. 2 becomes the left subtree of its right subtree 3. It looks like this: