An AVL tree is a binary search tree (BST) in which the height of left and right sub tree of each node will be with maximum difference one. With the help of AVL tree , searching, insertion and deletion in a tree with node n is achieved in time of order O(n) , even in worst case.