AVL Trees

Why balance matters

Remember the "guess my number" game: "Is it higher or lower than 50?" Each answer throws away half of the possibilities, so you need only about 7 questions for 100 numbers. A well-shaped BST works the same way. A badly shaped BST is like a friend who only answers "higher" — you end up trying every number one by one.

In the previous chapter every BST operation — search, insert, delete — cost O(h), where h is the height of the tree. The catch is that h depends on the order of the insertions. Insert 1, 2, 3, …, n into a plain BST and you get a linked list with height n − 1, so a search costs O(n). Sorted or nearly sorted input is common in practice (IDs, timestamps, alphabetical names), so "hope the input is random" is not a strategy.

Here are the same seven keys, inserted in the order 1, 2, 3, 4, 5, 6, 7, into a plain BST and into an AVL tree:

Plain BST (height 6)            AVL tree (height 2)

1                                      4
 \                                   /   \
  2                                 2     6
   \                               / \   / \
    3                             1   3 5   7
     \
      4          search(7): 7 steps       search(7): 3 steps
       \
        5
         \
          6
           \
            7

A self-balancing BST repairs its shape after every update so that h stays O(log n) whatever the insertion order. The AVL tree (Adelson-Velsky and Landis, 1962) was the first such structure, and it is still the easiest one to reason about.

Height and balance factor

This chapter uses the same convention as the BST chapter:

Tree	Height
empty (null)	−1
a single node (leaf)	0
any other node	1 + max(height(left), height(right))

The balance factor of a node is

bf(node) = height(node.left) − height(node.right)

A positive bf means "left-heavy", a negative bf "right-heavy". Each node stores its own height in a field, so bf is computed in O(1) instead of recomputing heights recursively.

Worked example. Heights (h) and balance factors (bf) of a small tree:

            20   h=2, bf = 1 − 0 = +1
           /  \
  h=1 →  10    30   ← h=0, bf = −1 − (−1) = 0
        /
       5   h=0, bf=0

Node 10: left height 0 (the leaf 5), right height −1 (empty), so bf(10) = 0 − (−1) = +1. Node 20: left height 1, right height 0, so bf(20) = +1. Every node is within −1 … +1.

private static class Node {
    int key;
    int height;          // leaf = 0
    Node left, right;
    Node(int key) { this.key = key; }
}

private static int height(Node n) { return n == null ? -1 : n.height; }

private static void update(Node n) {
    n.height = 1 + Math.max(height(n.left), height(n.right));
}

private static int balance(Node n) { return height(n.left) - height(n.right); }

The AVL invariant

In plain words: at every node, the two sides may differ in height by at most one. Not only at the root — everywhere.

An AVL tree is a BST in which every node has bf ∈ {−1, 0, +1}, i.e. |bf| ≤ 1. The two subtrees of any node differ in height by at most one. The root alone being balanced is not enough — the condition is checked at every node.

      8     root: bf = 2 − 2 = 0  (balanced)
     / \
    4   12
   /      \
  2        14
 /           \
1             15     node 4: bf = 1 − (−1) = +2  → NOT an AVL tree

The root of this tree looks perfect, but nodes 4 and 12 are both out of balance, so the tree is not an AVL tree.

An insertion or deletion changes the height of subtrees only along the path from the root to the changed node, so only nodes on that path can violate the invariant, and after one insertion their bf can only reach ±2 — never ±3.

Rotations: the one repair tool

A rotation re-hangs three pointers so that a child moves up and its parent moves down, while the BST ordering is preserved. It costs O(1).

Right rotation at z (fixes a left-heavy z whose left child y is left-heavy or balanced):

          z                         y
         / \                      /   \
        y   T4                   x     z
       / \        rotate        / \   / \
      x   T3      right(z)     T1 T2 T3  T4
     / \          ------->
    T1  T2

The only subtree that changes parent is T3: it was y's right child and becomes z's left child. The in-order sequence T1 x T2 y T3 z T4 is unchanged.

Why is it still a BST? Every key in T3 is bigger than y (it was in y's right subtree) and smaller than z (it was in z's left subtree). After the rotation T3 sits to the right of y and to the left of z — exactly where those keys belong.

