6.2 Red-Black Trees
Previous Section: AVL and Rotations | Next Chapter: Heap
AVL maintains exact heights; red-black trees instead track color and black height. This section first fixes the NIL convention, then derives an upper bound on height, followed by the color-flipping and rotations during insertion, implemented with parent pointers and validators.
1. After AVL, why do we still need to learn coloring?
AVL enforces a height difference limit at each node, achieving a very tight upper bound on shape. The update code must maintain exact heights; after deletion, multiple ancestors might remain unbalanced.
AVL trees and red-black trees maintain different invariants. The color rules allow for a more relaxed shape; actual performance still depends on the workload and implementation.
2. First unify NIL leaves
Code commonly represents absent children with None. The definition of a red-black tree treats each empty child as a black NIL leaf. NIL nodes do not store user keys but participate in color and black height reasoning.
This section uses the five common properties:
- Each actual node is either red or black.
- The root is black.
- Each NIL leaf is black.
- The two children of a red node are both black; therefore, no path from root to leaf contains two consecutive red nodes.
- From any node to its descendant NIL leaves, the number of black nodes on each path is the same.
Different textbooks might combine "root black" and "NIL black" into other rules, or rewrite "node color" as "parent link color." As long as the conventions are clearly defined, proofs and implementations can be interconverted. When answering questions, first specify which convention is being used.
3. How Black Height Limits the Entire Tree
This section defines the black height of node x as: the number of black nodes on the path from x to any descendant NIL, excluding x itself but including the terminal NIL. Property 5 guarantees the same count along every downward path. Define the black height of NIL itself as 0.
Let the subtree rooted at an actual node x have black height b. Both child subtrees have black height at least b-1: a black child consumes one black node; a red child does not. Starting the induction at NIL, which contains zero actual nodes, each side has at least 2^(b-1)-1 nodes. Adding x gives at least:
2^b - 1For the whole tree, let n count actual nodes and let b be the black height of the root. Then b <= log2(n + 1). The root is black and red nodes cannot be adjacent, so at least half the actual nodes on each path are black. Define h as the number of actual nodes on the longest path, excluding NIL; an empty tree has height 0. Thus:
h <= 2b <= 2 log2(n + 1)Searching along a root-to-leaf path takes time O(log n). Insertions and deletions first locate the node in the BST, then repair colors and links, also taking time O(log n).
"The longest path is at most twice the shortest path" is ambiguous unless it defines whether NIL is included and how path length is counted. The black-height derivation is more precise and directly provides an upper bound in terms of n.
4. Why does the new node get colored red first?
In a nonempty tree, inserting a black node at one NIL position adds a black node to paths through that position while leaving other paths unchanged, violating property 5. Inserting it red preserves black height. The first root is an exception: every path gains a black node together, so the root can be black.
A red new node might meet a red parent node, violating property 4. Insertion fix runs only when such a "double red" occurs. The root has no parent, and is finally colored black at the end.
In each repair round, first identify three roles:
node: The lower red node in the current conflict;parent: red parent node;uncle: the grandparent's other child, with an absent child treated as black.
5. Three Methods for Fixing Shapes
In the diagram, B represents black, and R represents red.
Red Uncle: Only changes color, conflicts move upward
Insert 1 into a tree containing 10, 5, and 15:
10B 10R
/ \ / \
5R 15R -> 5B 15B
/ /
1R 1RColor the parent and uncle black, and the grandparent red. If the grandparent is the root, color it black when the loop ends. If its parent is red, continue checking upward.
Black Uncle, outer shape: rotate grandparent
[10, 5, 1] produces the outer LL shape:
10B 5B
/ / \
5R --> 1R 10R
/
1RColor the parent black and the grandparent red, then rotate the grandparent right. RR is the mirror case.
Black Uncle, inner shape: pull straight first
[10, 5, 7] forms LR:
10B 10B 7B
/ / / \
5R --> 7R --> 5R 10R
\ /
7R 5RFirst rotate the parent node left to convert LR into LL; then handle it according to the outer rule. RL is the mirror.
6. Complete Red-Black Tree Insertion
The following implementation uses parent pointers to repair upward. Parent pointers make the iteration code more intuitive, but are not part of the red-black tree definition; a recursive implementation can also maintain ancestor links upon return. This version stores unique integer keys, checks the int type before insertion, and returns False for duplicates. As in the previous lesson, bool follows Python's integer equality rules.
is_valid() checks:
- Strict BST upper and lower bounds;
- root color and root parent pointer;
- Does each child
parentpoint back to the current node; - Does a red node have a red child;
- Are the black heights on the left and right sides the same?
- Does the actual number of nodes equal
size?
RED = "RED"
BLACK = "BLACK"
def require_int_key(key):
if not isinstance(key, int):
raise TypeError("key must be an integer")
class RBNode:
def __init__(self, key, color=RED):
require_int_key(key)
self.key = key
self.color = color
self.left = None
self.right = None
self.parent = None
class RedBlackTree:
def __init__(self):
self.root = None
self.size = 0
@staticmethod
def _color(node):
return BLACK if node is None else node.color
def _rotate_left(self, old_root):
new_root = old_root.right
middle = new_root.left
old_root.right = middle
if middle is not None:
middle.parent = old_root
new_root.parent = old_root.parent
if old_root.parent is None:
self.root = new_root
elif old_root is old_root.parent.left:
old_root.parent.left = new_root
else:
old_root.parent.right = new_root
new_root.left = old_root
old_root.parent = new_root
def _rotate_right(self, old_root):
new_root = old_root.left
middle = new_root.right
old_root.left = middle
if middle is not None:
middle.parent = old_root
new_root.parent = old_root.parent
if old_root.parent is None:
self.root = new_root
elif old_root is old_root.parent.left:
old_root.parent.left = new_root
else:
old_root.parent.right = new_root
new_root.right = old_root
old_root.parent = new_root
def insert(self, key):
require_int_key(key)
parent = None
current = self.root
while current is not None:
parent = current
if key < current.key:
current = current.left
elif key > current.key:
current = current.right
else:
return False
node = RBNode(key)
node.parent = parent
if parent is None:
self.root = node
elif key < parent.key:
parent.left = node
else:
parent.right = node
self.size += 1
self._fix_insert(node)
return True
def _fix_insert(self, node):
while node.parent is not None and node.parent.color == RED:
parent = node.parent
grandparent = parent.parent
if parent is grandparent.left:
uncle = grandparent.right
if self._color(uncle) == RED:
parent.color = BLACK
uncle.color = BLACK
grandparent.color = RED
node = grandparent
else:
if node is parent.right:
node = parent
self._rotate_left(node)
parent = node.parent
grandparent = parent.parent
parent.color = BLACK
grandparent.color = RED
self._rotate_right(grandparent)
else:
uncle = grandparent.left
if self._color(uncle) == RED:
parent.color = BLACK
uncle.color = BLACK
grandparent.color = RED
node = grandparent
else:
if node is parent.left:
node = parent
self._rotate_right(node)
parent = node.parent
grandparent = parent.parent
parent.color = BLACK
grandparent.color = RED
self._rotate_left(grandparent)
self.root.color = BLACK
def inorder(self):
result = []
def walk(node):
if node is None:
return
walk(node.left)
result.append(node.key)
walk(node.right)
walk(self.root)
return result
def height(self):
def measure(node):
if node is None:
return 0
return 1 + max(measure(node.left), measure(node.right))
return measure(self.root)
def is_valid(self):
if self.root is None:
return self.size == 0
if self.root.parent is not None or self.root.color != BLACK:
return False
def check(node, low, high, expected_parent):
if node is None:
return True, 1, 0 # Implicit NIL Black
if node.parent is not expected_parent:
return False, 0, 0
if node.color not in {RED, BLACK}:
return False, 0, 0
if (low is not None and node.key <= low) or (
high is not None and node.key >= high
):
return False, 0, 0
if node.color == RED and (
self._color(node.left) == RED or self._color(node.right) == RED
):
return False, 0, 0
left_ok, left_black_count, left_count = check(
node.left, low, node.key, node
)
right_ok, right_black_count, right_count = check(
node.right, node.key, high, node
)
if not left_ok or not right_ok or left_black_count != right_black_count:
return False, 0, 0
black_count = left_black_count + (node.color == BLACK)
return True, black_count, left_count + right_count + 1
valid, _, count = check(self.root, None, None, None)
return valid and count == self.size
tree = RedBlackTree()
values = [10, 5, 15, 1, 7, 12, 18, 6, 8, 11, 13, 17, 20]
for value in values:
assert tree.insert(value)
assert tree.is_valid()
assert tree.inorder() == sorted(values)
assert tree.insert(10) is False
assert tree.size == len(values)
ordered = RedBlackTree()
for value in range(1, 101):
ordered.insert(value)
assert ordered.is_valid()
assert (1 << ordered.height()) <= (ordered.size + 1) ** 2The black_count returned by check() includes both the current node and terminal NIL, so an absent child returns 1. This differs from Section 3's black height, which excludes the current node, by the current node's contribution: a black leaf has black_count 2 and black height 1. Comparing children works because both use the same convention.
The validator assumes acyclic child links with no shared nodes. It checks parent links, colors, order, and counts, but does not traverse arbitrary damaged object graphs. Here height() measures the whole tree in O(n); the AVL example reads cached height in O(1). height(), inorder(), and full validation use O(h+1) stack space, logarithmic for a valid tree. The in-order list also occupies Θ(n) output space. Insertion repairs upward with parent pointers and O(1) auxiliary space. These costs treat integer-key comparisons as constant-time.
The final assertion rewrites h <= 2 log2(n+1) as 2^h <= (n+1)^2, avoiding floating-point rounding.
Why Parent Links Must Be Updated Together
A rotation doesn't just modify the three downward links locally; the new root must reattach back to the original root's parent node:
- Modify the parent pointer of the middle subtree.
- The new root inherits the parent node of the old root.
- The old root's original parent redirects its
leftorrightto the new root; if the old root was originally the entire tree root, then updateself.root. - Attach the old root to the new root and modify the parent pointer.
An internal rotation must update the original parent's child pointer. A rotation at the whole tree's root must update self.root. Missing either case can leave nodes unreachable from the root.
7. Insertion Rotation Count and Total Time
Linux kernel rbtree documentation gives the classic repair bounds: insertion uses at most two rotations, and deletion at most three. These bounds belong to the classic algorithms; they do not automatically apply to every left-leaning or other variant.
Here, "at most twice" counts only rotations:
- Finding the insertion position still requires traversing a
O(log n)path; - The red-uncle case can repeat recoloring farther up the tree;
- Each color read-write cycle has constant work, but the number of cycles may reach
O(log n).
So "rotation is a constant number of times" and "total insertion time is O(log n)" are not contradictory.
AVL insert requires at most two basic rotations. The more noticeable difference appears in deletion: AVL might rotate at multiple ancestors, while classic red-black tree deletion keeps the number of rotations at most three. Actual performance also depends on the comparator, caching, and implementation quality.
8. Why Deletion Is Harder
First apply the BST deletion steps to reduce the operation to removing a node with at most one actual child. The relevant color belongs to the node physically removed. A target with two children may only have its key replaced; its successor is the node removed.
Removing a red leaf preserves black counts. When a removed black node has one red child, coloring that child black restores the count. Otherwise, some paths may lose one black node. Repair algorithms often represent this deficit as "extra black" or "double black," then inspect the sibling and its children to restore equal black counts through recoloring and rotations.
This page implements insertion and introduces the source of deletion repairs:
Delete black node → some paths have black height reduced by 1 → borrow structure from sibling or propagate the gap upwardIn work, prioritize using container implementations that have been tested. To learn complete deletion, tests must cover red leaves, black leaves, a child, the root, red siblings, black siblings with two black children, and mirrored cases with red near or far nephews. Of the sibling's two children, the one on the side closer to the deficit is the near nephew; the other is the far nephew. NIL counts as black.
9. Red-Black Trees and Multiway Trees
Red links can encode multiple binary nodes into a multi-key node, but the variant name must be clearly specified:
- A classic red-black tree more naturally corresponds to a 2-3-4 tree. A black node and its red children can be merged into a 2-node, 3-node, or 4-node.
- Princeton's
RedBlackBSTexplicitly implements the 2-3 version: after each operation, red links lean left and never occur consecutively. This gives a one-to-one correspondence with 2-3 trees.
The 2-3 correspondence here refers to that specific variant. A standard five-property red-black tree allows black nodes to have two red children, corresponding to 4-nodes in a 2-3-4 tree. Check the actual invariants before comparing algorithms; the names "red-black" and "left-leaning" do not make repair code interchangeable.
10. What Does the Standard Library Promise?
Java TreeMap
Oracle Java 21 Documentation explicitly states that TreeMap is based on a red-black tree and guarantees containsKey, get, put, and remove have O(log n) time complexity. The documentation also notes that key ordering comes from natural order or the order specified at construction via Comparator.
You can say "TreeMap uses a red-black tree." Oracle's public documentation does not explain the design decision in terms of read and write costs, so it does not support an invented rationale for that choice.
C++ std::map
C++ Ordered Associative Containers Requirements specify the ordering semantics, iteration order, and logarithmic complexity. The standard does not specify node colors nor require a particular tree structure.
Many standard library implementations use red-black trees, which is a matter of concrete implementation fact. Professional documentation should specify the implementation and version, and it should not be elevated to a language standard guarantee.
Linux rbtree
Linux provides a generic rbtree interface that kernel subsystems can use to manage ordered objects. Referencing the current kernel documentation is more reliable than stating "a certain scheduler definitely uses a red-black tree," because specific subsystems may change with kernel versions.
11. How much space does metadata occupy?
From a model perspective, AVL nodes record height, while red-black nodes record color. The model cannot directly infer the physical size of an object:
- The runtime might add headers and alignment padding to objects;
- The
booleanfield is not guaranteed to occupy only one physical bit; - Linux's
rb_nodestores the parent pointer and color together in__rb_parent_color; - Whether a parent pointer exists depends on the implementation.
When comparing memory, check the specific layout or measurements, do not infer object sizes from "an integer versus one color bit."
12. Troubleshooting Checklist
| Symptoms | Checkpoint |
|---|---|
| Root is red | Does _fix_insert force the root to black before returning? |
| In-order traversal misses a subtree | Is middle reattached during rotation? |
| Nodes unreachable after an internal rotation | Does the old root's original parent point to the new root? |
| Validator detects parent pointer errors | Whether the three parent links of child, old root, and new root are synchronized |
| Unequal black heights | After recoloring a red uncle, does the repair continue at the grandparent? |
| Wrong rotation direction in an inner case | Is the parent rotated first, then the parent and grandparent retrieved again? |
13. Check Colors and Parent Links
- Draw
[10, 5, 15, 1]and write the color of each actual node before and after recoloring. - Draw
[10, 5, 1]and[10, 5, 7], and indicate which step rotates the parent node and which step rotates the grandparent. - Explain why coloring a new node red doesn't immediately change the black height.
- Explain why parent pointers are an implementation choice, yet must remain correct in this lesson's iterative repair code.
- In one sentence, distinguish the API guarantees of Java
TreeMapand C++std::mapfrom any particular implementation strategy.
Summary: What a Red-Black Tree Maintains
Red-black markings do not measure the exact height of each branch. They prohibit consecutive red nodes and ensure that the black height from any node to all NIL nodes is consistent, thereby limiting the tree height to O(log n). Parent pointers support this implementation's iterative repair. During an internal rotation, failing to reconnect the original parent can leave the entire subtree unreachable.
An AVL tree stores explicit height metadata; a red-black tree stores colors and enforces black-height constraints. Both prevent search-tree degeneration, but their metadata and repair strategies differ. The next chapter no longer maintains a complete search order; it keeps the current minimum or maximum near the root: Chapter 7: Heap.