AVL Tree

How an AVL tree stays balanced

A plain binary search tree degenerates the moment you insert sorted data. Insert 1, 2, 3, 4, 5 in order and you get a linked list — every "search" walks the entire list, blowing past O(log n) into O(n). Adelson-Velsky and Landis fixed this in 1962 with the first self-balancing BST, named AVL after their initials.

The invariant is simple: for every node, the heights of its left and right subtrees differ by at most 1. The balance factor is defined as height(right) − height(left), and it must always be in {-1, 0, +1}. After every insert or delete, walk back up from the modified leaf and check each ancestor. If a balance factor reaches ±2, the tree is out of spec and must be rotated back into shape.

Four imbalance shapes can occur, and each has a fix:

The four rotations

Right-Right (RR) — single left rotation. A heavy right-right subtree:

      A                          B
       \                         / \
        B           -->         A   C
         \
          C

Pivot B up, A becomes its left child. B's old left child becomes A's right child. Heights drop by one.

Left-Left (LL) — single right rotation. Mirror image of RR:

        C                       B
       /                        / \
      B               -->      A   C
     /
    A

Left-Right (LR) — rotate child left, then rotate root right. The imbalance zig-zags:

      C                C                  B
     /                /                   / \
    A         -->    B          -->     A   C
     \              /
      B            A

A single rotation can't fix a zig-zag. Rotate A's right child up first to straighten the line into LL, then rotate normally.

Right-Left (RL) — rotate child right, then rotate root left. Mirror of LR:

    A                A                    B
     \                \                  / \
      C       -->      B          -->  A   C
     /                  \
    B                    C

The rule: when the imbalance is "outside-outside" (LL or RR), one rotation suffices. When it zig-zags ("inside"), you need two. Insert always finishes with at most one rotation event (single or double); delete may cascade.

When to choose AVL

• Lookup-heavy workloads where the lower height pays back over millions of reads.
• Range queries and ordered iteration — AVL keeps in-order traversal cheap, like any BST.
• Predictable worst case — unlike a hash table, an AVL has no probabilistic blow-ups.
• Memory databases where pointer chasing is acceptable and disk-locality doesn't matter.

If your workload is write-heavy, prefer a red-black tree. If you need on-disk performance, prefer a B-tree or B+ tree. AVL's strict balance is a liability when most operations are inserts and deletes.

AVL vs other balanced BSTs

	AVL	Red-black	Splay tree	Treap	Weight-balanced	Scapegoat
Worst-case height	≈ 1.44 log₂ n	≤ 2 log₂(n+1)	n (amortized log n)	O(log n) expected	O(log n)	O(log n) amortized
Search	O(log n)	O(log n)	O(log n) amortized	O(log n) expected	O(log n)	O(log n)
Insert rotations (worst)	2	2	O(log n) splays	O(log n)	0 (rebuild instead)	0 (rebuild instead)
Delete rotations (worst)	O(log n)	3	O(log n) splays	O(log n)	O(log n)	O(log n) amortized
Per-node overhead	2 bits balance	1 bit color	none	random priority	subtree size	none (counter at root)
Real-world use	Some DBs, in-memory indices	std::map, Java TreeMap, Linux RB	compilers, caches	competitive programming	functional libraries	simple amortized solution

The headline difference is rebalance cost. AVL's tighter invariant gives shorter trees and faster searches, but doubles the insert/delete work versus red-black. Most general-purpose libraries pick red-black because their workloads are mixed; AVL wins where you build the tree once and query forever.

What the numbers actually say

• Maximum height ≈ 1.44 log₂ n. The worst case is the Fibonacci tree — a tree where each node has subtrees of consecutive Fibonacci heights. So a 1-million-element AVL is at most height 30, vs 20 for a perfect tree, vs 40 for a red-black tree.
• Average rotations per insert: about 0.5, despite the worst-case bound of 2. Most inserts don't trigger any rotation at all.
• Average rotations per delete: about 0.7 log n — still modest, but ≈10× more work than red-black.
• Space overhead is 2 bits per node. In practice languages waste an int per node because bitfields are awkward.

JavaScript implementation

class Node {
  constructor(key) { this.key = key; this.left = null; this.right = null; this.h = 1; }
}

const height = n => n ? n.h : 0;
const balance = n => n ? height(n.right) - height(n.left) : 0;
const update = n => { n.h = 1 + Math.max(height(n.left), height(n.right)); };

function rotateRight(y) {
  const x = y.left, t = x.right;
  x.right = y; y.left = t;
  update(y); update(x);
  return x;
}

function rotateLeft(x) {
  const y = x.right, t = y.left;
  y.left = x; x.right = t;
  update(x); update(y);
  return y;
}