private static Node rotateRight(Node z) {
    Node y = z.left;
    z.left = y.right;     // T3 moves across
    y.right = z;
    update(z);            // z is now lower: update it first
    update(y);
    return y;             // new root of this subtree
}

A left rotation is the mirror image (y = z.right; z.right = y.left; y.left = z;).

The smallest example. Insert 30, 20, 10. After 10 arrives, node 30 has bf = +2 and its left child 20 has bf = +1: the tree leans to the left twice. One right rotation at 30 fixes it:

after insert 30    after insert 20    after insert 10       after rotateRight(30)

      30                 30              30  bf=+2                 20
                        /               /                         /  \
                      20              20    bf=+1               10    30
                                     /
                                   10

The mirror image — insert 10, 20, 30 — gives bf(10) = −2 and bf(20) = −1, fixed by one left rotation at 10. The result is the same tree 20(10, 30).

The four imbalance cases

In plain words: find the first node that tipped over, then look at which way the path bends during the next two steps down towards the new key. A straight path (left-left or right-right) needs one rotation. A bent path (left-right or right-left, a "zig-zag") needs two.

Let z be the lowest node on the insertion path whose |bf| became 2. The case is named after the two steps from z towards the new key:

Case	New key went into…	bf(z)	bf(child)	Fix
LL	left subtree of z's left child	+2	+1	single right rotation at z
RR	right subtree of z's right child	−2	−1	single left rotation at z
LR	right subtree of z's left child	+2	−1	left rotation at the child, then right rotation at z
RL	left subtree of z's right child	−2	+1	right rotation at the child, then left rotation at z

A memory aid: the rotation always goes against the heavy side. Left-heavy → rotate right. Right-heavy → rotate left.

The zig-zag cases (LR, RL) need a double rotation. A single right rotation at z in the LR case just produces a mirror-image imbalance: the middle subtree x moves across and the tree is still off by two, now on the other side.

LR case (the double rotation makes x — the middle key of the three — the new root):

        z                 z                    x
       / \               / \                 /   \
      y   T4            x   T4              y     z
     / \      left(y)  / \      right(z)   / \   / \
    T1  x     ------> y   T3    ------->  T1 T2 T3  T4
       / \           / \
      T2  T3        T1  T2

The smallest LR example. Insert 30, 10, 20. Node 30 has bf = +2, but its left child 10 has bf = −1: the path bends (left, then right).

after insert 20        rotateLeft(10)        rotateRight(30)

     30  bf=+2              30                    20
    /                      /                     /  \
  10     bf=−1           20                    10    30
    \                   /
     20               10

The first rotation turns the bent path into a straight one (LR becomes LL); the second rotation is the ordinary LL fix. The RL case (insert 10, 30, 20) is the mirror image: rotateRight(30), then rotateLeft(10), and again 20 ends on top.

RL is the mirror image. A handy way to remember the result: in every case the median of the three keys z, y, x becomes the subtree root with the other two as its children.

private static Node rebalance(Node n) {
    update(n);
    int bf = balance(n);
    if (bf > 1) {                                        // left-heavy
        if (balance(n.left) < 0) n.left = rotateLeft(n.left);    // LR → LL
        return rotateRight(n);                                   // LL
    }
    if (bf < -1) {                                       // right-heavy
        if (balance(n.right) > 0) n.right = rotateRight(n.right); // RL → RR
        return rotateLeft(n);                                     // RR
    }
    return n;                                            // already balanced
}

Rebalancing after insertion

In plain words: insert the key exactly as in a normal BST, then walk back up towards the root, fixing heights as you go. The first node you find that has tipped over gets one (single or double) rotation, and then you are done.

Insertion is ordinary BST insertion followed by a walk back up the path. The recursive version does the walk for free: after each recursive call returns, the node updates its height and calls rebalance.

private Node insert(Node n, int key) {
    if (n == null) return new Node(key);                 // height 0
    if (key < n.key)      n.left  = insert(n.left, key);
    else if (key > n.key) n.right = insert(n.right, key);
    else return n;                                       // duplicate: no change
    return rebalance(n);                                 // on the way back up
}

