An unbalanced binary search tree has the worst case search time of O(n). Therefore, balancing the tree will make search time more efficient.

AVL Tree, named after its inventors Adelson-Velsky and Landis, is a special variation of Binary Search Tree which exhibits self-balancing property .AVL Trees automatically attain the minimum possible height of the tree after the execution of any operation.

AVL tree self balances by keeping a check on the balance factor of every node.

Balance_factor = (Height of Left sub-tree) - (Height of right sub-tree)

The balance factor of any given node can only take the value of -1 , 0 and 1.To maintain this criteria AVL tree performs Tree rotations

After each insertion or deletion, if the balance factor of any node does not follow the AVL balance property, the AVL tree balances itself through the following rotation techniques:

• LL Rotation
• RR Rotation
• LR Rotation
• RL Rotation

LL Rotation

It is a type of single rotation that is performed when the tree gets unbalanced, upon insertion of a node into the left subtree of the left child of the imbalance node i.e., upon Left-Left (LL) insertion.

RR Rotation

It is a type of single rotation that is performed when the tree gets unbalanced, upon insertion of a node into the right subtree of the right child of the imbalance node i.e., upon Right-Right (RR) insertion.

LR Rotation

LR rotation is performed when the tree gets unbalanced , upon insertion of a node into the right subtree of the left child of the imbalance node, upon Left -Right (LR) insertion.

LR rotation is a combination of a RR rotation followed by a LL rotation.

RL Rotation

RL rotation is performed when the tree gets unbalanced , upon insertion of a node into the left subtree of the right child of the imbalance node, upon Right-Left(RL) insertion. RL rotation is a combination of a LL rotation followed by a RR rotation.