The AVL trees, also called "Height Balanced Trees" were first introduced by two Russians named Adelson-Velskii and Landis. AVL trees are maintained in such a way that the trees always remain within one level of being perfectly balanced. As a result of the balance, retrievals from a tree with n nodes may always be performed in O(log n) time. Insertions and deletions on the AVL trees are also done in O (log n) time.

Although the AVL Tree is considered logarithmic balanced, it is not quite "balanced"! AVL can be implemented only for unique keys!

"An AVL Tree is a binary tree with the additional balance property that, for any node in the tree, the height of the left and right subtrees can differ by at most one. "    [Weiss]

1. An empty tree is height balanced.
2. For a tree T, T-L shall denote the left subtree and T-R shall denote the right subtree.
3. For a tree T, h-L shall denote the height of the left subtree (T-L) and h-R shall denote the height of the right subtree (T-R).
4. A non empty binary tree is HEIGHT BALANCED if and only if
   T-R and T-L are height balanced
   -1 <= (h-L) - (h-R)| <= +1
5. The BALANCE FACTOR of a node T in a binary tree bf(T) = h-L - h-R.
6.  For any node T in an AVL tree, bf(T) = -1, 0, or +1

Authors vary with respect to the exact titles and descriptions for the four rotations, but all have essentially the same four rotations. In order to maintain the balance within the tree, nodes will have to be rotated into a balanced location. The nodes will be rotated with respect to the nearest ancestor that contains a +2 or -2 balance factor; the following diagrams will designate this ancestor with respect to the subtree A. An AVL tree will need only four rotations for insertion. AVL trees must be completely constructed with these four rotations in order to work!

1. ROTATE RIGHT rotation - the new node N is inserted on the left subtree of the left subtree of A.
2. ROTATE LEFT rotation - the new node N is inserted on the right subtree of the right subtree of A.
3. DOUBLE -ROTATE RIGHT rotation - the new node N is inserted on the right subtree of the left subtree of A.
4. DOUBLE -ROTATE LEFT rotation - the new node N is inserted on the left subtree of the right subtree of A.

It is important to emphasize that if trees are completely constructed using AVL rotations and insertions, there will only be four possible situations for a rotations.