7.15 Red-Black Trees

Red-black trees are self-balancing binary search trees with a relatively loose balance condition.

algorithmsbinary-searchordered-data

7.15 Red-Black Trees

Red-black trees are self-balancing binary search trees with a relatively loose balance condition. They do not try to keep the tree as strictly balanced as AVL trees. Instead, they enforce a small set of color rules that guarantee the tree height remains logarithmic.

This trade-off makes red-black trees practical. They provide predictable performance, handle frequent updates efficiently, and avoid excessive rotations. For that reason, they are widely used in standard libraries and systems software.

Examples include ordered maps, ordered sets, scheduler queues, memory management structures, and runtime data structures.

Problem

A plain binary search tree can degrade into a chain.

10
  \\n   20
     \\n      30
        \\n         40
           \\n            50

Search, insertion, and deletion degrade to:

O(n)

We need a structure that maintains logarithmic height even when keys are inserted in an unfavorable order.

AVL trees solve this by tracking exact height balance.

Red-black trees solve it by assigning each node a color and enforcing structural rules.

The Red-Black Tree Rules

Each node is either red or black.

A valid red-black tree satisfies five rules:

  1. Every node is red or black.
  2. The root is black.
  3. Every missing child is treated as a black leaf.
  4. A red node cannot have a red child.
  5. Every path from a node to a descendant leaf contains the same number of black nodes.

The fifth rule is the most important. It prevents one side of the tree from becoming much deeper than another.

The fourth rule prevents long chains of red nodes.

Together, these rules guarantee logarithmic height.

Node Structure

A minimal red-black node stores a key, child pointers, and a color.

type Color bool

const (
	Red   Color = true
	Black Color = false
)

type Node struct {
	Key   int
	Color Color

	Left  *Node
	Right *Node
}

Many production implementations also store:

Parent *Node
Value  any

Parent pointers simplify insertion and deletion fix-up code, but the core rules remain the same.

Why Colors Help

Consider this tree:

        40B
       /   \\n     20R   60R
    / \    / \\n  10B 30B 50B 70B

The letters show color:

B = black
R = red

No red node has a red child.

Every path from root to leaf has the same number of black nodes.

The tree is not necessarily perfectly balanced, but it is balanced enough.

Red nodes act like flexible connectors between black levels. They allow the tree to absorb insertions without immediately requiring strict height equality.

Black Height

The black height of a node is the number of black nodes on any path from that node down to a leaf.

Because every path must have the same black height, the tree cannot become arbitrarily skewed.

Example:

        40B
       /   \\n     20R   60R
    / \    / \\n  10B 30B 50B 70B

From 40 to any missing leaf, the number of black nodes is consistent.

This consistency is the structural backbone of red-black trees.

Searching

Searching in a red-black tree is identical to searching in an ordinary BST.

Colors play no role.

func Search(root *Node, key int) *Node {
	for root != nil {
		if key == root.Key {
			return root
		}

		if key < root.Key {
			root = root.Left
		} else {
			root = root.Right
		}
	}

	return nil
}

The colors only maintain shape during updates.

This separation keeps lookup simple.

Insertion Overview

Insertion begins exactly like ordinary BST insertion.

The new node is inserted as a leaf.

The new node is colored red.

Why red?

Adding a red node does not change the black height of any path. That minimizes the number of rules that might be violated.

The only likely violation is:

red parent with red child

That violation is repaired using recoloring and rotations.

Insertion Case 1: Empty Tree

If the tree is empty, the new node becomes the root.

The root must be black.

10B

This satisfies all rules.

Insertion Case 2: Black Parent

If the parent is black, inserting a red child creates no violation.

    20B
   /
 10R

The black height does not change.

No rotations are needed.

This is one reason red-black trees can be efficient for insert-heavy workloads.

Insertion Case 3: Red Parent and Red Uncle

Suppose the parent and uncle are both red.

        40B
       /   \\n     20R   60R
    /
  10R

The new node 10R violates the no-red-red rule with parent 20R.

Since the uncle 60R is also red, recolor:

        40R
       /   \\n     20B   60B
    /
  10R

If 40 is the root, recolor it black.

        40B
       /   \\n     20B   60B
    /
  10R

No rotation is needed.

The violation moves upward and may need further repair.

Insertion Case 4: Red Parent and Black Uncle

If the parent is red and the uncle is black or missing, rotations are required.

Example:

      30B
     /
   20R
  /
10R

This is a left-left case.

