AVL trees

What this chapter covers

Last chapter ended on a cliffhanger: a binary search tree is a wonderful ordered container until sorted input degenerates it into a linked list, at which point every operation is O(n). The AVL tree is the fix, and it's the first self-balancing search tree ever invented. It's an ordinary BST plus one rule: after every insert, check whether any node has become too lopsided, and if so, restore balance with a rotation — a constant-time rearrangement of a handful of pointers. That single discipline guarantees the height stays O(log n) for any insertion order, turning the fragile BST into one you can actually deploy. This chapter builds it, watches it rebalance sorted input in real time, and measures the 100×-plus difference balance makes.

A bit of history

The AVL tree is named for its inventors, the Soviet mathematicians Georgy Adelson-Velsky and Evgenii Landis, who published it in 1962 — the initials A-V-L are theirs. It was the first data structure to guarantee logarithmic height for a dynamic search tree, and it appeared almost immediately after the binary search tree itself, because the balance problem was obvious the moment people started inserting sorted data. Their key idea — keep a height-balance invariant at every node and repair it with local rotations — founded an entire family of balanced trees, including the red-black tree of the next chapter and the B-tree that indexes databases. Sixty years on, "balance factor" and "rotation" are still the vocabulary, and the AVL tree is still taught first, because its balance rule is the strictest and clearest of the family.

The intuition

Every AVL node remembers the height of its subtree, and from that you compute its balance factor: the height of its left subtree minus its right. In a balanced tree that difference is always -1, 0, or +1. The moment an insertion makes some node's balance factor +2 or -2 — one side two levels taller than the other — the tree fixes it before returning.

The fix is a rotation. Picture a node that's become left-heavy because you kept inserting smaller values. A right rotation lifts its left child up to take its place and pushes the node down to become that child's right child — the tree leans the other way, the two sides even out, and, because a left child is always smaller and a right child always larger, the search ordering is completely preserved. Only three pointers move, so a rotation is O(1). There are four cases in total: the simple left-heavy and right-heavy ones need a single rotation, and two "zig-zag" cases (left-heavy but the imbalance is in the left child's right subtree, and its mirror) need a double rotation — rotate the child first to turn it into a simple case, then rotate the node. Insert, then walk back up rotating wherever needed, and the height can never exceed about 1.44·log₂ n.

Complexity: how it scales

Because the balance invariant caps the height at $O(\log n)$ — precisely, at most about $1.44\log_2 n$ — every operation that's O(height) becomes O(log n) guaranteed, not just on average. Search, insert, delete: all $O(\log n)$, worst case, for any input. Insert and delete add only O(log n) of rebalancing work on top of the search, since each does at most a constant amount of rotation per level on the way back up. The two charts tell the story against the unbalanced BST from last chapter, both fed sorted input. The timing:

And the height that causes it — the AVL line barely rises while the plain BST's climbs linearly, because sorted input builds it as a straight chain:

At 8000 sorted insertions the AVL tree built in 20 ms against the plain BST's 2130 ms — 104 times faster. And at 100000 nodes, the AVL tree's height was 17 (right at log₂ n ≈ 16.6) while the plain BST's was 100000: a straight line of a hundred thousand nodes versus a bushy tree seventeen levels deep. That's the difference balance makes.

What it's good at, what it isn't

The AVL tree is the right structure when you need an ordered container with guaranteed logarithmic operations — sorted iteration, ranges, min, max, successor — and you can't rule out sorted or adversarial input (which you usually can't). It's the BST made safe: all the ordered-query power of last chapter, with the degeneration removed. Its strict balance also means it's slightly shorter than looser balanced trees, so lookups are a touch faster, which makes it a good fit for read-heavy workloads.

Its cost is the flip side of that strictness. Because it insists on the ±1 balance factor, it rotates more often on inserts and deletes than a red-black tree does — the red-black tree (next chapter) accepts a looser balance to rebalance less, trading a slightly taller tree for cheaper updates. So for update-heavy workloads, red-black trees often win, which is why they, not AVL trees, are what most standard libraries use for their ordered maps. AVL is the purest and most rigidly balanced of the family; red-black is the pragmatic compromise. Both beat an unbalanced BST by the margins above.

The data, or the inputs

The face-off and height charts both feed sorted input — 0, 1, 2, … — because that's the worst case that destroys a plain BST and the clearest demonstration that AVL survives it. The animation inserts the seven values 1 through 7 in order, the same sorted sequence, so you can watch the tree rotate itself flat instead of growing into a chain.

Build it, one function at a time

The two rotations are the mechanism — each moves three pointers and recomputes two heights, preserving the ordering:

def _rotate_right(y):
    """Right rotation: y's left child x rises to the top of this subtree and y sinks
    to become x's right child; x's old right subtree reattaches under y. Only three
    pointers move, heights are recomputed, and — crucially — the BST ordering is
    unchanged, because everything stays on its correct side of every value."""
    x = y.left
    y.left = x.right
    x.right = y
    _update(y)
    _update(x)
    return x


