Skip to main content

AVL Trees and the Height-Balanced Alternative

What This Concept Is​

An AVL tree is a BST where every node stores a balance factor equal to

bf(x) = height(left(x)) - height(right(x))

and the tree maintains the invariant

|bf(x)| <= 1 for every node x.

Every insertion or deletion walks back up to the root, updating heights, and performs a single or double rotation at the first ancestor whose balance factor becomes +2 or -2. The invariant keeps height within about 1.44 log(n) of optimal, which is slightly tighter than red-black's 2 log(n) bound.

AVL trees were the first self-balancing BST (Adelson-Velsky & Landis, 1962) and remain the tightest of the rank-based family. They are a good teaching example because the invariant is almost trivially restated -- "every node is nearly height-balanced" -- and the rotation cases mirror it one-to-one without the indirection of "coloring."

The tradeoff is that AVL's tighter balance costs more rotations during updates. On insertion, at most one rotation (single or double) restores the invariant; on deletion, however, a rotation can shrink a subtree's height by one and propagate imbalance to the next ancestor, so a single delete may require O(log n) rotations up the tree. Red-black trees avoid this amplification at the cost of a laxer shape.

In a modern microbenchmark, AVL typically wins on pure-lookup workloads (tighter tree, shorter paths), and red-black wins when writes are a significant fraction of traffic. Both are always O(log n) per operation; the winning margin is usually under 15% either way on general-purpose hardware.

Why It Matters Here​

AVL trees are the "other" classical balanced BST. They matter for three reasons:

  • they give a tighter height bound than red-black, so lookups can be marginally faster
  • the invariant is easier to state and explain than red-black coloring
  • the tradeoff is that rebalancing after insertion or deletion can require more rotations, which makes update-heavy workloads slightly slower

In practice, red-black wins when writes dominate and AVL wins when reads dominate. Both are O(log n) per operation; the constants differ. AVL also shows up in specialist contexts: databases that want the tightest possible fan-out (e.g., some older in-memory B-tree variants), and competitive programming templates for ordered set / multiset where balance is explicit.

Concrete Examples​

Example 1 -- right-right rotation. Insert 10, 20, 30 into an empty AVL tree. After 10 and 20 the tree is still balanced:

  10
    \
    20

Now insert 30. The tree becomes a right-leaning chain and the balance factor of 10 becomes -2:

  10   (bf = -2)
    \
    20 (bf = -1)
      \
      30 (bf = 0)

This is a right-right case, fixed by a single left rotation at 10:

    20
   /  \
  10   30

All balance factors are 0; the invariant is restored.

Example 2 -- left-right double rotation. Starting from a tree containing {30, 10}, insert 20:

  30   (bf = 2)
 /
10    (bf = -1)
  \
  20

This is a left-right case. First, left-rotate at 10:

    30
   /
  20
 /
10

Then right-rotate at 30:

    20
   /  \
  10   30

Two rotations, all balance factors zero, invariant restored. The "double rotation" is not a single exotic move; it is a left then a right on adjacent ancestors. The key observation: a zig-zag imbalance needs two rotations because a single rotation would merely transfer the imbalance to the other side.

Common Confusion / Misconceptions​

"The four cases are about the inserted key's position." AVL's four rotation cases map to the shape of the imbalance, not to the position of the inserted key. The cases are:

  • left-left (single right rotation)
  • right-right (single left rotation)
  • left-right (double rotation: left then right)
  • right-left (double rotation: right then left)

The mistake is to memorize "inserted on the left of the left child" as a rule about the new node. It is actually a rule about the imbalance shape at the first unbalanced ancestor, which can be several edges above the insertion point.

"AVL's 1.44 log n bound makes it noticeably faster." It does not. The constant-factor gap between 1.44 log n and 2 log n (red-black) is under 40%, which is already inside the noise of cache misses and branch prediction. Measure before you switch.

"A balance factor can be stored in a single bit." Only if the tree is guaranteed to be strict AVL (no bf = 2 ever stored). Standard implementations store two bits or three-state enums; a cleaner design stores the full subtree height as a small integer and derives bf on demand.

"Deletion needs at most one rotation, like insertion." No. Insertion is bounded by one rotation because a successful rotation leaves the subtree's height unchanged. Deletion can shrink the subtree's height after a rotation, propagating imbalance upward through O(log n) ancestors, each potentially requiring another rotation.

How To Use It​

For insertion:

  1. BST-insert the new node
  2. walk back up to the root, updating heights and balance factors
  3. at the first node with |bf| = 2, apply the matching single or double rotation
  4. updates stop: a correct rotation restores the subtree to its pre-insert height

For deletion:

  1. BST-delete as usual
  2. walk back up, updating heights
  3. apply rotations where imbalance appears
  4. unlike insertion, deletion may require rotations at multiple ancestors (subtree height can shrink and propagate)

For choosing AVL vs red-black vs others:

  • read-heavy, low-cardinality updates: AVL (tighter, faster lookups)
  • balanced or write-heavy: red-black (fewer rotations per update)
  • concurrent, lock-free, or easy-to-code: skip list or treap (next concepts)

Transfer / Where This Shows Up Later​

  • S5 (OS): AVL-like height-balanced trees appeared in older BSD process tables; the idea survives in any in-memory scheduler that needs guaranteed worst-case insert/lookup.
  • S6 (databases): AVL does not survive to disk (B+trees dominate), but the analysis -- counting rotations, bounding height with Fibonacci-like recurrences -- reappears when proving B-tree split/merge bounds.
  • S7 (architecture): "tighter worst-case vs lower update cost" is a classic trade-off captured in every balanced-tree ADR. The AVL vs red-black decision is your first exposure to it.
  • S8 (scale): consistent-hashing rings in distributed caches (Memcached, Cassandra, Redis Cluster) are often implemented as AVL or red-black trees keyed by hash ring position, because the data changes slowly but lookups dominate.

Check Yourself​

  1. What is the exact balance invariant in an AVL tree?
  2. Why does a single rotation restore the invariant in the left-left case but not the left-right case?
  3. Why can deletion require multiple rotations while insertion never requires more than one?
  4. When would you prefer AVL over red-black, and vice versa?
  5. What is the relationship between an AVL tree's size n and its maximum height, and why does the Fibonacci sequence appear in the proof?
  6. If you store only a 2-bit balance factor, how do you handle the transient |bf| = 2 state during fixup?

Mini Drill or Application​

  1. Insert 30, 20, 10, 25, 40, 50, 5 into an empty AVL tree. Draw the tree after each insertion and annotate every rotation.
  2. Delete 30 from your final tree. Redraw and note any rotations.
  3. Compute the height of your final tree and compare it to 1.44 log(n) for the current n.
  4. Implement AVL insert and delete in Python or C++ in under 120 lines. Insert 10^6 random keys, then delete half of them, and print height / log2(n) at the end.
  5. Construct the smallest AVL tree of height h for h = 1, 2, 3, 4 and confirm the node counts match Fibonacci numbers F(h+3) - 1.

Read This Only If Stuck​