AVL Trees and Self-Balancing: Fixing the Binary Search Tree's Worst Case

A binary search tree only gives you fast lookups while it stays short. Nothing in the plain insert algorithm makes it stay short. Feed it keys in ascending order — timestamps, auto-increment ids, a sorted export — and every new key lands to the right of the last one. The tree degenerates into a linked list with extra pointers, and the search that promised about 10 comparisons on 1,000 keys costs 1,000.

An AVL tree closes that hole. It is an ordinary binary search tree that stores one extra number per node — the height of the subtree that node roots — and enforces one rule after every insert and every delete: the two children of any node may differ in height by at most 1. When an operation breaks the rule, the tree repairs itself with a rotation, a local rewiring of three pointers that changes the shape without changing the sorted order of the keys.

That rule sounds far too weak to matter. It does not force anything like a perfect tree — every node is allowed to be one level lopsided, and lopsidedness compounds all the way down. It is still enough. What follows is the counting argument that pins the height at roughly 1.44 log₂ n, all four rotation cases with the pointer moves written out, and a full implementation of insert and delete — deletion included, because it is the part most write-ups quietly skip, and where the interesting behaviour lives.

The idea

A binary search tree keeps one invariant: for every node, all keys in its left subtree are smaller, and all keys in its right subtree are larger. That is what makes search work — compare, go left or right, repeat — and each comparison throws away one subtree. The cost of a search is therefore the number of nodes on the path you walk, which is bounded by the height of the tree, not by the number of keys in it.

Height here means the number of nodes on the longest root-to-leaf path: a single node has height 1, and the empty tree has height 0. A tree of height h holds at most 2^h − 1 keys, so h can never drop below log₂(n + 1). A perfectly balanced tree hits that floor. A degenerate tree — one long chain — has h = n, and every "search" is a linear scan.

The difference is not academic. Here are 1,000 keys inserted into a plain, unbalanced binary search tree, first in ascending order and then in an order chosen to build the tree perfectly:

class BSTNode:
    """A node of a plain binary search tree, with no balancing at all."""

    __slots__ = ("key", "left", "right")

    def __init__(self, key: int) -> None:
        self.key = key
        self.left: "BSTNode | None" = None
        self.right: "BSTNode | None" = None


def bst_insert(root: "BSTNode | None", key: int) -> BSTNode:
    """Insert without balancing.

    Written as a loop rather than a recursion because a degenerate tree gets
    deep enough to blow Python's recursion limit, which is itself the symptom.
    """
    if root is None:
        return BSTNode(key)
    node = root
    while True:
        if key < node.key:
            if node.left is None:
                node.left = BSTNode(key)
                return root
            node = node.left
        elif key > node.key:
            if node.right is None:
                node.right = BSTNode(key)
                return root
            node = node.right
        else:
            return root


def bst_height(root: "BSTNode | None") -> int:
    """Longest root-to-leaf path, counted in nodes, walked with a stack."""
    tallest = 0
    stack = [(root, 1)]
    while stack:
        node, depth = stack.pop()
        if node is None:
            continue
        tallest = max(tallest, depth)
        stack.append((node.left, depth + 1))
        stack.append((node.right, depth + 1))
    return tallest


def midpoint_order(low: int, high: int) -> list[int]:
    """The insertion order that happens to build a perfectly balanced tree."""
    if low > high:
        return []
    middle = (low + high) // 2
    return [middle] + midpoint_order(low, middle - 1) + midpoint_order(middle + 1, high)


ascending_tree = None
for number in range(1, 1001):
    ascending_tree = bst_insert(ascending_tree, number)

lucky_tree = None
for number in midpoint_order(1, 1000):
    lucky_tree = bst_insert(lucky_tree, number)

print("1000 keys, ascending order -> height", bst_height(ascending_tree))
print("1000 keys, midpoint order  -> height", bst_height(lucky_tree))

1000 keys, ascending order -> height 1000
1000 keys, midpoint order  -> height 10

Same keys, same code, a hundredfold difference in the cost of every future lookup — decided entirely by the order the data arrived in, which you do not control. And sorted input is not an unlucky edge case; it is the most common way real data arrives.

