Red-Black Trees — Properties, Rotations, Insertion, and Deletion Explained | Chapter 13 of Intro to Algorithms

Red-black trees are a class of self-balancing binary search trees that ensure fast operations for dynamic sets and dictionaries. By enforcing a series of color-based structural properties and local tree transformations, red-black trees guarantee O(log n) running time for SEARCH, INSERT, DELETE, and related queries. Chapter 13 of introduction to algorithms provides a comprehensive look at the mechanics, cases, and practical applications of red-black trees—an essential data structure in modern programming.

For a concise video summary and step-by-step walkthrough of red-black trees, watch below—and subscribe to Last Minute Lecture for more clear algorithm guides.

What Is a Red-Black Tree?

A red-black tree is a binary search tree (BST) that maintains strict balancing through five color-based properties:

• Each node is either red or black.
• The root is always black.
• All leaves (NIL nodes) are black.
• If a node is red, both children must be black (no two reds in a row).
• Every path from a node to its descendant leaves contains the same number of black nodes (equal black-height).

These constraints keep the longest root-to-leaf path at most twice the length of the shortest, guaranteeing the tree's height is O(log n).

Rotations: Tree Restructuring Operations

Red-black trees use rotations—local tree restructuring steps—to maintain balance after insertions and deletions:

• Left Rotation: Pivots a node x and its right child y, promoting y above x.
• Right Rotation: The mirror of left rotation, pivots left child above its parent.

Rotations preserve BST order and take only O(1) time. They are triggered during fix-up routines to restore red-black properties after updates.

Insertion: RB-INSERT and Fix-Up

To insert, add the new node using regular BST logic and color it red. If this breaks red-black properties (often by introducing consecutive red nodes), apply RB-INSERT-FIXUP:

• Case 1: Uncle is red — recolor parent and uncle black, grandparent red, then continue up the tree.
• Case 2: Uncle is black and node is a right child — left-rotate to convert to Case 3.
• Case 3: Uncle is black and node is a left child — recolor and right-rotate grandparent.

The final step always colors the root black. Insertions, including all fix-up steps, require O(log n) time and at most 2 rotations.

Deletion: RB-DELETE and Black-Height Restoration

Deletion in a red-black tree begins as a normal BST deletion, with three cases:

1. No child
2. One child
3. Two children: Replace with successor and adjust pointers

If a black node is removed, this can cause “extra blackness” violations that must be fixed. RB-DELETE-FIXUP uses a series of color changes and up to 3 rotations:

• Case 1: Sibling is red — recolor and rotate to convert to a simpler case.
• Case 2: Sibling and its children are black — recolor sibling and move the problem up.
• Case 3: Sibling is black, left child red, right child black — rotate and recolor to prepare for Case 4.
• Case 4: Sibling is black, right child red — recolor and rotate to restore all properties.

All fix-up steps ensure the red-black properties and tree height are restored, maintaining efficient O(log n) performance.

Red-Black Tree Applications and Variants

Red-black trees power the dynamic set and map data structures in many programming language libraries (e.g., C++ STL map and set). They also underpin variants such as:

• AVL Trees: Balance based on subtree heights
• 2-3 Trees: Allow multiple keys per node for higher branching
• B-Trees: Disk-friendly, multi-way balanced search trees
• Treaps, Splay Trees, Skip Lists: Alternative balancing or probabilistic structures

Red-black trees’ predictable balance and fast operations make them a standard for high-performance set, map, and database implementations.

Key Concepts and Glossary

• Red-Black Tree: BST with coloring rules to enforce balance
• Black-Height: Number of black nodes on root-to-leaf paths
• Rotation: O(1) tree operation to rebalance structure
• RB-INSERT-FIXUP / RB-DELETE-FIXUP: Restore properties after changes
• Sentinel (T:nil): Shared NIL node to simplify code
• Uncle: Parent’s sibling, key to fix-up logic
• Color Property: Constraints on red/black arrangement
• Successor/Predecessor: Inorder next or previous node
• Catalan Number: Counts unique BST shapes for n nodes

Conclusion: The Power of Red-Black Trees

Chapter 13 of introduction to algorithms equips you with a deep understanding of red-black trees, their invariants, and their crucial role in building fast, reliable data structures for searching, sorting, and set management.

Want to see these ideas in action? Watch the chapter video summary and keep learning with Last Minute Lecture.

Subscribe for new chapter walkthroughs and detailed algorithm explanations from introduction to algorithms and beyond!

If you found this breakdown helpful, be sure to subscribe to Last Minute Lecture for more chapter-by-chapter textbook summaries and academic study guides.