AVL Tree
An AVL tree is a binary tree in which the difference in heights between the left and the right subtree is not more than one for every node.
We can insert a node into an AVL tree by using the insertion algorithm for binary search trees in which we compare the key of the new node with that in the root and then insert the new node into the left subtree or right subtree depending on whether it is less than or greater than that in the root. Insertion may or may not result in change in the height of the tree. While inserting we must take care that the balance factor of any node not changes to values other than 0, 1 and -1. A tree becomes unbalanced if and only if
(i) The newly inserted node is a left descendant of a node that previously had a balance of 1.
(ii) The newly inserted node is a right descendent of a node that previously had a balance of -1.
If the balance factor of any node changes during insertion than one of the subtree is rotated one or more times to ensure that the balance factor is restored to correct values.