def _rotate_left(x):
    """Left rotation — the exact mirror image, for a right-heavy subtree."""
    y = x.right
    x.right = y.left
    y.left = x
    _update(x)
    _update(y)
    return y

Insert is a normal BST insert with one addition: on the way back up the recursion, update heights and rebalance:

def insert(self, value, rot=None):
    """O(log n) GUARANTEED: insert like a normal BST, then on the way back up
    update heights and rebalance. Because the recursion returns through every
    ancestor, each one is checked and fixed, and at most one rotation (or double
    rotation) is ever needed to restore balance after an insert."""
    self.root = self._insert(self.root, value, rot)

def _insert(self, node, value, rot):
    if node is None:
        self._n += 1
        return Node(value)
    if value < node.value:
        node.left = self._insert(node.left, value, rot)
    elif value > node.value:
        node.right = self._insert(node.right, value, rot)
    else:
        return node
    _update(node)
    return self._rebalance(node, rot)

And rebalancing is the four-case decision — single rotation for the simple cases, double for the zig-zags:

def _rebalance(self, node, rot):
    """The four cases. If the node is left-heavy and its left child is right-heavy,
    that's the left-right case: rotate the child left first, turning it into the
    simple left-left case, then rotate the node right. Right-heavy is the mirror.
    A single or double rotation always suffices."""
    bf = _balance(node)
    if bf > 1:                          # left-heavy
        if _balance(node.left) < 0:     # left-right → reduce to left-left
            node.left = _rotate_left(node.left)
        if rot is not None:
            rot.append(node.value)
        return _rotate_right(node)
    if bf < -1:                         # right-heavy
        if _balance(node.right) > 0:    # right-left → reduce to right-right
            node.right = _rotate_right(node.right)
        if rot is not None:
            rot.append(node.value)
        return _rotate_left(node)
    return node

Watch it work

Here's the AVL tree fed the exact input that destroyed the plain BST last chapter: 1, 2, 3, 4, 5, 6, 7 in sorted order. Green is a freshly inserted node; orange marks a node where a rotation just fired to restore balance. Step through it and watch what happens where the plain BST grew a chain: insert 1, 2 — fine; insert 3 and the tree tips right, so it rotates and 2 becomes the root; keep going and every couple of inserts triggers another rotation that folds the growing chain back into a balanced shape. Seven sorted insertions that would have built a height-7 linked list instead produce a perfectly balanced tree of height 3:

The complete code

Both versions in one place — flip between them. The from-scratch tab is the AVL tree, its rotations, and its rebalancing. The library tab is the plain unbalanced BST from last chapter — the same insert minus the rotations — kept as the baseline, so you can see that the only difference between a structure that degrades to O(n) and one that guarantees O(log n) is those few lines of rebalancing. (The real library counterpart is the third-party sortedcontainers.)

"""The AVL tree — a binary search tree that keeps itself balanced, so its height stays
O(log n) no matter the insertion order, and every operation is guaranteed O(log n).

It's an ordinary BST plus one discipline: after every insert, walk back up to the root
and, wherever a node has become too lopsided (its two subtrees differ in height by more
than one), fix it with a ROTATION — a local rearrangement of a few pointers that
rebalances the subtree while preserving the search-tree ordering. That's the whole idea,
and it's what turns the previous chapter's fragile BST into one you can actually ship.
"""


class Node:
    __slots__ = ("value", "left", "right", "height")

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 1


def _h(node):
    return node.height if node else 0


def _balance(node):
    """The balance factor: height of the left subtree minus the right. An AVL tree
    keeps this in {-1, 0, +1} at every node; anything beyond means rebalance."""
    return _h(node.left) - _h(node.right) if node else 0


def _update(node):
    node.height = 1 + max(_h(node.left), _h(node.right))


# region: rotations
def _rotate_right(y):
    """Right rotation: y's left child x rises to the top of this subtree and y sinks
    to become x's right child; x's old right subtree reattaches under y. Only three
    pointers move, heights are recomputed, and — crucially — the BST ordering is
    unchanged, because everything stays on its correct side of every value."""
    x = y.left
    y.left = x.right
    x.right = y
    _update(y)
    _update(x)
    return x


def _rotate_left(x):
    """Left rotation — the exact mirror image, for a right-heavy subtree."""
    y = x.right
    x.right = y.left
    y.left = x
    _update(x)
    _update(y)
    return y
# endregion


