AVL Tree, in depth: the balance invariant, the Fibonacci height bound, four rotation cases, deletion and a tested implementation

The invariant

In a binary search tree, smaller keys go left and larger keys go right, and search costs the tree's height. Insert sorted keys and the height becomes n: a linked list. A balanced tree adds a rule that prevents this.

AVL uses the strictest rule that is still cheap to maintain. Define the height of an empty tree as 0 and of a leaf as 1. For each node, define the balance factor as height(left) - height(right). The AVL invariant says every balance factor is -1, 0 or +1. Nothing else is required: the tree need not be complete, and leaves need not sit at the same depth.

Each node stores its height in a small integer. Storing only a two-bit balance factor saves memory but makes every update reason about how child heights changed, which is where most AVL bugs live.

Why the height is logarithmic

Why does a difference of one per node bound the height of the whole tree? Ask the reverse question: what is the fewest nodes an AVL tree of height h can have? Call that N(h). A sparsest tree of height h has a root, one subtree of height h-1, and, to use as few nodes as possible, a second subtree that is as short as the rule allows: h-2. Both subtrees must themselves be sparsest, so

N(1) = 1,  N(2) = 2,  N(h) = N(h-1) + N(h-2) + 1
N(h) = F(h+2) - 1      # F is the Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13 ...

Fibonacci numbers grow as phi^h with phi about 1.618, so the node count grows exponentially in the height. Turned around, the height grows logarithmically in the node count. The standard bound is h < 1.4405 * log2(n + 2) - 0.3277.

Put numbers on it. With a million keys, a perfectly balanced tree has height 20. An AVL tree has height at most 28. A red-black tree guarantees only 2 * log2(n + 1), which is 39. These are worst cases. Random inserts usually give AVL heights close to the optimum. But the bound is what a latency budget can rely on, and AVL's is the tightest of the common balanced trees. The sparsest shapes are called Fibonacci trees, and they make good test inputs.

Rotations and the four cases

A rotation swaps a parent and a child while keeping in-order key order. A right rotation at y lifts its left child x: x's right subtree becomes y's new left subtree, and y becomes x's right child. It changes three pointers and two stored heights. A left rotation is the mirror image. Because it only touches a constant number of nodes, a rotation costs O(1).

After an update, a node can have balance factor +2 or -2. Which repair to use depends on which side is heavy and which way the heavy child leans:

A single rotation cannot fix extra height in the inner grandchild: it moves that subtree across at the same depth and leaves the imbalance mirrored. The first rotation of the pair turns the inner case into an outer one, and the second fixes it.

Note the 0 entries. After an insertion the heavy child is never balanced, because the new key made it taller on one side. After a deletion it can be, and then a single rotation is the correct fix.

Insertion: at most one repair

Insertion first runs a normal BST insert, which adds a new leaf. Then it walks back up the search path, recomputing heights and balance factors. On the way up, one of three things happens at each node:

1. The node's height does not change. The walk can stop, because nothing above it can be affected.
2. Its height grows by one and the node is still within the rule. Keep walking up.
3. Its balance factor reaches +2 or -2. Apply the matching rotation.

The key fact is that the rotation in case 3 returns the subtree to exactly the height it had before the insert. So the walk ends there: an insertion does at most one single or double rotation. It still does O(log n) work, from the search and from checking heights on the way up, but it changes the shape in only one place.

Deletion: repairs can cascade

Deletion starts as a BST delete. A node with at most one child is spliced out. A node with two children takes its in-order successor, the minimum of its right subtree, and that successor is removed from where it was. Either way, a subtree on some path has lost one level of height.

The walk back up is like the one for insertion, with one difference. A rotation after a delete does not always restore the subtree's old height. In the left-left and right-right cases with a heavy child of balance 0, it does, and the walk can stop. In every other case the rotated subtree ends up one level shorter than before, and that can unbalance the parent. So a deletion can need a rotation at every level, which is O(log n) rotations in the worst case. Fibonacci trees reach that worst case.

This is AVL's weak spot next to red-black trees, which rotate a constant number of times per update. Most deletes rotate once or not at all, so measure before assuming it matters.

An implementation

Each function returns the new root of its subtree so the parent can re-link it, which avoids parent pointers. Recursion depth is the height, at most 28 for a million keys.

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

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

def rot_right(y):
    x = y.left
    y.left, x.right = x.right, y
    fix(y); fix(x)              # child first: x's height depends on y's
    return x

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

def rebalance(n):
    fix(n)
    b = bf(n)
    if b > 1:
        if bf(n.left) < 0:      # left-right; strictly less, so bf 0 gets a single rotation
            n.left = rot_left(n.left)
        return rot_right(n)
    if b < -1:
        if bf(n.right) > 0:     # right-left
            n.right = rot_right(n.right)
        return rot_left(n)
    return n

def insert(n, key, val):
    if n is None:
        return Node(key, val)
    if key < n.key:   n.left = insert(n.left, key, val)
    elif key > n.key: n.right = insert(n.right, key, val)
    else:             n.val = val; return n
    return rebalance(n)

