AVL Trees: The Balance Factor That Never Reaches ±2

A binary search tree with a promise

A plain binary search tree gives O(log n) lookup only if it stays roughly balanced; insert keys in sorted order into an unbalanced BST and it degenerates into a linked list, with O(n) lookup. The AVL tree, named for its 1962 inventors Georgy Adelson-Velsky and Evgenii Landis, was the first data structure to guarantee O(log n) height no matter what order keys arrive in, by enforcing a simple invariant after every insertion and deletion: for every node, the heights of its left and right subtrees may differ by at most 1.

The balance factor

Every node tracks (or can compute) a balance factor: height of right subtree minus height of left subtree. A legal AVL node has balance factor -1, 0 or +1. Insert or delete a key and the balance factor of every ancestor on the path back to the root may shift by one; if any ancestor's balance factor reaches -2 or +2, the tree is no longer AVL-legal at that node and must be repaired immediately, before returning from the operation, via a rotation.

Single and double rotations

There are exactly four imbalance shapes, and each has a fixed, mechanical fix. A left-left imbalance (the culprit inserted into the left subtree of a left child) is fixed by a single right rotation; a right-right imbalance by a single left rotation. The mixed cases — left-right (inserted into the right subtree of a left child) and right-left — need two rotations in sequence, first straightening the inner zigzag into a single-direction lean, then applying the matching single rotation:

// single right rotation, fixing a left-left imbalance at node z, child y = z.left
rotateRight(z):
  y = z.left
  z.left = y.right
  y.right = z
  update heights of z, then y
  return y                      // y is the new subtree root

// left-right case: two rotations
fixLeftRight(z):
  z.left = rotateLeft(z.left)   // straighten the zigzag first
  return rotateRight(z)          // then apply the matching single rotation

A rotation is a small, constant-time pointer rearrangement — it never touches more than a handful of nodes — and after insertion, at most one rotation (single or double) is ever needed to restore the whole tree's balance, because fixing the lowest unbalanced ancestor also restores the height that ancestor's own parent was expecting. Deletion is less forgiving: it can require rotations at every level on the path back to the root, up to O(log n) rotations in the worst case, because removing a node can shrink a subtree's height in a way that cascades imbalance upward.

Why bother, when red-black trees also guarantee O(log n)?

AVL trees keep a tighter balance invariant than red-black trees — an AVL tree's height never exceeds about 1.44*log2(n), noticeably closer to the theoretical minimum log2(n) than a red-black tree's looser bound of about 2*log2(n) — which makes AVL lookups faster in practice for lookup-heavy workloads. The trade-off is that AVL trees rebalance more aggressively and therefore do more rotation work per insertion or deletion on average, which is why red-black trees are the more common default in general-purpose library implementations (many standard-library ordered maps and sets use them) while AVL trees see more use in read-dominated structures like database and filesystem indexes, where the extra balance discipline pays for itself every time the tree is searched.

Frequently asked questions

Try it live

Everything above runs in your browser — open AVL Tree and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.