AVL Trees

Properties of an AVL tree

  • In an AVL tree, the heights of the two child subtrees of any node differ by at most one; therefore, it is also said to be height-balanced.
  • Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree.
  • Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.
  • The balance factor of a node is the height of its right subtree minus the height of its left subtree and a node with a balance factor 1, 0, or -1 is considered balanced.

Insertion

  • After inserting a node, it is necessary to check each of the node's ancestors for consistency with the AVL rules.
  • For each node checked, if the balance factor remains 1, 0, or -1 then no rotations are necessary. Otherwise, it's unbalanced.
  • After each insertion, at most two tree rotations are needed to restore the entire tree.

There are four cases, choosing which one depends on different types of unbalanced relations. In the following cases, assume Root is the initial parent before a rotation and Pivot is the child to take the root's place.

Left-left case, fixed by a right rotation: root 5 has left child pivot 3, whose left child is 2; after the rotation 3 is the root with children 2 and 5, and subtree B moves from 3 to the left of 5

Right-right case, fixed by a left rotation: root 3 has right child pivot 5, whose right child is 7; after the rotation 5 is the root with children 3 and 7, and subtree B moves from 5 to the right of 3

Left-right case, fixed by a left rotation and then a right rotation: root 5, left child 3, whose right child is 4; rotating 3-4 left makes 4 the left child of 5, then rotating 5 right makes 4 the root with children 3 and 5

Right-left case, fixed by a right rotation and then a left rotation: root 3, right child 5, whose left child is 4; rotating 5-4 right makes 4 the right child of 3, then rotating 3 left makes 4 the root with children 3 and 5

Deletion

  • If a node is a leaf, remove it.
  • If the node is not a leaf, replace it with either the largest in its left subtree (rightmost) or the smallest in its right subtree (leftmost), and remove that node. The node that was found as replacement has at most one subtree.
  • After deletion, retrace the path from parent of the replacement to the root, adjusting the balance factors as needed.
  • More complicated rules for stopping. The retracing can stop if the balance factor becomes -1 or +1 indicating that the height of the subtree has remained unchanged. If the balance factor becomes 0 then the height of the subtree has decreased by one and the retracing needs to continue. This is in contrast to an insertion where a rotation resulting in a balance factor of 0 indicated that the subtree's height has remained unchanged.

Deleting node 7, which has two children: it is replaced either by 6, the largest key in its left subtree (left), or by 9, the smallest key in its right subtree (right)

Overall, the time required is O(log n) for lookup, plus a maximum of O(log n) rotations on the way back to the root, so the deletion can be completed in O(log n) time.

Lookup (Search)

Lookup in an AVL tree is exactly the same as in an unbalanced BST. Because of the height-balancing of the tree, a lookup takes O(log n) time.

Example. Insert 14, 17, 11, 7, 53, 4, 13, 12, 8 into an empty AVL tree and then remove 53, 11, 8 from the AVL tree. Try it with the animation above: type each key and press Insert, then Delete.

Where AVL trees are used

AVL trees are the stricter of the two classic balanced binary search trees. Keeping every node's subtree heights within one of each other holds the height to about 1.44 log2 n, against 2 log2 n for a red-black tree. That buys slightly faster lookups, and costs more work on writes: an AVL deletion may rotate at every level on the way back to the root, where a red-black deletion never needs more than three rotations. The rule of thumb follows directly — AVL when reads dominate, red-black when the tree is written to constantly.

  • ZFS and the illumos/Solaris kernel. A general AVL implementation (avl_tree_t) is used throughout, for range trees, metaslabs and many other in-kernel ordered sets.
  • Functional and persistent maps. OCaml's Map and Set modules are height-balanced trees of this kind. The balance condition is local and easy to restore while sharing structure between versions, which suits immutable data.
  • Read-mostly in-memory indexes, where the table is built once or rarely updated and then queried heavily, and the shorter tree pays for itself.
  • Situations that want a predictable worst case rather than a good average: the tight height bound makes the cost of a lookup easy to reason about, which matters in real-time and embedded settings.

Where AVL trees are not used is just as informative. The C++, Java and .NET ordered containers all chose red-black instead, because a library cannot know whether its user will read or write more. And on disk the whole question is moot: there a node should be a page holding hundreds of keys, which is a B+ tree, not a binary tree.