def pop_min(n):
    """Detach the minimum node of subtree n. Returns (new subtree root, detached node)."""
    if n.left is None:
        return n.right, n
    n.left, m = pop_min(n.left)
    return rebalance(n), m

def delete(n, key):
    if n is None:
        return None
    if key < n.key:   n.left = delete(n.left, key)
    elif key > n.key: n.right = delete(n.right, key)
    else:
        if n.left is None:  return n.right
        if n.right is None: return n.left
        rest, s = pop_min(n.right)
        s.left, s.right = n.left, rest
        n = s
    return rebalance(n)

This version calls rebalance at every level instead of stopping early; the result is the same and the code stays short. Store a subtree size and update it in fix to get rank and k-th smallest queries in O(log n). Rotations keep any augmented field correct as long as fix recomputes it from the children.

Worked example

Insert 10, 20, 30, 40, 50 and 25 into an empty tree, in that order.

1. 10, then 20: the tree is 10 with right child 20. The root's balance factor is -1, which is legal.
2. 30: the root 10 reaches -2 and its right child 20 has -1. This is the right-right case, so rotate left at 10. Now 20 is the root, with children 10 and 30.
3. 40: it goes under 30 on the right. Balance factors are 30 at -1 and 20 at -1, so nothing rotates.
4. 50: it goes under 40. Node 30 reaches -2 and its child 40 has -1, another right-right case, so rotate left at 30. The tree is now 20 over 10 and 40, with 40 over 30 and 50.
5. 25: the path is 20, then 40, then 30, then left. Node 30 now has +1 and node 40 has +1, so the left side is heavier. At the root, the left subtree has height 1 and the right has height 3, giving -2. The root leans right but its heavy child leans left, which is the right-left case.

After the double rotation, 30 is the root, 20 has children 10 and 25, and 40 has only a right child, 50. Every balance factor is 0 or -1, and the height is 3, the minimum for six keys. A plain BST would have built a chain of height 5 from the first five keys.

Testing it properly

An AVL implementation is easy to get almost right. Test it with an invariant checker and a randomised comparison against a trusted map, not with a few hand-picked cases:

import random

def check(n, lo=None, hi=None):
    """Return the true height of subtree n; assert order, stored height and balance."""
    if n is None:
        return 0
    assert (lo is None or lo < n.key) and (hi is None or n.key < hi), "BST order"
    hl, hr = check(n.left, lo, n.key), check(n.right, n.key, hi)
    assert n.h == 1 + max(hl, hr), "stale height"
    assert abs(hl - hr) <= 1, "AVL balance"
    return n.h

root, model = None, {}
for step in range(200_000):
    k = random.randrange(5_000)
    if random.random() < 0.55:
        root = insert(root, k, step); model[k] = step
    else:
        root = delete(root, k); model.pop(k, None)
    if step % 997 == 0:
        check(root)
check(root)

Keep the key range small so deletes hit existing keys, and add sorted, reverse-sorted and Fibonacci-tree runs.

AVL versus red-black and the alternatives

AVL favours reads and red-black favours writes, but the gap is small. Java's TreeMap and the Linux kernel's rbtree chose red-black for steady write cost and one colour bit. For a read-mostly in-memory index with a tail-latency budget, AVL's tighter bound is real. For data on disk, use a B-tree instead: it packs hundreds of keys per node, so a lookup touches a few pages, not 20 scattered cache lines.

Failure modes

• Stale heights after a rotation. The demoted node has to be fixed before the promoted node, because the promoted node's height is computed from it. Fix them the other way round and the tree looks fine until a later update reads the wrong height.
• Double rotation when the heavy child is balanced. Testing bf(child) <= 0 instead of < 0 sends the balanced case on a delete into a double rotation, which can leave a node at +2. Only the randomised delete test catches this one.
• Forgetting to re-link the returned root. Every function returns a possibly new subtree root. Dropping the return value of insert or delete at the top level silently loses nodes.
• Comparators that are not total orders. A floating-point NaN key compares false to everything, so it breaks the search invariant without an error. Reject such keys or map them to a defined position.
• Sharing one tree across threads. Readers can see a half-rotated tree. Use a lock, a copy-on-write tree, or a concurrent skip list.

What to do next

1. Type in the implementation above, insert 10, 20, 30, 40, 50 and 25, and assert that the root key is 30.
2. Run the randomised test with the checker, then break rebalance on purpose by changing < 0 to <= 0, and confirm the test fails.
3. Add a size field, maintain it in fix, and implement select(k) and rank(key).
4. Count rotations per operation on random, sorted and Fibonacci-tree inputs, and compare those counts with your language's built-in ordered map.
5. Read the red-black tree deep dive and write down which of your workloads favours each structure.
6. Revisit the plain BST operations and the balanced-tree check, then compare with randomised balancing in treaps and disk-oriented balancing in B-tree indexes.