class AVLTree:
    def __init__(self):
        self.root = None
        self._n = 0

    # region: insert
    def insert(self, value, rot=None):
        """O(log n) GUARANTEED: insert like a normal BST, then on the way back up
        update heights and rebalance. Because the recursion returns through every
        ancestor, each one is checked and fixed, and at most one rotation (or double
        rotation) is ever needed to restore balance after an insert."""
        self.root = self._insert(self.root, value, rot)

    def _insert(self, node, value, rot):
        if node is None:
            self._n += 1
            return Node(value)
        if value < node.value:
            node.left = self._insert(node.left, value, rot)
        elif value > node.value:
            node.right = self._insert(node.right, value, rot)
        else:
            return node
        _update(node)
        return self._rebalance(node, rot)
    # endregion

    # region: rebalance
    def _rebalance(self, node, rot):
        """The four cases. If the node is left-heavy and its left child is right-heavy,
        that's the left-right case: rotate the child left first, turning it into the
        simple left-left case, then rotate the node right. Right-heavy is the mirror.
        A single or double rotation always suffices."""
        bf = _balance(node)
        if bf > 1:                          # left-heavy
            if _balance(node.left) < 0:     # left-right → reduce to left-left
                node.left = _rotate_left(node.left)
            if rot is not None:
                rot.append(node.value)
            return _rotate_right(node)
        if bf < -1:                         # right-heavy
            if _balance(node.right) > 0:    # right-left → reduce to right-right
                node.right = _rotate_right(node.right)
            if rot is not None:
                rot.append(node.value)
            return _rotate_left(node)
        return node
    # endregion

    def __contains__(self, value):
        node = self.root
        while node is not None:
            if value == node.value:
                return True
            node = node.left if value < node.value else node.right
        return False

    def __len__(self):
        return self._n

    def height(self):
        return _h(self.root)

    def inorder(self):
        out = []

        def rec(node):
            if node is not None:
                rec(node.left)
                out.append(node.value)
                rec(node.right)

        rec(self.root)
        return out

"""Python's standard library has no balanced BST; the third-party
`sortedcontainers.SortedList` is what you'd use in practice (it's actually a list of
lists, not a tree, but offers the same O(log n) ordered operations). So the meaningful
comparison here is against the structure AVL improves on — last chapter's UNBALANCED
BST — to show that self-balancing turns the sorted-input catastrophe back into O(log n).

That plain BST is included below as the reference baseline.
"""


# region: plain_bst
class PlainBSTNode:
    __slots__ = ("value", "left", "right")

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class PlainBST:
    """An ordinary binary search tree with NO balancing — the same insert as the AVL
    tree, minus the rotations. On sorted input it degenerates into a linked list, which
    is exactly the O(n)-per-operation disaster the AVL tree's rotations prevent."""

    def __init__(self):
        self.root = None

    def insert(self, value):
        self.root = self._insert(self.root, value)

    def _insert(self, node, value):
        if node is None:
            return PlainBSTNode(value)
        if value < node.value:
            node.left = self._insert(node.left, value)
        elif value > node.value:
            node.right = self._insert(node.right, value)
        return node

    def __contains__(self, value):
        node = self.root
        while node is not None:
            if value == node.value:
                return True
            node = node.left if value < node.value else node.right
        return False
# endregion

Scratch vs library

This is the rare face-off where the from-scratch code isn't racing a C library but its own unbalanced sibling — and it wins by two orders of magnitude on the input that matters. 104× faster at 8000 sorted insertions, and the gap grows quadratically, because the plain BST is doing O(n²) work to the AVL's O(n log n). The height chart is the cause laid bare: 17 versus 100000. What's striking is how little code buys that: the AVL tree is the BST plus height tracking and a dozen lines of rotation. That's the whole lesson of balanced trees — a small, local, constant-time repair applied consistently converts a structure with a catastrophic worst case into one with an ironclad guarantee. You still wouldn't hand-roll this in Python (use sortedcontainers), but now you know exactly what "balanced" costs and buys.

Where you'll actually meet it

AVL trees run wherever ordered data needs guaranteed-fast updates and lookups. They're a common choice in database and filesystem in-memory indexes, in-memory key-value stores that need range queries, and any ordered map where lookups dominate. Their close cousin the red-black tree powers std::map/std::set in C++, TreeMap in Java, and the Linux kernel's scheduler and memory management. And the rotation — the O(1) local rebalancing move you just built — is the fundamental operation of the whole balanced-tree family; once you understand it here, red-black trees, splay trees, and treaps are variations on where and when to apply it.

Takeaways

An AVL tree is a binary search tree that keeps a balance factor of ±1 at every node, repairing any violation after an insert or delete with an O(1) rotation, which guarantees the height stays about $1.44\log_2 n$ and every operation stays $O(\log n)$ for any input. It's the BST with its fatal flaw removed, at the modest cost of tracking heights and rotating — 104× faster than the unbalanced version on the sorted input that matters.

The next chapter is its more relaxed sibling. The red-black tree guarantees the same $O(\log n)$ but with a looser balance rule enforced by node colors, so it rotates less on updates — which is why, despite AVL's head start and tighter balance, the red-black tree is the one hiding inside most standard-library ordered maps.