function insert(node, key) {
  if (!node) return new Node(key);
  if (key < node.key) node.left = insert(node.left, key);
  else if (key > node.key) node.right = insert(node.right, key);
  else return node;                 // no duplicates

  update(node);
  const b = balance(node);

  // LL — heavy on the left, key smaller than left's key
  if (b < -1 && key < node.left.key)  return rotateRight(node);
  // RR — heavy on the right, key larger than right's key
  if (b >  1 && key > node.right.key) return rotateLeft(node);
  // LR — heavy left, but key fell to left.right; rotate left first
  if (b < -1 && key > node.left.key) {
    node.left = rotateLeft(node.left);
    return rotateRight(node);
  }
  // RL — heavy right, but key fell to right.left; rotate right first
  if (b >  1 && key < node.right.key) {
    node.right = rotateRight(node.right);
    return rotateLeft(node);
  }
  return node;
}

Two implementation details worth flagging. First, every recursive call returns the (possibly-new) subtree root — assignment to node.left or node.right is how you propagate rotations back up. Second, balance factor is recomputed from height after every change rather than maintained directly; it's clearer and the cost is negligible.

Python implementation

class Node:
    __slots__ = ('key', 'left', 'right', 'h')
    def __init__(self, key):
        self.key, self.left, self.right, self.h = key, None, None, 1

def h(n):  return n.h if n else 0
def bf(n): return h(n.right) - h(n.left)
def upd(n): n.h = 1 + max(h(n.left), h(n.right))

def rot_right(y):
    x = y.left
    y.left, x.right = x.right, y
    upd(y); upd(x)
    return x

def rot_left(x):
    y = x.right
    x.right, y.left = y.left, x
    upd(x); upd(y)
    return y

def insert(node, key):
    if not node: return Node(key)
    if   key < node.key: node.left  = insert(node.left,  key)
    elif key > node.key: node.right = insert(node.right, key)
    else: return node
    upd(node)
    b = bf(node)
    if b < -1 and key < node.left.key:  return rot_right(node)
    if b >  1 and key > node.right.key: return rot_left(node)
    if b < -1 and key > node.left.key:
        node.left = rot_left(node.left)
        return rot_right(node)
    if b >  1 and key < node.right.key:
        node.right = rot_right(node.right)
        return rot_left(node)
    return node

def delete(node, key):
    if not node: return None
    if   key < node.key: node.left  = delete(node.left,  key)
    elif key > node.key: node.right = delete(node.right, key)
    else:
        if not node.left:  return node.right
        if not node.right: return node.left
        succ = node.right
        while succ.left: succ = succ.left
        node.key = succ.key
        node.right = delete(node.right, succ.key)
    upd(node)
    b = bf(node)
    # Same four cases — but compare against subtree balance, not the deleted key.
    if b < -1 and bf(node.left)  <= 0: return rot_right(node)
    if b < -1 and bf(node.left)  >  0:
        node.left = rot_left(node.left); return rot_right(node)
    if b >  1 and bf(node.right) >= 0: return rot_left(node)
    if b >  1 and bf(node.right) <  0:
        node.right = rot_right(node.right); return rot_left(node)
    return node

Note the asymmetry between insert and delete: insert decides which rotation to apply by comparing the inserted key to subtree keys, but delete has to inspect the balance factor of the deeper subtree instead — there's no inserted key to compare against.

Variants worth knowing

Weight-balanced trees (BB[α]). Instead of height, keep size(left) and size(right) within a constant ratio α. Used in functional programming where you have subtree sizes anyway, and in some persistent data structures.

Scapegoat trees. Don't rebalance per-operation. Instead, when an operation creates an unbalanced ancestor (depth > α · log n), rebuild that subtree from scratch in linear time. Amortizes to O(log n) and stores nothing per node — just a global counter.

WAVL trees. "Weak AVL" — relaxes the balance condition slightly to give red-black-style cheap deletion while keeping AVL-style cheap insertion. A 2015 design that hasn't seen wide adoption.

2-3 trees and 2-3-4 trees. Multi-way generalisations where each node has 2, 3, or 4 children. Conceptually cleaner balancing rules; red-black is the binary encoding of a 2-3-4 tree.

Splay trees. Rotate the just-accessed node to the root on every operation. Hot keys end up shallow without explicit caching; worst case per operation is O(n), but amortized cost is O(log n).

Common bugs and edge cases

• Forgetting to update height after rotation. The two affected nodes both need fresh heights, in the right order: child first, then new root.
• Mishandling LR/RL detection. The condition is key > node.left.key for LR, not balance(node.left) > 0. Mixing them up rotates the wrong way.
• Not propagating the new subtree root. A rotation returns a new root; if you don't reassign parent.left = rotate(parent.left), the parent still points at the old root.
• Stopping rebalance too early on delete. Insert can early-exit once balance returns to 0; delete must continue all the way to the root because each rotation may propagate the height change up.
• Using AVL when a hash table would do. If you don't need ordered traversal or range queries, a hash table is faster and simpler.
• Comparing AVL to red-black with cold caches. Microbenchmarks favor AVL on lookups; production workloads often favor red-black because writes are common and rotations are cheaper.