AVL Tree Explanation

AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

Why AVL Trees?

Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary tree. If we make sure that height of the tree remains O(Logn) after every insertion and deletion, then we can guarantee an upper bound of O(Logn) for all these operations. The height of an AVL tree is always O(Logn) where n is the number of nodes in the tree.

To make sure that the given tree remains AVL after every insertion, we must augment the standard BST insert operation to perform some re-balancing. Following are two basic operations that can be performed to re-balance a BST without violating the BST property (keys(left) < key(root) < keys(right)).
1) Left Rotation
2) Right Rotation

T1, T2 and T3 are subtrees of the tree 
rooted with y (on the left side) or x (on 
the right side)           
     y                               x
    / \     Right Rotation          /  \
   x   T3   - - - - - - - >        T1   y 
  / \       < - - - - - - -            / \
 T1  T2     Left Rotation            T2  T3
Keys in both of the above trees follow the 
following order 
 keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)
So BST property is not violated anywhere.

It is the speciality of AVL tree that it has been re-balanced by two rotations (left or right) keeping maximum 1 distance between left and right subtrees . 

 There are four different use cases to insert into AVL tree
 * left left - needs ones right rotation
   if (balance > 1 && key < node->left->key)  
   
 * left right - needs one left and one right rotation
   if (balance > 1 && key > node->left->key)  

 * right left - needs one right and one left rotation
   if (balance < -1 && key < node->right->key)  

 * right right - needs one left rotation
   if (balance < -1 && key > node->right->key)  

where balance is equal to = height(N->left) - height(N->right).

 At every node we will also keep height of the tree so that we don't have to recalculate values again.
  
 Average Runtime complexity to insert into AVL tree is O(logn).In worst case it will take O(2*logn) time complexity.