Balanced Search Trees: How AVL and Red-Black Trees Stay Fast

You keep a running leaderboard — scores dropping in one at a time — and it’s always instantly sorted. Tap a name and its rank is right there. Ask “who scored between 900 and 1000?” and they appear in order. Thousands of entries, and it never slows down.

That last part is the quiet miracle: never slows down, no matter what order the scores arrived in. Because there’s a version of this that secretly rots — feed a naive sorted structure its keys in an unlucky order and it quietly decays until every lookup crawls through the whole thing. Fast on the demo, unusable in production. The structure that refuses to rot is a balanced search tree, and by the end of this article you and I will have built one, rotation by rotation, and you’ll know exactly why it can promise O(log n) forever.

Let’s start nowhere near a computer

Picture a baby’s crib mobile — the hanging kind, little tags dangling from crossbars, each crossbar balanced on a pivot. Hang it evenly and it floats wide and flat. Now clip every new tag onto the same left end. Pretty soon the whole thing isn’t a mobile at all — it’s one sad vertical string of tags, hanging straight down.

Here’s what makes it a search tool and not just décor: the tags hang in a fixed left-to-right order. To find one, you start at the top pivot and, at each crossbar, go left or right — a decision that throws away half of what’s left. Reaching any tag takes as many steps as the mobile is tall. A wide, flat mobile is a handful of steps deep. The sad vertical string is as deep as it has tags — you’re back to checking them one by one.

So depth is everything, and depth is exactly what “clip everything to one side” destroys.

Now the repair, and this is the whole trick of the article. When one side gets too heavy, you don’t rebuild the mobile. You grab a lower joint, hoist it up to become the new top pivot, and let the old top swing down to the other side. The tags dangling in the middle swing across to a new arm — but their left-to-right order never changes. You’ve made the mobile shorter without reordering a single tag.

That hoist has a name in code: a rotation. And “shorter without reordering” is the one sentence to carry through everything below.

Where you already lean on this

Every time you reach for a sorted map or set from the standard library — TreeMap, TreeSet — you’re standing on a balanced tree; the ordering you get for free (first key, last key, everything after some value) is the tree’s shape showing through. And every database index you’ve ever queried is a balance story: ask for “all orders from last Tuesday” and the engine walks a balanced tree to reach the answer in a few hops instead of scanning the table.

But the most illuminating cousin lives where the assumptions change: the B-tree inside that database index. A plain balanced tree obsesses over the number of comparisons on the longest path. A B-tree obsesses over the same longest path — but measured in disk seeks, and a seek is roughly a million times slower than a comparison. So a B-tree makes each node fat: hundreds of keys and hundreds of children per node, crushing the tree to three or four levels even for a billion rows, so a lookup touches three or four pages instead of thirty. Same obsession — keep the longest path short — with the ruler swapped from comparisons to seeks. That one reframe, balance is really about bounding the longest path, and “path” can be counted in whatever is slow, teaches you more than another five “you’ve seen this” bullets.

What a balanced search tree actually looks like

Before any code, let’s pin down what we’re balancing. A binary search tree stores keys so that for every node, everything in its left subtree is smaller and everything in its right subtree is larger. That one rule — smaller left, larger right — is what lets you find a key by going left-or-right and halving the problem at each step, exactly like the mobile.

Read a BST left to right (an “in-order” walk) and it spells its keys in sorted order. Always. Hold onto that; it’s the invariant every rotation must protect.

The catch is that the ordering rule says nothing about shape. Insert 1, 2, 3, 4, 5, 6, 7 in that order into a plain BST and each key is bigger than the last, so each hangs off the right of the one before — the sad vertical string, height 7. Insert the same seven keys as a balanced tree and it’s height 3.

Both trees obey smaller-left-larger-right. Both spell 1..7 in order. But searching the left one is O(log n) and the right one is O(n) — the difference between three hops and seven, and at a million keys, between twenty hops and a million. A balanced search tree is just a BST that actively keeps itself looking like the left picture, whatever order the keys arrive in.

Let’s build one, step by step

We’ll build an AVL tree, because its rule is the easiest to see. At the end you’ll have the complete class.

Step 1: a node that remembers its height

To balance a tree we have to measure it, so every node carries its own height — the longest path down to a leaf beneath it. A lone leaf has height 1; an empty spot has height 0.

