An AVL tree is a binary search tree that has the given properties:

• The sub-tree of each of the node differs in height through at most one.
• Each sub tree will be an AVL tree.

Figure illustrated an AVL tree.

Figure: Balance requirement for AVL tree: the left & right sub tree differ by at most one in height

AVL stands for the names of G.M. Adelson - Velskii & E.M. Landis, two Russian mathematicians, who came up along with this method of keeping the tree balanced.

An AVL tree is a binary search tree that has the balance property and additionally to its key, each of the node stores an additional piece of information: the current balance of its subtree. The three possibilities are following:

• Left - HIGH (balance factor -1)

The left child contain a height which is greater than the right child by 1.

• BALANCED (balance factor 0)

 Both of children have the same height

• RIGHT - HIGH (balance factor +1)

The right child contains a height that is greater by 1.

An AVL tree that remains balanced guarantees O(log n) search time, even into the worst case. Here, n refer to the number of nodes. The AVL data structure gain this property by placing limitation on the difference in heights among the sub- trees of given node and rebalancing the tree even if it violates these limitation.