Red-Black Trees

What is a Red-Black Tree?

A red-black tree is a self-balancing binary search tree where each node stores an extra bit representing its color (red or black). These color constraints ensure the tree remains approximately balanced, guaranteeing O(log n) time for search, insert, and delete.

The Five Rules

  1. Every node is either red or black.
  2. The root is always black.
  3. All NULL leaf nodes are considered black.
  4. A red node cannot have a red child (no two consecutive red nodes).
  5. Every path from a node to its descendant NULL leaves has the same number of black nodes.

Diagram

Example of a red-black tree by Nomen4Omen, CC BY-SA 4.0

Learn More

Wikipedia: Red-Black Tree