After an insertion at most one (single or double) rotation is ever performed. The rotation at the lowest unbalanced node z restores that subtree to the height it had before the insertion, so no ancestor of z sees any change. The upward walk still costs O(log n), because heights have to be updated.

Worked example — insert 10, 20, 30, 25, 28, 27:

Insert	What happens	Pre-order afterwards
10, 20	no rotation	10 20
30	bf(10) = −2, RR → left rotation at 10	20 10 30
25	no rotation	20 10 30 25
28	bf(30) = +2, its left child 25 has bf −1: LR at 30	20 10 28 25 30
27	bf(20) = −2, its right child 28 has bf +1: RL at 20	25 20 10 28 27 30

Here is the same example, drawn after every step. (These trees were produced by running the code above.)

Steps 1–3: insert 10, 20, 30. After 30, node 10 has bf = −2 and its right child 20 has bf = −1: case RR, one left rotation at 10.

insert 10, 20        insert 30               rotateLeft(10)

   10                 10  bf=−2                    20
     \                  \                         /  \
      20                 20  bf=−1              10    30
                           \
                            30

Step 4: insert 25. It goes 20 → right → 30 → left. Walk up: bf(30) = 0 − (−1) = +1, bf(20) = 0 − 1 = −1. Nobody tipped over, no rotation.

        20   bf=−1
       /  \
     10    30   bf=+1
          /
        25

Step 5: insert 28. It goes 20 → 30 → 25 → right. Walk up: bf(25) = −1, bf(30) = +2 — tipped over! The path from 30 goes left (to 25) then right (to 28): case LR at 30.

before                 rotateLeft(25)          rotateRight(30)

    20                      20                        20
   /  \                    /  \                      /  \
 10    30  bf=+2         10    30                  10    28
      /                       /                         /  \
    25     bf=−1            28                        25    30
      \                    /
       28                25

The median of 30, 25, 28 is 28, and 28 is the new root of that subtree. The subtree has height 1 again, as before the insertion, so 20 is still fine (bf = 0 − 1 = −1).

Step 6: insert 27. It goes 20 → 28 → 25 → right. Walk up: bf(25) = −1, bf(28) = 1 − 0 = +1, bf(20) = 0 − 2 = −2 — tipped over at the root. From 20 the path goes right (to 28) then left (to 25): case RL at 20.

before                    rotateRight(28)            rotateLeft(20)

    20  bf=−2                 20                           25
   /  \                      /  \                        /    \
 10    28  bf=+1           10    25                    20      28
      /  \                         \                  /       /  \
    25    30                        28              10      27    30
      \                            /  \
       27                        27    30

Final tree: pre-order 25 20 10 28 27 30, height 2, every bf in {−1, 0, +1}. Notice how 27 moved from 25's right child to 28's left child — that is the "T3 changes parent" step of the rotation.

Notice that at the last step the unbalanced node is the root 20, not the parent of 27: every node on the path must be checked.

Sorted input is no longer a problem. Inserting 1, 2, …, 7 into an AVL tree causes four RR rotations (at 1 after inserting 3, at 3 after 5, at the root 2 after 6, and at 5 after 7) and ends with the perfect tree 4(2(1, 3), 6(5, 7)) drawn at the start of the chapter — height 2 instead of 6.

Deletion in outline

In plain words: delete as in a normal BST, then walk up and fix every node that tipped over. The difference from insertion is that one repair may not be the end — removing a node can make a whole subtree shorter, and that can tip over a node higher up.

Deletion starts as BST deletion (a node with two children is replaced by its in-order successor or predecessor, which is then removed from the right or left subtree). Then walk back up and call the same rebalance at every node on the path. Two differences from insertion:

• The child on the heavy side may have bf = 0, which insertion never produces. Then a single rotation is correct (LL when bf(z) = +2 and bf(child) = 0), which is why the code above tests balance(n.left) < 0 rather than <= 0 for the double case.
• A rotation after deletion can make the subtree shorter than before, so the ancestor above may now be unbalanced too. Deletion can trigger rotations at O(log n) levels — still O(log n) work in total.

