AVL Tree and Red-Black Tree

Definition: Self-balancing binary search trees that automatically adjust node heights via tree rotations to guarantee O(log n) worst-case operation bounds.

How It Works

AVL Tree. Every node stores (or computes) a Balance Factor BF = height(left) - height(right), and the invariant is that BF stays in {-1, 0, 1} for every node. After an insert or delete, the algorithm walks back up from the modified node toward the root, recalculating heights. The first node found with BF outside that range triggers a rotation:

LL case (left-left heavy): single right rotation
RR case (right-right heavy): single left rotation
LR case (left-right heavy): left rotation on the child, then right rotation on the node
RL case (right-left heavy): right rotation on the child, then left rotation on the node

Red-Black Tree. Balance is relaxed and encoded with color instead of a numeric height. Five invariants hold at all times: every node is red or black, the root is black, every leaf (null) is treated as black, a red node never has a red child, and every root-to-null path passes through the same number of black nodes (the black-height). Insert/delete fix-ups recolor nodes and perform at most a constant number of rotations (at most 2 for insertion, at most 3 for deletion) to restore these invariants, unlike AVL which can require rotations cascading all the way up.

Rotation mechanics. A rotation is a local, O(1) pointer rearrangement: pick an edge between a node and a child, and pivot the subtree around it so the child becomes the new local root. It preserves the BST in-order property while changing which subtree is “taller.”

AVL’s tighter invariant bounds tree height to roughly 1.44 * log2(n+2); Red-Black trees bound height to at most 2 * log2(n+1), since a red-black path can never be more than twice as long as the shortest path to a leaf.
Deletion is the harder operation in both structures: unlike insertion, which typically stops rebalancing after the first fix-up, deletion can require propagating rebalancing operations all the way up to the root.

Rotation Mechanics, Visually

A single right rotation around node P with left child C:

      P                C
     / \              / \
    C   z    ->      x   P
   / \                  / \
  x   y                y   z

C becomes the new subtree root, P becomes C’s right child, and y (formerly C’s right subtree) is reattached as P’s new left subtree. In-order order (x, C, y, P, z) is unchanged; only the shape changes. A left rotation is the mirror image. The LR and RL cases are just two of these single rotations applied back to back.

Red-Black Fix-Up Cases

Insertion always adds a new node colored red (a black node would immediately break the black-height invariant). If its parent is also red, three cases resolve the conflict, checked against the “uncle” node (the parent’s sibling):

Red uncle: recolor parent, uncle to black and grandparent to red, then continue fixing up from the grandparent — no rotation needed.
Black/null uncle, “triangle” shape (node is an inner grandchild): rotate the parent to convert it into the “line” shape below.
Black/null uncle, “line” shape (node is an outer grandchild): rotate the grandparent and swap its color with the parent’s — done in one step.

Deletion Cases (Both Trees)

Deleting a leaf: remove directly, then rebalance/re-fix-up starting from its former parent.
Deleting a node with one child: splice the child into the deleted node’s position.
Deleting a node with two children: replace its value with the in-order successor (leftmost node of the right subtree), then delete that successor instead, which is guaranteed to have at most one child.

Complexity Analysis

Operation	AVL Tree	Red-Black Tree
Search	O(log n)	O(log n)
Insert	O(log n) (up to O(log n) rotations)	O(log n) (at most 2 rotations + O(log n) recolors)
Delete	O(log n) (up to O(log n) rotations)	O(log n) (at most 3 rotations + O(log n) recolors)
Space	O(n)	O(n) + 1 bit/node for color

Both structures guarantee O(log n) in the worst case, which is the entire point: a plain Binary Search Tree (BST) offers no such guarantee and can degrade to O(n).

Why It Matters

Guarantees robust O(log n) worst-case performance under arbitrary insert/delete order, unlike a plain BST which degrades to a linked list on sorted input.
Red-Black trees favor write-heavy workloads (fewer rotations per update) which is why they back general-purpose ordered map/set libraries. AVL favors read-heavy workloads (tighter balance means shorter average search paths).
Underpins Linux’s Completely Fair Scheduler run-queue and virtual memory area (VMA) tracking, both implemented as Red-Black trees in the kernel, because the kernel needs predictable worst-case latency, not just good average performance.
Both structures avoid the single biggest weakness of an unbalanced BST: an adversary (or just unlucky input ordering) can’t force quadratic behavior, which matters anywhere untrusted or unpredictable data drives the tree’s shape.

When to Choose Which

Pick AVL when the workload is search-dominated and writes are rare, e.g. a static or slowly-changing index that gets queried far more often than updated.
Pick Red-Black when inserts and deletes are frequent relative to lookups, e.g. a language runtime’s ordered map, a scheduler run-queue, or any structure under constant churn.
Pick neither, and use a B-Tree or B+ Tree instead, when the structure lives on disk or across a network round-trip and minimizing the number of I/O operations matters more than minimizing in-memory comparisons.

Common Pitfalls

