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]
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!
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.