Data Structures and Algorithms

8.3 AVL Trees

An AVL tree is another balanced
binary search tree.
Named after their inventors,
AdelsonVelskii and Landis,
they were the first dynamically balanced trees to be proposed.
Like redblack trees, they are not perfectly balanced, but
pairs of subtrees differ in height by at most 1,
maintaining an
O(logn) search time.
Addition and deletion operations also take
O(logn) time.
Definition of an AVL tree
An AVL tree is a binary search tree which has the
following properties:
 The subtrees of every node differ in height by at most one.
 Every subtree is an AVL tree.



Balance requirement for an AVL tree:
the left and right subtrees differ by
at most 1 in height. 
You need to be careful with this definition: it permits
some apparently unbalanced trees!
For example, here are some trees:
Tree  AVL tree? 
 Yes
Examination shows that each left subtree has a height 1 greater
than each right subtree. 
 No
Subtree with root 8 has height 4 and subtree with root 18
has height 2 
Insertion
As with the redblack tree,
insertion is somewhat complex and involves a number
of cases.
Implementations of AVL tree insertion may be found in many
textbooks:
they rely on adding an extra attribute, the
balance factor
to each node.
This factor indicates whether the tree is
leftheavy (the height of the left subtree is 1 greater
than the right subtree),
balanced (both subtrees are the same height) or
rightheavy (the height of the right subtree is 1 greater
than the left subtree).
If the balance would be destroyed by an insertion,
a rotation is performed to correct the balance.

A new item has been added to the left subtree of node 1,
causing its height to become 2 greater than 2's
right subtree (shown in green).
A rightrotation is performed to correct the imbalance.

 AVL trees
 Trees which remain balanced  and thus guarantee
O(logn) search times  in a dynamic environment.
Or more importantly, since any tree can be rebalanced  but at
considerable cost  can be rebalanced in O(logn) time.
© John Morris, 1998