The AVL fix, published by Adelson-Velsky and Landis in 1962, is to notice the imbalance the moment it appears and undo it. Define the balance factor of a node as the height of its left subtree minus the height of its right subtree: a leaf is 0, a node with only a left child is +1. The AVL invariant is that every node's balance factor is one of -1, 0 or +1. A single insert or delete only changes heights along the one path it walked, so the damage is confined to that path — and a rotation repairs it.

Rotations: the only repair tool

A rotation takes a parent and one of its children, swaps their roles, and reattaches exactly one subtree in the process. It redistributes height and leaves the sorted order untouched, which is what makes it safe to apply at any moment.

Here is the right rotation in general form. z is the node whose balance factor has reached +2, y is its left child, and T1 to T4 are whatever subtrees hang below:

        z  (bf +2)                          y
       / \                                /   \
      y   T4       rotate right          x     z
     / \           ------------>        / \   / \
    x   T3            at z             T1 T2 T3 T4
   / \
  T1 T2

Read the in-order sequence off both pictures: T1 x T2 y T3 z T4, in both cases. Nothing has been reordered. The only pointer that had to find a new home is T3, which was the right child of y and becomes the left child of z — and it belongs there, because every key in T3 sits between y and z.

The rewiring is six steps, and only two of them write a child pointer:

1. pivot = z.left — grab y, the node being promoted.
2. orphan = pivot.right — grab T3 before you overwrite the pointer to it.
3. pivot.right = z — y adopts its old parent as its right child.
4. z.left = orphan — z takes T3 as its new left child.
5. Recompute z's cached height, then y's. Order matters: z is now below y, so y's height depends on the value you just wrote into z.
6. Return y so the caller can hang it where z used to be.

A left rotation is the same six steps with left and right swapped throughout.

Four situations can arise, distinguished by two signs: which way the unbalanced node leans, and which way its taller child leans.

Left-left: one right rotation

The unbalanced node is left-heavy and its left child is also left-heavy — the three nodes form a straight line leaning left. One right rotation at the top straightens it.

Insert 30, then 20, then 10. After 10 arrives, node 30 has a left subtree of height 2 and no right subtree, so its balance factor is +2. Rotating right at 30 promotes 20 to the root, with 10 and 30 as its children.

Right-right: one left rotation

The mirror image: the node is right-heavy and its right child is right-heavy.

Insert 10, then 20, then 30. Node 10 reaches balance factor -2, and one left rotation at 10 lifts 20 into its place.

Left-right: rotate the child left, then the node right

Now the awkward one. The node leans left but its left child leans right — the three nodes form a zig-zag, not a line. A single right rotation does not help here: it would just produce the mirror-image zig-zag and leave the tree exactly as unbalanced as before.

The fix is to straighten the zig-zag into a line first, with a left rotation on the child, and then apply the ordinary right rotation on top.

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

Insert 30, then 10, then 20. The left rotation at 10 gives the left-left chain 30 → 20 → 10, and the right rotation at 30 finishes the job. Two rotations, six pointer writes, still O(1).

Right-left: rotate the child right, then the node left

The mirror of left-right. The node leans right, its right child leans left. Rotate the child right to make a straight line, then rotate the node left.

Insert 10, then 30, then 20. All four cases end at the same place — 20 at the root with 10 and 30 below it — which is the point: the repair depends only on the local shape, never on how the tree got there.

That gives one compact rule. If a node's balance factor is +2, look at its left child: if that child leans right, rotate it left first; then rotate the node right. If the balance factor is -2, do the mirror. That is the entire rebalancing logic, for insert and delete alike.

Watching it work

Insert 10, 20, 30, 40, 50, 25 into an empty AVL tree, in that order. The first five are ascending, which is exactly the input that destroys a plain BST.

Insert 10, then 20. No rule broken yet. Node 10 has balance factor -1, which is legal.

10
  \
   20

Insert 30. It goes right of 20. Now node 10 has an empty left subtree and a right subtree of height 2, so its balance factor is -2. Its right child leans right, so this is right-right: one left rotation at 10.

   10  (bf -2)                20
     \        left at 10     /  \
      20      ---------->  10    30
        \
         30

Insert 40. It goes right of 30. Node 30 now has balance factor -1 and node 20 has balance factor -1. Both legal, no rotation.