Implementing rotation logic without correctly updating parent pointers corrupts the tree silently; bugs only surface on later traversals or lookups.
Forgetting to rebalance on the walk back up after deletion, not just insertion, leaves the tree unbalanced despite passing insert-only tests.
Choosing AVL for a write-heavy cache or index when a Red-Black tree (or a B-Tree for disk-backed structures) would need far fewer rotations per update.
Off-by-one errors in balance-factor comparisons (> 1 vs >= 1) silently permit an unbalanced tree to pass shallow unit tests that only check a handful of insertions.
Recomputing subtree height from scratch on every operation instead of maintaining it incrementally, turning an O(log n) rebalance into an accidental O(n) one.
Misclassifying the LR/RL cases as LL/RR and applying a single rotation where a double rotation is required, which leaves the tree technically “balanced” by height but with the wrong in-order structure.
Treating a null child as unclassified rather than implicitly black in a Red-Black tree, which breaks black-height counting at the fringes of the tree.
Benchmarking only insert-heavy synthetic workloads when choosing between AVL and Red-Black, then discovering the real production workload is read-heavy (or vice versa) after the structure is already load-bearing.

Comparison

	AVL Tree	Red-Black Tree	Plain BST	B-Tree
Balance guarantee	Strict (height factor ±1)	Relaxed (2x bound)	None	Strict, multi-way
Lookup speed	Faster (tighter height)	Slightly slower	Unbounded worst case	Fast, disk-optimized
Write speed	Slower (more rotations)	Faster (fewer rotations)	Fastest, no rebalancing	Optimized for block I/O
Typical use	Read-heavy indexes	Language stdlib maps/sets	Teaching, simple cases	Disk-backed databases

Other Self-Balancing Variants

AVL and Red-Black are the two most common general-purpose balanced BSTs, but not the only ones. A Splay Tree rebalances opportunistically by moving recently-accessed nodes toward the root, giving good amortized performance for skewed access patterns at the cost of no strict worst-case bound per operation. A Treap combines BST ordering on keys with heap ordering on randomly assigned priorities, achieving expected O(log n) balance without any explicit rotation bookkeeping logic, at the cost of only a probabilistic (not guaranteed) bound.

Example

C++ std::map/std::set and Java TreeMap/TreeSet are typically implemented using Red-Black Trees, favoring predictable write cost over the tightest possible read cost. Inserting 10, 20, 30 into an AVL tree in ascending order triggers an immediate RR rotation after the third insert, since 10 -> 20 -> 30 would otherwise form a degenerate linked-list chain: the tree rebalances to a root of 20 with 10 and 30 as children, keeping height at 1 instead of letting it grow to 2. A Red-Black tree handles the same sequence differently: it inserts 30 as red under 20, and since no red-red conflict occurs (20 is black), no rotation happens at all, only the color assignment.

Extending the AVL example with a fourth insert, 40:

Before insert(40):        After insert(40) - no violation:
        20                        20
       /  \                      /  \
     10    30                  10    30
                                        \
                                         40

BF(30) = 0 - 1 = -1, still within range, so no rotation is needed here. Inserting a fifth value, 50, pushes BF(30) past the allowed range:

Before insert(50):             BF(30) = height(left=nil) - height(right={40,50}) = 0 - 2 = -2  VIOLATION
        20
       /  \
     10    30
             \
              40
                \
                 50

30 is the deepest unbalanced node, and the new node 50 was added to the right child of 30’s right child, an RR case. A single left rotation at 30 fixes it: 40 becomes the new subtree root, 30 becomes its left child, 50 stays as 40’s right child:

After left rotation at 30:
        20
       /  \
     10    40
          /  \
        30    50

Height drops back to 2 for the whole tree instead of growing to 3, restoring every node’s balance factor to within {-1, 0, 1} in a single O(1) rotation.

Real-World Systems

C++‘s std::map, std::set, std::multimap, and std::multiset are Red-Black trees in every major standard library implementation (libstdc++, libc++, MSVC STL), even though the standard itself only mandates the complexity guarantees, not the specific structure.
Java’s TreeMap and TreeSet are documented Red-Black tree implementations, and .NET’s SortedDictionary/SortedSet follow the same design.
The Linux kernel uses Red-Black trees for the Completely Fair Scheduler’s run-queue and for tracking a process’s virtual memory areas (VMAs), both chosen specifically for predictable O(log n) worst-case latency under constant insertion and deletion.
AVL trees show up less often in general-purpose libraries but are common in database index implementations and language runtimes that prioritize read-heavy lookup speed over write throughput.

Common Interview Questions

Why does Red-Black favor writes and AVL favor reads? — Red-Black tolerates a looser balance (up to 2x height difference) to minimize rotations per update; AVL enforces a tighter balance, which means more rotations on average but shorter search paths.
What’s the maximum number of rotations a single AVL insertion can trigger? — at most one double rotation (LR or RL) or one single rotation (LL or RR), since fixing the lowest unbalanced ancestor always restores the height invariant for everything above it too.
Why can Red-Black deletion require up to 3 rotations while insertion needs at most 2? — deletion can remove a black node without replacing it with another black node, requiring more extensive recoloring and rebalancing to restore the black-height invariant across multiple sibling subtrees.
If you only needed ordered iteration and rarely searched by key, would you still pick a balanced BST? — often not; a sorted array or skip list can be simpler and faster for read-mostly, append-rarely workloads where the balancing machinery isn’t earning its cost.

Referenced by

Dig deeper

Spot an error in this note?