AVL Tree vs Red-Black Tree: Ordered O(log n), No Exceptions

A plain binary search tree has one quiet failure mode. Insert keys in sorted order and you get a linked list. Every operation that was supposed to be O(log n) silently becomes O(n). Balanced BSTs exist to make that failure impossible, not unlikely. Impossible. Not "unlikely on random data." Not "probably fine in practice." Impossible. Structurally.

The mental model: a balanced BST is a sorted dictionary that enforces a height invariant so strict that every operation runs in O(log n) regardless of input order. It's the data structure you reach for when you need fast insert, delete, and lookup on ordered data, plus the operations a hash table simply cannot do: floor (largest key at or below a target), ceiling (smallest key at or above a target), range scans, and order statistics.

Two variants dominate. The AVL tree vs Red-Black tree question comes up in interviews precisely because they guarantee identical asymptotic bounds through different invariants. Understanding both makes you dangerous.

Why Plain BSTs Break

Binary search trees are elegant in theory. Left child smaller, right child larger, search follows the BST property down the tree in O(h) time where h is height. In a perfectly balanced tree of n nodes, h equals log₂ n and everything is O(log n).

Nothing enforces that balance, though. Insert 1, 2, 3, 4, 5 in ascending order and every new node goes right. The tree is a chain. Height is n. Search is O(n). You built a linked list with extra steps. O(n) insert. O(n) delete. Congratulations on the world's most elaborate linked list.

Left: height 3, every search O(log n). Right: same keys, sorted insertion, height 7, every search O(n).

The fix is to maintain a height invariant during every insert and delete. Both AVL and Red-Black trees do this through rotations, pointer-swapping operations that preserve the BST ordering property while reshuffling nodes to restore balance.

AVL Trees: The Strict Height Police

AVL trees (Adelson-Velsky and Landis, 1962, two Soviet mathematicians who apparently had very strong opinions about tree height) use the tightest possible invariant: for every node, the heights of its left and right subtrees differ by at most one.

Each node stores a balance factor: height(right subtree) - height(left subtree). Valid values are -1, 0, and +1. The moment any node's balance factor hits -2 or +2 after an insert or delete, you rotate to fix it.

How the Height Stays Logarithmic

Let N(h) be the minimum number of nodes in an AVL tree of height h. The worst case has one subtree at height h-1 and the other at h-2, giving:

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

That recurrence is the Fibonacci sequence. Yes, really. The worst-case AVL tree is literally a Fibonacci tree. Someone should have warned the CS departments this was going to come up in coding interviews. Fibonacci numbers grow as φ^h where φ ≈ 1.618, so n ≥ φ^h roughly, meaning h ≤ log_φ(n) ≈ 1.44 log₂ n.

An AVL tree of n nodes has height at most 1.44 log₂ n. Even in the worst case, you're within a factor of 1.44 of the theoretical minimum. That is a tight bound, not a loose one.

The Four Rotation Cases

When a balance factor violation occurs, you look at the unbalanced node and its heavy child to pick the fix.

LL/RR: one rotation. LR/RL: two. Either way, the imbalance is gone.

LL case. The left child's left subtree is too heavy. A single right rotation at the unbalanced node fixes it.

RR case. Mirror of LL. Single left rotation.

LR case. The left child's right subtree is heavy. Left-rotate the child first, then right-rotate the unbalanced node. Two rotations.

RL case. Mirror of LR. Right-rotate the child, then left-rotate the node.

Insertion needs at most one rotation (or one double rotation). The height of the rotated subtree returns to what it was before the insert, so imbalance cannot propagate upward. Deletion is harder: you may need to rotate and propagate all the way to the root, up to O(log n) rotations.

Red-Black Trees: The Color Rules

Red-Black trees enforce balance through a coloring scheme instead of an explicit height. Every node is red or black, and five invariants must hold at all times. Five. Here they are:

1. Every node is red or black.
2. The root is black.
3. Every NIL leaf is black.
4. A red node's children must both be black. No two consecutive red nodes.
5. Every path from a given node to any descendant NIL leaf passes through the same number of black nodes (the "black-height").