Insert 50. It goes right of 40. Node 30 now has no left subtree and a right subtree of height 2 — balance factor -2, right-right again. A left rotation at 30 promotes 40:

    20                       20
   /  \                     /  \
  10    30  (bf -2)   ->  10    40
          \                    /  \
           40                30    50
             \
              50

Insert 25. This is the interesting one. 25 is greater than 20, so go right to 40; less than 40, so go left to 30; less than 30, so it becomes 30's left child. Walking back up: node 30 now has height 2 and balance factor +1 (legal), node 40 has a left subtree of height 2 and a right subtree of height 1, balance factor +1 (legal), and node 20 has a left subtree of height 1 and a right subtree of height 3 — balance factor -2. Broken, at the root.

Node 20 leans right, and its right child 40 leans left. Right-left. So rotate 40 right, then rotate 20 left:

    20                    20                      30
   /  \                  /  \                    /  \
  10    40   right     10    30     left       20    40
       /  \   at 40         /  \     at 20    /  \     \
     30    50   ---->     25    40   ---->  10    25    50
    /                             \
  25                               50

Six keys, height 3. A plain BST fed the same six keys would be the chain 10-20-30-40-50 with 25 hanging off 30 — height 5, and every lookup of 50 costing five comparisons instead of three.

The code

Start with the node and the two rotations. The height is stored on the node and updated in O(1); never recompute it by walking the subtree, or every insert turns into O(n) work.

class AVLNode:
    """A binary search tree node that caches the height of its own subtree."""

    __slots__ = ("key", "left", "right", "height")

    def __init__(self, key: int) -> None:
        self.key = key
        self.left: "AVLNode | None" = None
        self.right: "AVLNode | None" = None
        self.height = 1  # a node with no children is a subtree of height 1


def height(node: "AVLNode | None") -> int:
    """Cached height of a subtree. The empty tree has height 0."""
    return 0 if node is None else node.height


def balance_factor(node: "AVLNode | None") -> int:
    """Left height minus right height. Positive means left-heavy."""
    return 0 if node is None else height(node.left) - height(node.right)


def update_height(node: AVLNode) -> None:
    """Recompute one node's height from its children. O(1), no walking."""
    node.height = 1 + max(height(node.left), height(node.right))


def rotate_right(root: AVLNode) -> AVLNode:
    """Pull the left child up over its parent. Returns the new subtree root."""
    pivot = root.left
    orphan = pivot.right       # the only subtree that changes parent
    pivot.right = root
    root.left = orphan
    update_height(root)        # root now sits below pivot, so fix it first
    update_height(pivot)
    return pivot


def rotate_left(root: AVLNode) -> AVLNode:
    """Pull the right child up over its parent. The mirror of rotate_right."""
    pivot = root.right
    orphan = pivot.left
    pivot.left = root
    root.right = orphan
    update_height(root)
    update_height(pivot)
    return pivot


def in_order(node: "AVLNode | None", keys: "list[int] | None" = None) -> list[int]:
    """Every key in ascending order — the property a rotation must preserve.

    Appends into one shared list instead of concatenating a new list at every
    level, which is what keeps the whole walk O(n) rather than O(n log n).
    """
    if keys is None:
        keys = []
    if node is not None:
        in_order(node.left, keys)
        keys.append(node.key)
        in_order(node.right, keys)
    return keys


def render(node: "AVLNode | None", tag: str = "") -> list[str]:
    """Draw a subtree as text lines, showing each node's height and balance."""
    if node is None:
        return []
    lines = [f"{tag}{node.key}  h={node.height}  bf={balance_factor(node):+d}"]
    for child, side in ((node.left, "L"), (node.right, "R")):
        if child is None:
            continue
        block = render(child, f"{side}: ")
        for index, line in enumerate(block):
            lines.append(("+- " if index == 0 else "   ") + line)
    return lines


# Build the left-left shape 30 -> 20 -> 10 by hand.
skewed = AVLNode(30)
skewed.left = AVLNode(20)
skewed.left.left = AVLNode(10)
update_height(skewed.left)
update_height(skewed)

print("before, in order:", in_order(skewed))
print("\n".join(render(skewed)))

repaired = rotate_right(skewed)

print("after, in order: ", in_order(repaired))
print("\n".join(render(repaired)))

before, in order: [10, 20, 30]
30  h=3  bf=+2
+- L: 20  h=2  bf=+1
   +- L: 10  h=1  bf=+0
