# AVL tree

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.