**1 Answer**

written 17 months ago by | • modified 17 months ago |

**AVL Tree**

AVL Trees are

*Self-Balanced Binary Search Trees.*In AVL trees, the balancing factor of each node is either

*0 or 1 or -1.***Balance Factor of AVL Tree**calculated as**= Height of Left Sub-tree - Height of Right Sub-tree**

**Construction of AVL Trees -**

Insertion Operation is performed to construct the AVL Tree.

Inserting the element in the AVL tree is same as the insertion performed in BST.

After insertion, check the balance factor of each node of the resulting tree.

After the insertion, the balance factor of each node is either

then the tree is considered to be*0 or 1 or -1,*,*balanced*, and inserts the next element if any.*concludes the operation*After the insertion, the balance factor of at least one node is

, then the tree is considered to be*not 0 or 1 or -1*,*imbalanced*to balance the tree, and after the tree is balanced, insert the next element if any.*perform the suitable rotation*

**Rotations used to Balance the AVL Tree -**

After inserting an element in the AVL tree,

If a tree becomes imbalanced, then there exists one particular node in the tree by balancing which the entire tree becomes balanced automatically.

- To rebalance the tree, balance that particular node.

*To find that particular node:*

- Traverse the path from the newly inserted node to the root node.
- Check the balance factor of each node that is encountered while traversing the path.
- The first encountered imbalanced node will be the node that needs to be balanced.

*To balance that node:*

- Count three nodes in the direction of the leaf node.
Then, use the concept of AVL Tree Rotations to rebalance the tree.

**LL Rotation -***In LL rotation, every node moves one position to left from the current position.***RR Rotation -***In RR rotation, every node moves one position to right from the current position.***LR Rotation -***In LR rotation, at first, every node moves one position to the left and then one position to right from the current position.***RL Rotation -***In RL rotation, at first every node moves one position to right and then one position to left from the current position.*