after, in order:  [10, 20, 30]
20  h=2  bf=+0
+- L: 10  h=1  bf=+0
+- R: 30  h=1  bf=+0

The in-order list is identical before and after. That is the guarantee every rotation must keep.

Now insert. The recursion does the bookkeeping for free: on the way down it finds the slot, and on the way back up every ancestor gets its height refreshed and its balance checked.

def rebalance(node: AVLNode) -> AVLNode:
    """Restore the invariant at one node whose children already satisfy it."""
    balance = balance_factor(node)

    if balance > 1:                            # left-heavy by two
        if balance_factor(node.left) < 0:      # left-right: straighten first
            node.left = rotate_left(node.left)
        return rotate_right(node)

    if balance < -1:                           # right-heavy by two
        if balance_factor(node.right) > 0:     # right-left: straighten first
            node.right = rotate_right(node.right)
        return rotate_left(node)

    return node


def insert(node: "AVLNode | None", key: int) -> AVLNode:
    """Insert a key, then fix heights and balance on the way back up.

    Duplicate keys are ignored, so the tree behaves as a set of keys.
    """
    if node is None:
        return AVLNode(key)

    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
    else:
        return node

    update_height(node)
    return rebalance(node)


def find(node: "AVLNode | None", key: int) -> bool:
    """Search is the plain BST search — balancing changes nothing here."""
    while node is not None:
        if key == node.key:
            return True
        node = node.left if key < node.key else node.right
    return False


tree = None
for key in [10, 20, 30, 40, 50, 25]:
    tree = insert(tree, key)
    print(f"insert {key}: root {tree.key}, height {tree.height}, keys {in_order(tree)}")

print()
print("\n".join(render(tree)))
print("find(25):", find(tree, 25), "  find(35):", find(tree, 35))

insert 10: root 10, height 1, keys [10]
insert 20: root 10, height 2, keys [10, 20]
insert 30: root 20, height 2, keys [10, 20, 30]
insert 40: root 20, height 3, keys [10, 20, 30, 40]
insert 50: root 20, height 3, keys [10, 20, 30, 40, 50]
insert 25: root 30, height 3, keys [10, 20, 25, 30, 40, 50]

30  h=3  bf=+0
+- L: 20  h=2  bf=+0
   +- L: 10  h=1  bf=+0
   +- R: 25  h=1  bf=+0
+- R: 40  h=2  bf=-1
   +- R: 50  h=1  bf=+0
find(25): True   find(35): False

Every root and height matches the hand trace above: the root moves from 10 to 20 when 30 arrives, and from 20 to 30 when 25 arrives.

Deletion is the same skeleton with a harder middle. Removing a node with two children means you cannot just unhook it, so you overwrite its key with the smallest key in its right subtree — the in-order successor, the very next key in sorted order — and then delete that node instead. The successor has no left child by construction, so the second deletion is the easy case.

def delete(node: "AVLNode | None", key: int) -> "AVLNode | None":
    """Remove a key, then fix heights and balance on the way back up."""
    if node is None:
        return None

    if key < node.key:
        node.left = delete(node.left, key)
    elif key > node.key:
        node.right = delete(node.right, key)
    else:
        # No child or one child: splice the node out and hand back the child.
        if node.left is None:
            return node.right
        if node.right is None:
            return node.left
        # Two children: copy the in-order successor's key up, then delete the
        # successor, which by definition has no left child.
        successor = node.right
        while successor.left is not None:
            successor = successor.left
        node.key = successor.key
        node.right = delete(node.right, successor.key)

    update_height(node)
    return rebalance(node)


for key in [25, 10, 20]:
    tree = delete(tree, key)
    print(f"delete {key}: root {tree.key}, height {tree.height}, keys {in_order(tree)}")

print()
print("\n".join(render(tree)))

delete 25: root 30, height 3, keys [10, 20, 30, 40, 50]
delete 10: root 30, height 3, keys [20, 30, 40, 50]
delete 20: root 40, height 2, keys [30, 40, 50]

40  h=2  bf=+0
+- L: 30  h=1  bf=+0
+- R: 50  h=1  bf=+0

