Red-Black vs AVL Tree

The balance invariants — side by side

AVL (Adelson-Velsky and Landis, 1962). For every node v, the heights of v's left and right subtrees differ by at most 1. The balance factor BF(v) = height(right) − height(left) is always in {−1, 0, +1}. Any insertion or deletion that breaks this triggers rebalancing rotations until the invariant is restored.

Red-Black (Bayer 1972 / Guibas-Sedgewick 1978). Five rules: (1) every node is red or black; (2) root is black; (3) NIL leaves are black; (4) red nodes have black children only; (5) every path from a node to its descendant NIL leaves has the same number of black nodes (black height). Together these guarantee max height ≤ 2 × log2(n+1).

The invariants imply very different shapes. AVL trees are nearly perfectly balanced: a chain of length 30 is impossible if AVL height is 30 — you need at least F(30) ≈ 832,040 nodes (where F is the Fibonacci sequence) to reach height 30 in AVL. Red-black trees can be more lopsided: a chain of black-red-black-red can reach height 30 with as few as 2^15 = 32,768 nodes.

Rotation counts — where red-black wins

For insert, both trees do a standard BST insert first, then rebalance. The rebalance cost differs sharply:

• AVL insert. Walk up from the new node, updating balance factors. At the first node where |BF| reaches 2, perform a rotation (single or double, depending on whether the path is LL, RR, LR, or RL). This rotation always restores balance — but in the worst case, you may walk up to O(log n) levels updating balance factors before reaching that point.
• RB insert. Color the new node red. If parent is black: done — no rebalancing needed. If parent is red: a "red-red violation" — fix by recoloring (case 1: uncle red — recolor parent/uncle black, grandparent red, recurse upward) or rotating (case 2/3: uncle black — at most 2 rotations and we're done permanently).
• Worst-case rotations. RB insert: at most 2 rotations regardless of N. AVL insert: 1 single rotation or 1 double rotation per imbalanced ancestor — but those imbalances can cascade O(log n) levels up.
• Recolorings. RB inserts may recolor up to O(log n) nodes (each is just one bit flip — O(1) work each). AVL updates O(log n) balance factors. Roughly equal mutation cost on recoloring/updating; the rotation savings on RB are the differentiator.

Lookup speed — where AVL wins

Lookup walks from root to target, comparing keys at each step. Average comparisons ≈ tree height. Since AVL is shorter (1.44 log2 N) than RB (2 log2 N), AVL averages fewer comparisons per lookup.

For n = 1,000,000:

• Perfect tree height: 20 (2^20 ≈ 1M)
• AVL max height: ~29 (1.44 × 20)
• RB max height: ~40 (2 × 20)

In practice, for random insertions, both trees stay close to the perfect height. The worst-case gap matters only on adversarial input — and benchmarks consistently show AVL is 5–10% faster on read-only workloads. For 90% read / 10% write workloads, the AVL lookup advantage starts to pay back its higher mutation cost; somewhere around 80% read it crosses over and AVL becomes competitive overall. For 50/50 or write-heavy workloads, RB clearly wins.

Side-by-side comparison

	Red-black tree	AVL tree
Balance invariant	Path-length ratio ≤ 2	Height difference ≤ 1
Max height	2 log₂(N+1)	1.44 log₂(N+2) − 0.328
Min nodes for height h	2^(h/2)	F(h+2) − 1 (Fibonacci)
Lookup speed	Slower (taller tree)	Faster (shorter tree)
Insert rotations	At most 2	Up to O(log N)
Delete rotations	At most 3	Up to O(log N)
Per-node metadata	1 color bit	Balance factor (2-3 bits)
Recoloring on insert	O(log N) (cheap, bit flips)	O(log N) BF updates
Best workload	Mixed reads + writes	Read-heavy
Used by	std::map, TreeMap, Linux CFS	Database indexes (less common)
Inventor / year	Bayer 1972, Guibas-Sedgewick 1978	Adelson-Velsky & Landis 1962

How to choose

• Use red-black when reads and writes are mixed in your workload, when you're using a standard library implementation (it's almost certainly RB), or when you need to interop with std::map / TreeMap.
• Use AVL when reads dominate (95%+ read), when you need tight latency bounds and can pay extra on writes, when the data structure is in a hot read path and the 5–10% lookup speedup matters.
• Use neither when you don't need order — use a hash table. When you need persistent/immutable trees — use functional finger trees. When you need range queries on disk — use B-trees or B+-trees. When you need lock-free concurrency — use skip lists.