private static final class Node {
    final int key;
    Node left, right;
    int height = 1;          // a lone leaf is 1, an empty spot is 0
 
    Node(int key) { this.key = key; }
}

Storing the height on the node instead of recomputing it is what keeps every balance check O(1). We hold it correct with one helper that every change calls:

private static int height(Node n) {
    return n == null ? 0 : n.height;
}
 
private static void recomputeHeight(Node n) {
    n.height = 1 + Math.max(height(n.left), height(n.right));
}

Step 2: the balance factor — one number that spots the tilt

The mobile tips when one arm hangs lower than the other. The number that measures that tilt is the balance factor: the height of the left subtree minus the height of the right.

private static int balanceFactor(Node n) {
    return n == null ? 0 : height(n.left) - height(n.right);
}

A healthy AVL node has a balance factor of -1, 0, or +1 — the two sides differ by at most one level. The instant an insert pushes it to +2 (dangerously left-heavy) or -2 (right-heavy), we rebalance. That single threshold is the entire AVL rule.

Step 3: the bug — a plain insert rots on sorted input

Let’s write the obvious insert first — walk down, smaller-left larger-right, drop the key in the empty slot — with no balancing:

static Node insert(Node n, int key) {
    if (n == null) return new Node(key);
    if (key < n.key)      n.left  = insert(n.left, key);
    else if (key > n.key) n.right = insert(n.right, key);
    return n;                       // never looks at balance
}

Correct, and fine on shuffled data. But feed it sorted keys — which happens constantly: importing already-ordered records, timestamps, auto-increment ids — and every key lands to the right of the last. You’ve built the vertical string from the overview, height n. In a quick test, inserting 1..7 this way gives a tree of height 7; the balanced version gives 3.

The fix is to notice the tilt on the way back up and correct it. And the tool that corrects it — the one move this whole structure rests on — is the rotation.

Step 4: the rotation — shorter without reordering

Here’s the operation everything depends on, so let’s slow all the way down. A right rotation takes a left-heavy pair and re-hangs it around the lower node. Watch what moves:

Before, y is on top with x as its left child. After, x is on top and y has swung down to become x’s right child. Three subtrees hang off them — call them A, B, C from left to right. Trace them: before the rotation, the left-to-right (in-order) reading is A, x, B, y, C; after the rotation, it’s still A, x, B, y, C. The rotation did not reorder anything.

That isn’t a lucky coincidence — it’s forced by the BST rule, and it’s worth proving to yourself, because it’s the reason rotations are legal. Everything in the picture obeys A < x < B < y < C:

• x sits between A and B (a BST node: left subtree smaller, right subtree larger).
• y is larger than everything under x — A, x, B all lived in y’s left subtree — and smaller than C.

A right rotation has to re-home exactly one subtree: B, which was x’s right child, becomes y’s left child. Is that legal? B holds keys that are all greater than x and less than y — which is precisely what the slot “left child of y” demands (smaller than y, and sitting to y’s left so larger than x). Every other subtree keeps its parent. So the ordering A < x < B < y < C survives untouched while the left-leaning height drops by one. Shorter, not reordered.

In code it’s six pointer moves and two height updates — and the order of those updates matters:

private static Node rotateRight(Node y) {
    Node x = y.left;       // x will rise to the top
    Node b = x.right;      // b is the subtree that swings across
    x.right = y;
    y.left  = b;
    recomputeHeight(y);    // the lower node first...
    recomputeHeight(x);    // ...then the new top, which now depends on y
    return x;              // hand the new subtree-root back to the caller
}
 
private static Node rotateLeft(Node x) {
    Node y = x.right;
    Node b = y.left;
    y.left  = x;
    x.right = b;
    recomputeHeight(x);
    recomputeHeight(y);
    return y;
}

rotateLeft is the mirror image — the same six moves with left and right swapped. Note the two heights are recomputed bottom-up: y sinks below x, so y’s new height must be settled before x’s can be computed from it. Recompute in the wrong order and every balance factor above this point is quietly wrong.

Step 5: the four cases — which rotation, and when

A rotation fixes one specific lean. But a node can go out of balance in four shapes, depending on where the offending key landed two levels down. Name each by the path from the unbalanced node z to the new key: LL, LR, RL, RR.

The two “straight” cases are easy — a single rotation snaps them flat:

• LL (left child’s left grew): one rotateRight(z).
• RR (right child’s right grew): one rotateLeft(z).