Removing 25 and then 10 breaks nothing. Removing 20 leaves the root 30 with an empty left side and a right subtree of height 2 — balance factor -2, right-right — so a left rotation at 30 promotes 40. Note what triggered it: deleting on the left forced a rotation that lifted a node from the right. Deletions rebalance the side you did not touch, which is why they are easy to get wrong.

How the code maps to the idea

The recursion is the "walk back up". There are no parent pointers anywhere in this implementation. Each call returns the new root of the subtree it was given, and the caller writes it back with node.left = insert(node.left, key). Forget that assignment and the tree silently stops changing shape — rotations happen and are thrown away. This is the single most common AVL bug.

update_height before rebalance, always. rebalance reads balance factors, which read cached heights. If the node's own height still reflects the tree from before the insert, the check looks at stale data and misses the violation.

One rebalance covers all four cases. The outer test picks the direction from the node's own balance factor; the inner test picks single-versus-double from the child's. The inner comparison must be strict — balance_factor(node.left) < 0, not <= 0. After an insert, a node sitting at +2 always has a taller child at +1 or -1, because that child's height is what just grew, so the two spellings agree. After a delete the child can sit at 0, and there only the single rotation is correct: the double rotation's first step can leave the intermediate node two levels out of balance, and the tree that comes out is not an AVL tree. The single rotation also leaves the subtree at the height it already had, which stops the deletion cascade at that level.

Deletion's two-child case mutates a key, not a structure. Copying the successor's key into the node keeps every pointer valid and reduces the problem to deleting a node with at most one child. If your nodes carry values as well as keys, copy both.

Early returns skip the rebalance, correctly. When delete hits the zero-or-one-child case it returns the child directly without calling update_height or rebalance. That subtree was already a valid AVL tree, and its parent will fix its own height on the way back up.

Insert stops after one rotation; delete does not. After an insert, a single rebalance restores the subtree to exactly the height it had before the insert, so no ancestor's balance factor changes and the rest of the walk back up is pure bookkeeping. After a delete, the rebalanced subtree can end up one level shorter than it was, which is a fresh imbalance for the parent — so a single deletion can set off rotations at level after level on the way back to the root. The recursion handles that without any extra code, because it calls rebalance at every level anyway.

Search ignores all of it. find is the plain BST descent, unchanged. Balancing is entirely a write-time cost paid to make read time predictable.

Complexity

Everything rests on one claim: the invariant forces the height to stay logarithmic.

Ask the opposite question. Instead of "how tall can a tree with n keys get?", ask "what is the fewest keys a tree of height h can hold?" Call that number N(h). A tree of height 1 is a single node, so N(1) = 1. A tree of height 2 needs a root and one child, so N(2) = 2. For any taller h, take the root and hang the sparsest legal subtrees below it: one of height h − 1, because something has to reach that height, and — since the rule permits a difference of exactly 1 — one of height h − 2. That gives

N(h) = 1 + N(h - 1) + N(h - 2)

which is the Fibonacci recurrence with an extra 1. In fact N(h) = Fib(h + 2) − 1 exactly, and Fibonacci numbers grow geometrically, multiplying by the golden ratio φ = 1.618 each step. So N(h) grows like φ^h.

Turn that around. If n keys are in the tree then n ≥ N(h), so φ^h is at most about n, so h is at most log_φ(n) = log₂(n) / log₂(1.618) ≈ 1.44 log₂(n). An AVL tree is never more than about 44% taller than a perfect tree. Since search, insert and delete each walk one root-to-leaf path, all three are O(log n) in the worst case — not on average, not on random data, always.

The numbers are small enough to print:

from functools import lru_cache


@lru_cache(maxsize=None)
def minimum_nodes(h: int) -> int:
    """Fewest keys an AVL tree of height h can hold.

    One node at the top, plus the sparsest legal subtrees below it: one of
    height h - 1 and one of height h - 2, which is as lopsided as the rule allows.
    """
    if h <= 0:
        return 0
    if h == 1:
        return 1
    return 1 + minimum_nodes(h - 1) + minimum_nodes(h - 2)


def tallest_possible(n: int) -> int:
    """The tallest AVL tree that n keys could ever form."""
    h = 1
    while minimum_nodes(h + 1) <= n:
        h += 1
    return h


print("height:   ", " ".join(f"{h:>6}" for h in range(1, 11)))
print("min keys: ", " ".join(f"{minimum_nodes(h):>6}" for h in range(1, 11)))
print("tallest AVL tree holding     1,000 keys:", tallest_possible(1_000))
print("tallest AVL tree holding 1,000,000 keys:", tallest_possible(1_000_000))