Worked example — delete 10 from the tree 20(10, 30(25, 40)):

before                after removing 10          rotateLeft(20)

     20                    20  bf = −1 − 1 = −2          30
    /  \                     \                          /  \
  10    30                    30  bf = 0              20    40
       /  \                  /  \                       \
     25    40              25    40                      25

Node 20 tipped to the right, and its right child 30 has bf = 0 — a case that insertion never produces. A single left rotation is enough: because bf(30) is 0 and not +1, this is treated as the RR case, and rebalance does not do a double rotation. Afterwards bf(20) = −1 and bf(30) = +1: valid AVL tree.

Why the height is O(log n)

In plain words: an AVL tree may lean a little at every node, but not a lot. Even the thinnest, most leaning AVL tree still has to contain a surprisingly large number of nodes for its height — the numbers grow like the Fibonacci numbers, which roughly multiply by 1.6 at every step. So the height can only grow logarithmically.

Ask the opposite question: what is the fewest nodes N(h) an AVL tree of height h can have? The thinnest tree has one subtree of height h − 1 and the other of height h − 2 (any shorter would break |bf| ≤ 1), each of them as thin as possible:

N(0) = 1,  N(1) = 2,  N(h) = 1 + N(h − 1) + N(h − 2)

h	0	1	2	3	4	5	6	7	8
N(h)	1	2	4	7	12	20	33	54	88

For example, N(3) = 1 + N(2) + N(1) = 1 + 4 + 2 = 7. The thinnest AVL tree of height 3 looks like this (every internal node leans left by exactly one):

            o            h=3
          /   \
         o     o         h=2 and h=1
        / \   /
       o   o o           h=1, h=0, h=0
      /
     o                   h=0

This is the Fibonacci recurrence plus one (in fact N(h) = F(h + 3) − 1), and Fibonacci numbers grow like φʰ with φ ≈ 1.618. So n ≥ N(h) ≈ φʰ, which gives h ≤ about 1.44 · log₂ n. These thinnest trees are called Fibonacci trees. For n = 1,000,000 the height is at most 27, against 19 for a perfectly balanced tree and 999,999 for the degenerate one.

AVL trees, plain BSTs and red-black trees

In plain words: a plain BST never balances (cheap updates, but it can become a chain). An AVL tree balances strictly (the shortest trees, so the fastest searches). A red-black tree balances loosely (slightly taller trees, but fewer rotations when you insert and delete). Java chose the loose version for TreeMap.

	Plain BST	AVL tree	Red-black tree
Worst-case height	n − 1	≈ 1.44 log₂ n	≈ 2 log₂ n
Search (worst case)	O(n)	O(log n)	O(log n)
Rotations per insert	0	≤ 1 (single or double)	≤ 2
Rotations per delete	0	up to O(log n)	≤ 3
Extra data per node	none	height (or bf)	one colour bit

A red-black tree colours each node red or black and keeps a looser rule (no red node has a red child; every root-to-null path has the same number of black nodes). Its trees are a little taller than AVL trees, but updates do fewer rotations. Java's TreeMap and TreeSet are red-black trees, which is why their put, get and remove are documented as guaranteed O(log n). AVL trees are a good choice when searches greatly outnumber updates.

Key takeaways

• BST operations cost O(h). Without balancing h can be n − 1 (sorted input); an AVL tree keeps h ≤ about 1.44 log₂ n.
• Height: empty = −1, leaf = 0. Balance factor = height(left) − height(right). AVL rule: |bf| ≤ 1 at every node.
• A rotation is O(1), keeps the in-order sequence, and moves exactly one subtree (T3) to a new parent. Update the lower node's height first.
• Straight cases (LL, RR) → one rotation against the heavy side. Zig-zag cases (LR, RL) → rotate the child first, then z. The median of the three keys ends on top.
• Insertion: rebalance at the lowest unbalanced ancestor on the way up; at most one single or double rotation.
• Deletion: may need rotations at several levels; a heavy child with bf = 0 is fixed by a single rotation.
• TreeMap/TreeSet use red-black trees: a looser balance rule, slightly taller, fewer rotations, still guaranteed O(log n).