The two “zig-zag” cases can’t be fixed by a single rotation — rotate once and you just tip the imbalance the other way. You straighten first, then rotate:

• LR: rotateLeft the left child to turn it into an LL, then rotateRight(z).
• RL: rotateRight the right child to turn it into an RR, then rotateLeft(z).

Here’s the whole decision, reading the balance factor to pick the case:

private static Node rebalance(Node node, int key) {
    int bf = balanceFactor(node);
    if (bf > 1) {                                 // left-heavy: LL or LR
        if (key > node.left.key) {
            node.left = rotateLeft(node.left);    // LR → straighten to LL
        }
        return rotateRight(node);
    }
    if (bf < -1) {                                // right-heavy: RR or RL
        if (key < node.right.key) {
            node.right = rotateRight(node.right); // RL → straighten to RR
        }
        return rotateLeft(node);
    }
    return node;                                  // still balanced, nothing to do
}

Comparing the new key against the child’s key is a compact way to tell a straight case from a zig-zag: if a left-heavy node’s new key went right of its left child, it’s the LR zig-zag.

Step 6: insert — walk down, heal on the way up

Now insert is just the naive walk with one thing added at the bottom of the recursion: after the child returns, recompute this node’s height and rebalance it.

public void insert(int key) {
    root = insert(root, key);              // reassign — the root itself can change
}
 
private static Node insert(Node node, int key) {
    if (node == null) 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
    recomputeHeight(node);
    return rebalance(node, key);           // heal on the way back up
}

Because the recursion unwinds from the new leaf up to the root, the first unbalanced node it meets is the deepest one — and for an AVL insert, fixing that single node with one rotation (or one double rotation) rebalances the entire tree. One insert, at most one rebalance. That’s the guarantee in full: after every insert no node leans by more than one, so height stays O(log n) forever.

How balanced trees stack up

Put n keys in. Here’s what each structure costs — and the column that matters is the last one, because a plain BST’s average case is a lie the moment your input is sorted:

Read the top two rows and a hash map looks like the obvious winner — O(1) beats O(log n). If all you ever do is “is this key present?” and “store this key”, use the hash map. It’s faster and simpler.

Everything below those two rows is why balanced trees exist. A hash map scatters keys across buckets by design, so it has no idea which key is smallest, which comes just before 20, or which fall between 10 and 40 — every such question forces it to look at all n keys. A balanced tree answers each in O(log n) because its keys are physically arranged in order.

So the real decision rule is about the questions, not the raw speed:

AVL vs red-black: two dialects of one promise

We built an AVL tree because its one-number rule is the clearest. But the balanced tree you actually use every day — inside TreeMap, TreeSet, and countless libraries — is a red-black tree. Both guarantee O(log n); they differ in how tightly they hold balance, and therefore how much work each write does.

An AVL tree is a strict landlord: every node’s two sides differ by at most one level, so lookups stay as shallow as possible. The price is that holding that strict rule can demand more rotations as you insert and delete.

A red-black tree is looser. Instead of tracking heights it paints each node red or black and enforces a few coloring rules:

• the root is black,
• a red node never has a red child,
• every path from the root down to a leaf passes through the same number of black nodes.

Those rules alone force the longest root-to-leaf path to be at most twice the shortest, which is all you need for O(log n). Because the balance is looser, a red-black tree gets away with fewer rotations — often a couple of recolorings (just flipping a bit) settle an insert that an AVL tree would rotate for. That’s the trade in one table:

If your workload is overwhelmingly reads, AVL’s shallower trees win. For a general-purpose sorted map that sees a healthy mix of reads and writes, red-black’s cheaper updates win — which is exactly why the standard library reached for it.

The complete implementation

Everything above, assembled into one class you can drop in or whiteboard from memory:

package dev.fiveyear.baltree;
 
import java.util.ArrayList;
import java.util.List;
 
/** A self-balancing binary search tree (AVL). Every operation is O(log n). */
public final class AvlTree {
 
    private static final class Node {
        final int key;
        Node left, right;
        int height = 1; // height in nodes: a lone leaf is 1, an empty spot is 0
 
        Node(int key) {
            this.key = key;
        }
    }
 
    private Node root;
 
    // --- reading the shape ---
 
    private static int height(Node n) {
        return n == null ? 0 : n.height;
    }
 