balanced = None
for number in range(1, 1001):
    balanced = insert(balanced, number)
print("1000 ascending inserts into an AVL tree -> height", balanced.height)

height:         1      2      3      4      5      6      7      8      9     10
min keys:       1      2      4      7     12     20     33     54     88    143
tallest AVL tree holding     1,000 keys: 14
tallest AVL tree holding 1,000,000 keys: 28
1000 ascending inserts into an AVL tree -> height 10

A perfect tree over 1,000 keys has height 10; the worst legal AVL tree has height 14. Over a million keys it is 20 against 28. Both ratios are 1.4, exactly as the golden-ratio argument predicts. And the ascending insertion order that produced a 1,000-node chain in the plain BST produces a height-10 tree here — the best possible.

Now the write cost. A search is at most h comparisons. An insert walks down h levels and then, on the way back up, does O(1) work per level plus at most one rebalance. A delete does the same, except it may rotate at more than one level.

def scramble(n: int, step: int) -> list[int]:
    """A deterministic stand-in for a shuffle: 0..n-1 in a scattered order.

    Any step coprime with n visits every value exactly once, so this gives a
    reproducible "random-ish" insertion order with no seed to worry about.
    """
    return [(index * step) % n for index in range(n)]


def is_avl(node: "AVLNode | None") -> bool:
    """Check the invariant and the cached heights at every node."""
    if node is None:
        return True
    if node.height != 1 + max(height(node.left), height(node.right)):
        return False
    if abs(balance_factor(node)) > 1:
        return False
    return is_avl(node.left) and is_avl(node.right)


rotations = 0
plain_rotate_left, plain_rotate_right = rotate_left, rotate_right


def rotate_left(root: AVLNode) -> AVLNode:      # rebinding on purpose
    """The real rotate_left, wrapped so every rotation is counted."""
    global rotations
    rotations += 1
    return plain_rotate_left(root)


def rotate_right(root: AVLNode) -> AVLNode:     # rebinding on purpose
    """The real rotate_right, wrapped so every rotation is counted."""
    global rotations
    rotations += 1
    return plain_rotate_right(root)


def build_minimal(h: int, next_key: int) -> tuple["AVLNode | None", int]:
    """Build the sparsest legal AVL tree of height h, keyed in ascending order."""
    if h <= 0:
        return None, next_key
    left, next_key = build_minimal(h - 1, next_key)
    node = AVLNode(next_key)
    right, next_key = build_minimal(h - 2, next_key + 1)
    node.left, node.right = left, right
    update_height(node)
    return node, next_key


rotations, worst_insert = 0, 0
growing = None
for number in range(1, 1001):
    before = rotations
    growing = insert(growing, number)
    worst_insert = max(worst_insert, rotations - before)
print(f"1000 ascending inserts: {rotations} rotations, worst single insert {worst_insert}")

rotations, worst_insert = 0, 0
growing = None
for number in scramble(1000, 617):
    before = rotations
    growing = insert(growing, number)
    worst_insert = max(worst_insert, rotations - before)
print(f"1000 scattered inserts: {rotations} rotations, worst single insert {worst_insert}")

size = minimum_nodes(9)
worst_delete, worst_key = 0, 0
for key in range(1, size + 1):
    sparse, _ = build_minimal(9, 1)
    rotations = 0
    sparse = delete(sparse, key)
    if rotations > worst_delete:
        worst_delete, worst_key = rotations, key
print(f"sparsest height-9 tree ({size} keys): worst delete costs {worst_delete} rotations (key {worst_key})")

healthy = True
for build_step, empty_step in [(1, 499), (617, 33), (291, 7)]:
    root = None
    for key in scramble(500, build_step):
        root = insert(root, key)
        healthy = healthy and is_avl(root)
    for key in scramble(500, empty_step):
        root = delete(root, key)
        healthy = healthy and is_avl(root)
    healthy = healthy and root is None
print("every tree along 3 build-and-empty cycles of 500 keys is a valid AVL tree:", healthy)

