Data Structures and Algorithms 8.3 AVL Trees

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:
TreeAVL 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.

### Key terms

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.