Every path from root to NIL hits 3 black nodes. No two reds touch. Both rules satisfied, no exceptions.

Rules 4 and 5 together constrain the shape. Rule 5 means every root-to-leaf path has the same black-height bh. Rule 4 says no two consecutive red nodes, so the longest possible path alternates black and red, reaching at most 2*bh nodes.

The Height Bound

By induction: a subtree rooted at black-height bh contains at least 2^bh - 1 internal nodes. Base case: bh = 0 is a NIL leaf with 0 nodes. Inductive step: each child has black-height at least bh-1 (a red child's children are black and still contribute bh-1; a black child contributes bh-1 directly), so the subtree has at least 1 + 2*(2^(bh-1) - 1) = 2^bh - 1 nodes.

So n ≥ 2^bh - 1, meaning bh ≤ log₂(n+1). The max height is 2*bh, so:

Height of a Red-Black tree ≤ 2 log₂(n+1). Always. No exceptions.

The Cheaper Fix-Up

After an insert, you may create a red node with a red parent, violating rule 4. The fix requires recoloring and at most 2 rotations. After a delete, at most 3 rotations. Most fix-up work is recoloring: O(1) per node, propagating at most O(log n) levels.

Red-Black trees do fewer rotations per operation than AVL trees. Fewer rotations means simpler, faster real-world updates. This is why they dominate standard libraries: C++ std::map and std::set, Java's TreeMap and TreeSet, the Linux kernel's completely fair scheduler. Every one of them is a Red-Black tree. The Linux kernel is scheduling your processes with this right now.

Node Memory Layout

Both structures share the same basic node shape: key, value, left pointer, right pointer, parent pointer, and one extra field.

For AVL nodes, the extra field is the node's height: an int, typically 4 bytes. For Red-Black nodes, the extra field is the color: 1 bit in theory, but usually padded to a byte or packed into the low bit of a pointer.

At 10 million nodes that's 400 to 480 MB. This is the moment people start looking at Rust's BTreeMap.

On a 64-bit system, a typical node costs 40 to 48 bytes. At 10 million nodes that's 400 to 480 MB. The constant factor matters at scale. Rust's BTreeMap takes a different approach: it's a B-tree that packs multiple keys per node, which means better cache locality and the same O(log n) guarantees.

Core Operations

The O(log n) guarantee for search, insert, and delete holds in the worst case, not just on average. That is what separates balanced BSTs from hash tables. No hash collisions, no degenerate inputs, no pathological behavior.

Floor and ceiling fall naturally from the BST structure. To find the floor of a target: walk the tree. Every time you go right (target is greater than current), record the current node as the best candidate so far. When you fall off the tree, the last recorded node is the answer. Ceiling is the mirror image.

One Structure, Every Language

You rarely implement a balanced BST from scratch. Most languages ship one in the standard library. Where they don't, AVL is the idiomatic choice.

from sortedcontainers import SortedList, SortedDict

sl = SortedList([5, 3, 1, 4, 2])
sl.add(6)
sl.remove(3)
print(sl[0])              # min: 1
print(sl[-1])             # max: 6
print(sl.bisect_left(4))  # index of floor

sd = SortedDict()
sd[3] = "three"
sd[1] = "one"
sd[5] = "five"

for key, value in sd.items():    # in-order iteration
    print(key, value)

print(sd.peekitem(0))    # (1, "one")  - min
print(sd.peekitem(-1))   # (5, "five") - max

What Problems It Solves

Ordered map with O(log n) everything. Any time you need a dictionary where you can also iterate in key order, find neighbors, or ask range questions, a balanced BST does what a hash table cannot. Hash tables win on raw lookup speed (O(1) average), but they give you no ordering at all.

Range queries. Find all events between timestamps A and B: walk to A in O(log n), then iterate in order until you pass B. Total cost is O(log n + k) where k is the number of results.

Order statistics. Augment each node with the size of its subtree and you get "kth smallest" in O(log n). Order books, ranking leaderboards, percentile queries: all use this pattern. Java's TreeMap doesn't come with this augmentation, but C++'s policy-based __gnu_pbds::tree does via find_by_order and order_of_key.

Sliding window with arbitrary eviction. When the outgoing element can be anywhere in the window (not just the oldest), a heap fails. It only supports O(log n) removal from the top. A balanced BST gives O(log n) removal from any position.

Median tracking. Two balanced BSTs (one for the lower half, one for the upper half) answer "current median" in O(1) after each O(log n) insert. The tops of the two structures are the two middle elements. Rebalance the sizes when they drift by more than one.

Recognizing the Pattern

Reach for a balanced BST when you see these signals. Not a heap. Not a sorted array. Not a HashMap with some creative key encoding. A balanced BST:

• You need sorted order, not just existence. If you're asking "is X in the set?", a hash set is faster. If you're asking "what's just below X?", you need a BST.
• You need O(log n) worst case on inserts and deletes, not just average case.
• You're doing range queries or neighbor lookups on dynamic data.
• You're maintaining a sorted window where arbitrary elements leave, not just the oldest.
• The problem says "sliding window" and the values can repeat (requiring a multiset, i.e., std::multiset in C++ or TreeMap with counts).

Worked Example 1: Sliding Window Median (LeetCode 480)

Find the median of every window of size k as it slides across an array.

A sorted array gives you the median in O(1) but insert and delete cost O(k). A heap gives O(1) peek but arbitrary-position deletion is O(k). Neither scales.

Use two TreeMaps (or multisets), one for the lower half and one for the upper half. Keep their sizes equal (or off by one). The median lives at the boundary. When the window advances: insert the new element into the correct half, rebalance the sizes, then delete the outgoing element from whichever half contains it. Each step is O(log k). Total: O(n log k).

The signal here is "sorted window" plus "arbitrary-position delete." That combination rules out heaps and points directly at a balanced BST. If you're still reaching for a heap at this point, that's fine. One WA teaches this faster than any explanation.

Worked Example 2: Count of Range Sum (LeetCode 327)

Count the number of range sums S(i, j) = prefix[j] - prefix[i] that fall within [lower, upper].

For each prefix sum p[j], you need to count how many previous prefix sums p[i] satisfy:

lower <= p[j] - p[i] <= upper
=> p[j] - upper <= p[i] <= p[j] - lower

That's a range count on a dynamic sorted set. A balanced BST augmented with subtree sizes answers each range count in O(log n), giving O(n log n) overall. In Java, use a TreeMap<Long, Integer> where the value is the count of times that prefix sum has appeared.

The signal: you're counting how many previously seen values fall in a computed range. That's a floor/ceiling range query on dynamic data. If that smells like a balanced BST problem, your nose is working.

AVL Tree vs Red-Black Tree: Recap

• Plain BSTs degenerate to O(n) on sorted input. Balanced BSTs add a height invariant that prevents it.
• AVL trees enforce balance factor ∈ {-1, 0, 1} at every node. Height is at most 1.44 log₂ n. Faster lookups, more rotations on updates.
• Red-Black trees enforce five color rules. Height is at most 2 log₂(n+1). Fewer rotations per update. Used in C++ STL, Java's TreeMap, and Linux internals.
• Total operation cost is O(log n) either way. AVL may rotate O(log n) times during a delete; Red-Black caps rotations at O(1) per operation but may recolor O(log n) nodes.
• The critical operations that hash tables cannot match: floor, ceiling, range queries, ordered iteration, and order statistics.
• In practice: TreeMap in Java or Kotlin, std::map in C++, SortedDictionary in C#, BTreeMap in Rust, sortedcontainers in Python.

If you want to practice explaining this reasoning out loud under interview pressure, SpaceComplexity puts you in a voice-based mock interview where you have to justify your structure choice and walk through the approach. Rubric-based feedback tells you whether you communicated the why, not just the what.

For complementary reading on the interview skills that matter alongside data structure knowledge, how to stop going silent when you're stuck and the clarifying questions that unlock the algorithm are worth your time.

Further reading

• Red-Black Tree - Wikipedia
• AVL Tree - Wikipedia
• std::map - cppreference.com
• BTreeMap in std::collections - Rust
• Red-Black Tree vs AVL Tree - GeeksforGeeks