1000 ascending inserts: 990 rotations, worst single insert 1
1000 scattered inserts: 749 rotations, worst single insert 2
sparsest height-9 tree (88 keys): worst delete costs 4 rotations (key 87)
every tree along 3 build-and-empty cycles of 500 keys is a valid AVL tree: True

Those four lines are the write cost measured rather than asserted. Sorted input keeps the tree busy — 990 rotations for 1,000 keys, near enough one per insert — and scattered input needs fewer, 749. But no single insert ever costs more than 2 rotations, 1 for the straight-line cases and 2 for the zig-zags, no matter how many keys the tree holds. That is the "one rebalance restores the original subtree height" argument in action.

Deletion is the exception. On the sparsest legal height-9 tree, removing one particular key sets off 4 rotations — one at every level of the path back to the root, not one here and there along it. The count is 4 rather than 9 because that tree's shortest root-to-leaf path holds only about half as many nodes as its height, and that is the path this deletion walked. So a deletion can cost O(log n) rotations where an insertion costs O(1) — though each rotation is O(1) work and there are at most as many as there are levels, so the operation as a whole is still O(log n).

Space is O(n): one node per key, each holding a key, two pointers and one integer height. The recursion adds O(log n) stack frames, bounded by the height — which is exactly why a recursive implementation is safe here and was not safe for the degenerate BST at the top of this post. Listing every key in order is O(n), an in-order traversal that visits each node once; finding the minimum or maximum is O(log n), a walk down the left or right spine.

When to use it, and when not to

Reach for a balanced tree when you need ordered operations with a worst-case guarantee: keys in sorted order on demand, "the smallest key above x", range queries, a rank that keeps updating. A hash table cannot do any of those — it gives you exact-match lookup that is O(1) on average but O(n) in the worst case, when every key lands in one bucket, and no order at all. If you only ever look keys up by exact value, use a hash table and stop reading here.

Do not use one when the data is static. If you build the index once and then only query it, sort the keys into a plain list and use binary search: same O(log n) lookup, a fraction of the memory, no pointer chasing, and it iterates in order for free.

And in Python specifically, do not write this class in production code. CPython's standard library ships no balanced tree, and a Python-level AVL tree loses badly to the C-level alternatives:

import bisect

keys: list[int] = []
for key in [10, 20, 30, 40, 50, 25]:
    bisect.insort(keys, key)

low = bisect.bisect_left(keys, 20)
high = bisect.bisect_right(keys, 40)
print(keys)
print("position of 30:", bisect.bisect_left(keys, 30))
print("keys from 20 to 40:", keys[low:high])

[10, 20, 25, 30, 40, 50]
position of 30: 3
keys from 20 to 40: [20, 25, 30, 40]

bisect.insort finds the position in O(log n) comparisons and then shifts the tail of the list, which is O(n) — but that shift is a single memmove of contiguous pointers inside CPython, and it comfortably beats an interpreted tree walk up to the tens of thousands of elements. Above that, the usual answer is the sortedcontainers package, whose SortedList is not a tree at all: it keeps a list of short lists, so every operation reduces to bisect plus a small slice, both running in C. If you only need the smallest item rather than full ordering, use heapq instead.

So learn AVL trees for the mechanism, and write one when you are the one implementing the container — in C, or in an embedded system that cannot carry a general-purpose library. Everywhere else, use the ordered container your language already ships: std::map in C++, TreeMap in Java, BTreeMap in Rust.

Where it shows up in the real world

Red-black trees, not AVL trees, won the standard libraries. A red-black tree enforces a weaker rule — the longest root-to-leaf path is at most twice the shortest — so it is taller than an AVL tree (up to 2 log₂ n against 1.44 log₂ n) and its lookups are correspondingly a little slower. In exchange it needs at most 2 rotations for an insert and at most 3 for a delete, ever, doing the rest of its repair work by recolouring nodes. That trade — slightly worse reads, bounded and cheaper writes — is what most general-purpose containers want:

• C++: std::map and std::set are required to give ordered iteration and logarithmic operations; libstdc++, libc++ and MSVC all implement them as red-black trees.
• Java: TreeMap and TreeSet are documented as red-black trees, and since Java 8 HashMap turns a bucket into a red-black tree once it holds too many colliding keys.
• The Linux kernel: lib/rbtree.c shows up all over the tree, most famously in the process scheduler — CFS held every runnable task in a red-black tree ordered by virtual runtime, so choosing the next task meant taking the leftmost node. epoll keeps its set of watched file descriptors in one too.

