Trinity University

Computer Science Department

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]

- An empty tree is
__height balanced__. - For a tree T, T-L shall denote the left subtree and T-R shall denote the right subtree.
- 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).
- 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` - The BALANCE FACTOR of a node T in a
binary tree
`bf(T) = h-L - h-R.` - 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!__

**ROTATE RIGHT**rotation - the new node N is inserted on the left subtree of the left subtree of A.**ROTATE LEFT**rotation - the new node N is inserted on the right subtree of the right subtree of A.**DOUBLE -ROTATE RIGHT**rotation - the new node N is inserted on the right subtree of the left subtree of A.**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.

Sample Exam Questions