An AVL tree is another balanced binary search tree. Named after their inventors, Adelson-Velskii and Landis, they were the first dynamically balanced trees to be proposed. Like red-black trees, they are not perfectly balanced, but pairs of sub-trees 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 sub-trees of every node differ in height by at most one.
- Every sub-tree is an AVL tree.
|  |
| | Balance requirement for an AVL tree: the left and right sub-trees 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 sub-tree has a height 1 greater than each right sub-tree. |
 | No Sub-tree with root 8 has height 4 and sub-tree with root 18 has height 2 |
Insertion
As with the red-black 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 left-heavy (the height of the left sub-tree is 1 greater than the right sub-tree), balanced (both sub-trees are the same height) or right-heavy (the height of the right sub-tree is 1 greater than the left sub-tree). 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 sub-tree (shown in green). A right-rotation 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 re-balanced - but at considerable cost - can be re-balanced in O(logn) time.