B-trees own the disk. Once the data stops fitting in memory the cost model changes: what matters is the number of blocks read, not the number of comparisons made. A B-tree node is sized to a disk page — 8 KB in PostgreSQL — and holds hundreds of keys, so a tree over a billion rows is three or four levels deep instead of forty-odd. PostgreSQL's default index is a B-tree, SQLite stores every table and index as a B-tree, MySQL's InnoDB clusters rows in a B+ tree keyed by the primary key, and btrfs and XFS are built on B-trees on the filesystem side.

AVL trees themselves survive where lookups dominate updates and the tightest possible height is worth the extra rotations. The Windows kernel stores each process's virtual address descriptors — the map of which address ranges are reserved — in an AVL tree, read on every page fault and updated comparatively rarely. They also remain the standard teaching example, and what an interviewer usually means by "balanced tree".

Not everyone picks a tree at all: Redis implements sorted sets with a skip list plus a hash table, because a skip list answers range queries as well as a balanced tree does while being markedly simpler to implement and debug.

Common mistakes

Not reassigning the result. insert(node.left, key) on its own compiles, runs, and silently discards every rotation. It must be node.left = insert(node.left, key), and the top-level call must be tree = insert(tree, key).

Recomputing height instead of caching it. Writing height(node) as a recursive walk of the subtree costs one visit per node below it. Insert calls it at every level, so the total for one insert is n + n/2 + n/4 + … = O(n), and the whole point of the structure is gone. Store the height on the node and update it in O(1).

Updating heights in the wrong order inside a rotation. In rotate_right you must update the demoted node first and the promoted node second. Do it the other way around and the promoted node's height is computed from a stale value, and the corruption spreads with every future operation.

Stopping after the first rotation in delete. Insert may stop after one rebalance; delete may not. If you write delete iteratively and break out of the loop once you have fixed a node, you will produce trees that violate the invariant several levels up. The recursive version avoids this by construction.

Getting the double-rotation test backwards. For a left-heavy node you inspect the left child, and you rotate that child left before rotating the parent right. Mixing up either direction turns a zig-zag into a mirror-image zig-zag and the tree stays unbalanced — the code will not crash, it will just quietly stop being an AVL tree.

Deleting the successor by walking instead of recursing. After copying the successor's key up, delete it with a recursive call into the right subtree so that every node on the path back gets its height and balance fixed. Unhooking the successor node directly leaves stale heights along that path.

Practice

1. Add a size field to each node, maintained through inserts, deletes and rotations, and use it to answer "what is the k-th smallest key?" in O(log n).
2. Write range_keys(node, low, high) that returns every key in a range, skipping any subtree whose whole key span falls outside it.
3. Implement delete iteratively with an explicit stack of the nodes on the path, and rebalance by popping that stack — then check it against is_avl on a few thousand random operations.
4. Relax the invariant to allow a balance factor of ±2 before rotating. Measure how much taller the tree gets over 100,000 inserts and how many rotations you save.
5. Build the sparsest AVL tree of height 12 with build_minimal, then find every key whose deletion causes the most rotations, and explain what those keys have in common.

Summary

An AVL tree is a binary search tree that refuses to get tall. One number per node, one invariant — no node's children may differ in height by more than 1 — and four rotation cases are enough to guarantee O(log n) search, insert and delete on any input, including the sorted input that reduces a plain BST to a linked list. The proof is the minimum-nodes recurrence: a tree of height h needs at least Fib(h + 2) − 1 keys, Fibonacci grows like 1.618^h, and therefore h stays under about 1.44 log₂ n.

Learn the rotations until you can draw all four from memory, because every self-balancing structure you meet later — red-black trees, B-trees, splay trees — is the same idea with a different rule about when to apply them.

Keep reading

• Binary Search Trees — the unbalanced version this post repairs, including traversals and deletion in full.
• Hash Tables — the O(1) alternative, and exactly which queries it cannot answer.
• Heaps and Priority Queues — a different tree-shaped invariant, kept in a flat list with no pointers at all.
• Binary Search — the same halving argument on a sorted array, and the right answer when the data does not change.
• Big O Notation — where log n comes from, and why 1.44 log₂ n and log₂ n are the same O.