Rotate right at 30 and recolor.

      20B
     /   \\n   10R   30R

The BST property is preserved, and the red-black rules are restored.

Left-Right Insertion Case

Consider:

      30B
     /
   10R
     \\n     20R

This is a left-right case.

First rotate left at 10.

      30B
     /
   20R
   /
 10R

Then rotate right at 30 and recolor.

      20B
     /   \\n   10R   30R

The mirror cases apply on the right side.

Simplified Insertion Strategy

At a high level:

1. Insert as in a BST.
2. Color the new node red.
3. While parent is red:
   - If uncle is red, recolor.
   - If uncle is black, rotate and recolor.
4. Color the root black.

This process repairs local violations while preserving the global black-height rule.

The implementation details are more involved than treaps, but the conceptual repair loop is compact.

Rotations in Red-Black Trees

Rotations are the same rotations used in ordinary BST balancing.

A left rotation:

    x
     \\n      y

becomes:

      y
     /
    x

A right rotation is the mirror image.

The colors determine when rotations happen and how nodes are recolored afterward.

The rotation preserves key order. The recoloring restores red-black validity.

Deletion Overview

Deletion is more complex than insertion.

If a red node is removed, black heights remain unchanged.

If a black node is removed, one path may lose a black node. This creates a black-height violation.

The repair process may involve:

recoloring
rotations
moving the violation upward

Deletion fix-up is the most error-prone part of red-black tree implementation.

In many practical settings, developers use a library implementation rather than writing deletion logic by hand.

Why Red-Black Trees Are Loosely Balanced

AVL trees require the heights of left and right subtrees to differ by at most one at every node.

Red-black trees allow more variation.

This looser rule means:

fewer rotations during insertion and deletion

The trade-off is that lookups may perform slightly more comparisons than in an AVL tree.

In update-heavy workloads, red-black trees often perform well because they avoid over-correcting the shape.

Red-Black Trees in Libraries

Many language runtimes and standard libraries use red-black trees or closely related structures.

Common uses include:

Structure Typical Implementation
Ordered map Red-black tree
Ordered set Red-black tree
Interval tree Augmented red-black tree
Scheduler queue Red-black tree variant
Memory region index Red-black tree variant

The exact implementation may vary, but the red-black idea remains common because it provides strong worst-case guarantees with modest update overhead.

Red-Black Trees Versus AVL Trees

Feature Red-Black Tree AVL Tree
Balance strictness Looser Stricter
Search speed Slightly worse in practice Slightly better in practice
Insert/delete rotations Often fewer Often more
Implementation complexity High Moderate
Worst-case height O(log n) O(log n)
Common use General-purpose ordered maps Read-heavy ordered indexes

This is a practical distinction.

AVL trees optimize lookup height.

Red-black trees optimize update flexibility.

Red-Black Trees Versus Treaps

Feature Red-Black Tree Treap
Balancing Deterministic Randomized
Guarantee Worst-case O(log n) Expected O(log n)
Metadata Color Priority
Split/merge Awkward Natural
Library use Very common Less common
Implementation Complex Simple

Treaps are easier to write.

Red-black trees are preferred when deterministic worst-case bounds matter.

Complexity Analysis

A red-black tree with n nodes has height:

O(log n)

Therefore:

Operation Complexity
Search O(log n)
Insert O(log n)
Delete O(log n)
Minimum O(log n)
Maximum O(log n)
Lower bound O(log n)
Upper bound O(log n)

Rotations per insertion are bounded by a small constant. Recoloring may propagate upward, but the number of visited nodes remains logarithmic.

Common Mistakes

A common mistake is treating colors as cosmetic metadata. Colors encode the balancing invariant. Incorrect colors can silently destroy performance guarantees.

Another mistake is forgetting that missing children are considered black leaves. Many deletion cases depend on this convention.

A third mistake is recoloring without considering the root rule. The root must always be black after insertion or deletion repair.

Finally, developers often implement insertion correctly and underestimate deletion. Red-black deletion is substantially more subtle and deserves isolated testing.

Takeaway

Red-black trees are balanced binary search trees that use color rules to guarantee logarithmic height without enforcing strict symmetry. Their looser balance condition makes updates efficient while preserving strong worst-case bounds. Searching works exactly like an ordinary BST; colors only matter during insertion and deletion repair. Red-black trees are a standard choice for general-purpose ordered maps and sets because they provide a practical balance between predictable performance, update efficiency, and implementation cost.