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: root 5, pivot 3, its left child 2; one right rotation makes 3 the root with children 2 and 5, and subtree B moves from 3 to the left of 5. Right-right case: the mirror image, one left rotation makes 5 the root with children 3 and 7
In the straight cases one rotation lifts the pivot to the top and hands its inner subtree B to the old root.
Left-right case: root 5, left child 3, whose right child is 4; a left rotation at 3 and then a right rotation at 5 make 4 the root with children 3 and 5. Right-left case: the mirror image, a right rotation at 5 and then a left rotation at 3
In the zig-zag cases the middle key 4 is rotated up twice: the first rotation makes the case straight, the second fixes it.

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)
A deleted key with two children is replaced by its in-order predecessor 6 or its successor 9, and the tree is rebalanced from there up.

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.

What the page leaves out

The page keeps small integer keys with no values, and it stores a full height in every node, where compact implementations keep only a balance factor in two bits. Deletion always uses the largest key of the left subtree. It leaves out iterative (non-recursive) insertion with parent pointers, bulk loading a tree from sorted keys, joining and splitting trees, and the cost of cache misses, which matters more in practice than the number of rotations.