    /** left height minus right height: +ve is left-heavy, -ve is right-heavy. */
    private static int balanceFactor(Node n) {
        return n == null ? 0 : height(n.left) - height(n.right);
    }
 
    private static void recomputeHeight(Node n) {
        n.height = 1 + Math.max(height(n.left), height(n.right));
    }
 
    // --- the two rotations: the universal rebalancing move ---
 
    private static Node rotateRight(Node y) {
        Node x = y.left; // x rises to the top
        Node b = x.right; // b swings across to y
        x.right = y;
        y.left = b;
        recomputeHeight(y); // the lower node first...
        recomputeHeight(x); // ...then the new top
        return x; // x is the new root of this subtree
    }
 
    private static Node rotateLeft(Node x) {
        Node y = x.right;
        Node b = y.left;
        y.left = x;
        x.right = b;
        recomputeHeight(x);
        recomputeHeight(y);
        return y;
    }
 
    // --- insert, then heal on the way back up ---
 
    public void insert(int key) {
        root = insert(root, key);
    }
 
    private static Node insert(Node node, int key) {
        if (node == null) {
            return new Node(key); // the empty slot the walk fell into
        }
        if (key < node.key) {
            node.left = insert(node.left, key);
        } else if (key > node.key) {
            node.right = insert(node.right, key);
        } else {
            return node; // key already present — no duplicates
        }
        recomputeHeight(node);
        return rebalance(node, key);
    }
 
    private static Node rebalance(Node node, int key) {
        int bf = balanceFactor(node);
        if (bf > 1) { // left-heavy
            if (key > node.left.key) {
                node.left = rotateLeft(node.left); // Left-Right: straighten first
            }
            return rotateRight(node); // Left-Left (and the finished Left-Right)
        }
        if (bf < -1) { // right-heavy
            if (key < node.right.key) {
                node.right = rotateRight(node.right); // Right-Left: straighten first
            }
            return rotateLeft(node); // Right-Right (and the finished Right-Left)
        }
        return node; // already balanced
    }
 
    // --- the plain lookup a hash map also gives you ---
 
    public boolean contains(int key) {
        Node n = root;
        while (n != null) {
            if (key < n.key) {
                n = n.left;
            } else if (key > n.key) {
                n = n.right;
            } else {
                return true;
            }
        }
        return false;
    }
 
    public int height() {
        return height(root);
    }
 
    // --- the ordered operations a hash map cannot ---
 
    /** Largest stored key that is <= key, or null if none. O(log n). */
    public Integer floor(int key) {
        Node n = root;
        Integer best = null;
        while (n != null) {
            if (n.key == key) {
                return n.key;
            }
            if (n.key < key) {
                best = n.key; // a candidate; maybe a bigger one still fits
                n = n.right;
            } else {
                n = n.left;
            }
        }
        return best;
    }
 
    /** Smallest stored key that is >= key, or null if none. O(log n). */
    public Integer ceiling(int key) {
        Node n = root;
        Integer best = null;
        while (n != null) {
            if (n.key == key) {
                return n.key;
            }
            if (n.key > key) {
                best = n.key;
                n = n.left;
            } else {
                n = n.right;
            }
        }
        return best;
    }
 
    /** Every stored key in [lo, hi], in sorted order. O(log n + k). */
    public List<Integer> range(int lo, int hi) {
        List<Integer> out = new ArrayList<>();
        range(root, lo, hi, out);
        return out;
    }
 
    private static void range(Node n, int lo, int hi, List<Integer> out) {
        if (n == null) {
            return;
        }
        if (n.key > lo) {
            range(n.left, lo, hi, out); // only descend left when it can hold matches
        }
        if (n.key >= lo && n.key <= hi) {
            out.add(n.key);
        }
        if (n.key < hi) {
            range(n.right, lo, hi, out);
        }
    }
 
    /** All keys, sorted — an in-order walk. O(n). */
    public List<Integer> keys() {
        List<Integer> out = new ArrayList<>();
        inorder(root, out);
        return out;
    }
 
    private static void inorder(Node n, List<Integer> out) {
        if (n == null) {
            return;
        }
        inorder(n.left, out);
        out.add(n.key);
        inorder(n.right, out);
    }
}

And here it is doing the things we drew — the sorted feed that wrecks a plain BST, and the ordered questions a hash map can’t answer:

AvlTree tree = new AvlTree();
for (int i = 1; i <= 7; i++) tree.insert(i);   // the killer sorted feed
 
tree.height();          // 3  — not 7; a plain BST would be a 7-deep strand
tree.keys();            // [1, 2, 3, 4, 5, 6, 7]  — always sorted
tree.contains(4);       // true
tree.floor(4);          // 4
tree.floor(0);          // null   — nothing at or below 0
tree.ceiling(0);        // 1      — nothing at or below, smallest above
tree.range(2, 5);       // [2, 3, 4, 5]
 
// the guarantee, at scale: insert 1..100000 in sorted order
AvlTree big = new AvlTree();
for (int i = 1; i <= 100_000; i++) big.insert(i);
big.height();           // 17  — a plain BST here would be 100000 deep

That last line is the whole point in one number: a hundred thousand keys fed in the worst possible order, and the tree is seventeen hops tall.

The interview corner

Before you write a line, ask:

1. “Do we actually need ordered operations, or just lookup by key?” If it’s pure membership, a hash map is simpler and faster — say so out loud. Balanced trees earn their keep only when you need range, floor/ceiling, min/max, or sorted iteration.
2. “What’s the read/write mix, and do we care about worst-case latency?” Read-heavy and latency-sensitive nudges toward AVL; a balanced mix toward red-black. If the interviewer only cares about the average case on random data, mention that even a plain BST is a fair baseline.
3. “Are the keys comparable, and can there be duplicates?” A tree needs a total order (a Comparator); duplicates need a policy — reject them, or store a count on the node.

Then the ladder they’ll climb:

1. “Plain BSTs are already O(log n) on average — why bother balancing?” Average assumes random insertion order; real inputs (sorted imports, timestamps, ids) are the worst case, and a plain BST degrades to an O(n) strand. Balancing turns the average-case hope into a worst-case guarantee.
2. “Why does a rotation keep the tree valid?” It re-homes exactly one subtree, and that subtree’s key range fits its new parent exactly, so the in-order (sorted) sequence is unchanged — only heights move.
3. “AVL or red-black, and why?” Both are O(log n); AVL is stricter so lookups are shallower but writes rotate more, red-black is looser so writes are cheaper — general-purpose libraries (TreeMap, TreeSet) pick red-black.
4. “How would you answer ‘the k-th smallest key’ fast?” Store a subtree-size count on each node — an order-statistic tree — then rank and select are O(log n) by comparing k against left-subtree sizes as you descend. The count is maintained in the very same recompute step that maintains height.
5. “Now make it safe for many threads.” A single lock around the tree is correct but serial; for real concurrency reach for a ConcurrentSkipListMap — a skip list gives the same ordered operations with lock-free reads — or, on disk, a B-tree, which databases lock at page granularity.

Three mistakes that fail the round:

• Forgetting to reassign a rotation’s return value. rotateRight(node.left) computes a new subtree root; without writing it back via node.left = …, the real tree never changes shape and your “balanced” tree stays broken.
• Recomputing heights in the wrong order after a rotation. The node that sinks must be updated before the node that rises, or every balance factor above the rotation reads stale — the code believes it’s balanced while it isn’t.
• Handling a zig-zag with a single rotation. LR and RL need a double rotation; a single one just flips the lean to the other side. Two of the four cases are single, two are double.

Where to go from here

• Red-black insertion and deletion in full — we built AVL end to end and treated red-black at the level of its rules; the recolor-and-rotate cases are the natural next read, since it’s what TreeMap actually runs.
• B-trees and B+ trees — the same “keep it short” idea rebuilt for disk, where each node holds hundreds of keys to minimise slow seeks. Every relational database index is one.
• Skip lists — a probabilistic structure that delivers the same ordered operations with far simpler code and easy concurrency (ConcurrentSkipListMap).
• Order-statistic and interval trees — hang a little extra data on each node (a subtree count, a max endpoint) and the same balanced tree answers rank/select or “which intervals overlap this one” in O(log n).

If you enjoyed watching a structure trade its shape for speed, the trie plays the same game with strings, and Dijkstra’s algorithm leans on the heap — another tree kept deliberately short.

Next time you filter a list by “everything between these two values” and it answers instantly, you’ll know a tree somewhere just took a few short hops down a path it’s been carefully keeping short — hoisting a joint here, swinging a subtree there — so it never has to grow tall.