**AVL tree:**

AVL tree is a self balancing binary search tree, in which the heights of the two sub trees of a node may differ by at most one.

Due to this property, the AVL tree is also known as height balance tree.

The key advantage of using an AVL tree is that, it takes O (log n) time to perform search, insert and delete operations in an average case as well as the worst case (because the height of the tree is limited to O (log n)

It is a binary search tree in which node has a balance faster of -1, 0 or 1 is said to be height balanced.

There are four types of re-balancing rotations and applications of these rotations depends on the position of the inserted node with reference to the critical node.

The four categories of rotations are:

**a] LL rotation :** The new node is inserted in the left sub tree of the left sub tree of the critical node.

**b] RR rotation:** The new node is inserted in the right sub tree of the right sub tree of the critical node.

**c] LR rotation:** The new node is inserted in the right sub tree of the left sub tree of the critical node.

**d] RC rotation:** The new node is inserted in the left sub tree of the right sub tree of the critical node.

**Example:**

44 17 32 78 50 88 48 62 54

**Step 1:** Insert 44

**Step 2:** Insert 17

**Step 3:** Insert 32

**Step 4:** Insert 78

**Step 5:** Insert 50

**Step 6:** Insert 88

**Step 7:** Insert 48 **Step 8:** Insert 62

**Step 9:** Insert 54