# AVL (Balanced Binary Search Tree)

In our previous post(Binary Search Tree), we have discussed binary search trees. We have checked out the insertion, deletion, and find operation for a BST.

In the best-case scenario, BST can provide O(log n) complexity but in the worst-case scenario, this gives us O(n) complexity. The worst-case can happen if the input data is sorted in any order. To prevent the worst case, there are extensions that can help us maintain the binary tree balanced and get the best outcome. Some of them are,

• AVL tree
• Red black tree
• Treap
• B-tree

Today, we will discuss the height-balanced AVL tree.

## AVL tree

AVL tree is an extension of the binary search tree. It has an additional field called the balance factor. After insert, delete, or modification operation, it always checks the balance factor of each node.

Based on the value of the balance factor, the tree self-balances itself.

## Balance factor

The balance factor of a node in an AVL tree is the difference between the height of the left subtree and the height of the right subtree of that node.
Balance factor = Height of Left Subtree — Height of Right Subtree (or inverse)
The value of the balance factor should always be [-1, 0 or+1]

We will use a callback pattern for our AVL tree insert and delete methods.

We have already discussed BST implementation in our previous post. We will extend the insert and delete operation here to maintain AVL properties.

## Insert

After the binary search tree insertion, we need to update the balance factor of each node. As we know we insert in any of the subtrees we are going to check all the way up to the parent to check if every node maintains the AVL properties.
If the node is unbalanced, we need to rotate the tree to maintain the balance factor ≤ 1 and ≥ -1

## Unbalanced Node

The subtree can be unbalanced in 4 different ways,

1. Left unbalanced (LL)
2. Right unbalanced (RR)
3. Left Right unbalanced (LR)
4. Right unbalanced (RL)

For these use cases, we have to rotate our tree to maintain our balance properties.

First, we have to find the unbalanced direction

Next, we have to apply rotation based on the direction

## Left rotation

To apply the rotation in left rotation,

## Right rotation

To apply the rotation in the right rotation

## Deletion

In terms of deletion, we need to check certain steps to determine if the balance factor is appropriate.

1. The parent of the deleted node has any child node unbalanced.
2. The unbalanced key that will determine the rotation direction

First, we need to check if any unbalanced node exists or not

Then we have to check the key, for which the node is unbalanced. We just need to check two nodes here and because to find the unbalanced direction two nodes are sufficient.

## Driver

We can check our AVL tree using a driver method

This will make our tree as

Full source code is shared.