Worked example: 7 inserts

Insert the keys [10, 20, 30, 40, 50, 25, 15] in order into both an empty AVL and empty RB tree:

• AVL trajectory. Insert 10 (root). Insert 20 right of 10 — BF = +1, OK. Insert 30 right of 20 — BF at 10 becomes +2 — rotate left at 10. Now tree is 20/10\30. Insert 40 right of 30 — BF at 20 becomes +1. Insert 50 right of 40 — BF at 30 becomes +2 — rotate left at 30. Tree: 20/10\40-30,50. Insert 25 left of 30 — no imbalance, BF stays under 2. Insert 15 left of 20 — no imbalance. Final tree height: 3. Total rotations: 2. Total BF updates: ~10.
• RB trajectory. Insert 10 (root, black). Insert 20 (red, right of 10) — parent black, OK. Insert 30 (red, right of 20) — red-red violation — uncle is NIL (black) — rotate left at 10, recolor. Tree: 20(B)/10(R)\30(R). Insert 40 (red, right of 30) — uncle 10 is red — recolor both children of 20 black, recolor 20 red. But 20 is root — make it black. Insert 50 (red, right of 40) — uncle is NIL, rotate left at 30, recolor. Insert 25 (red, left of 30) — no violation. Insert 15 (red, left of 10) — no violation. Final height: 3. Total rotations: 2. Total recolorings: ~4.

Both trees do 2 rotations on this sequence — a tie. For adversarial sequences (sorted input), AVL still rebalances at every level, while RB does at most 2 rotations regardless. RB's mutation thrift is most visible on long insertion sequences.

Real-world usage

• std::map and std::set (libstdc++, libc++). Red-black tree. Reasonable balance, cheap mutations.
• java.util.TreeMap and TreeSet. Red-black tree.
• Linux kernel's Completely Fair Scheduler (CFS). Red-black tree, keyed by virtual runtime. Picks the leftmost (lowest vruntime) process to run next. Insert/remove on every context switch — extremely mutation-heavy, hence RB.
• Linux kernel's epoll, virtual memory areas (vma_struct). Red-black tree.
• Some database B-tree variants. Effectively RB on a per-page basis when leaf data is in-memory.
• AVL trees in practice. Some embedded systems libraries (with strict latency bounds favoring shorter trees), some database catalog indexes where reads dominate, some algorithmic libraries for theoretical work. AVL is rarely the default in modern standard libraries.

Common misconceptions

• "AVL is always faster than RB." Only for lookups. Mutations are cheaper on RB. Mixed workloads favor RB.
• "RB is always faster than AVL." Only for writes. Lookup-heavy workloads favor AVL by 5–10%.
• "AVL's height bound is 1.5 log N." Close — the precise bound is 1.4404 log2(N+2) − 0.328. The 1.44 coefficient is the golden-ratio-related constant 1/log2(phi).
• "RB does at most 2 rotations per delete." Insert yes, delete is up to 3. Different operations have different rotation budgets.
• "AVL's balance factor must be stored as integer." No — it fits in 3 bits ({-2, -1, 0, +1, +2} during rebalance). Some implementations store the full subtree height (1 byte) instead for simpler code.
• "Red-black trees are 'order' trees by definition." No — they're a coloring scheme on top of an otherwise plain BST. The colors enforce balance; ordering is the BST invariant, unrelated.