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