Skip to content
Algorithm Atlas
Data StructuresAll categories
CoreSource checked

Red-Black Tree

Maintains a balanced binary search tree with color rules.

Explore relationshipsOpen constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category
Data Structures
Difficulty
Advanced
Family
Balanced Search Tree
Tier
Core
Status
Verified
Review
Source Checked
Sources
2
Formulas
0
Relationships
7
Code example
Not ready
Visualization
Ready
Aliases
RB Tree

Overview

A Red-Black Tree uses red and black node colors plus rotations to keep search, insert, and delete logarithmic.

Core Concepts

stored invarianttree balancingtree structuresorted search spacebalanced search treeinvariant maintenancequery operationupdate operation

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(log n)

Average

O(log n)

Worst

O(log n)

Space

O(n)

When to Use

  • Use Red-Black Tree when you need to store ordered keys.
  • Use it when the input assumptions match the method's model.
  • Use it when the operation mix matches the structure's strengths.
  • Use it when the method's tradeoffs fit the workload.

When Not to Use

  • Avoid it when the input cannot be kept sorted cheaply.
  • Avoid it when simpler arrays or maps meet the performance and clarity needs.
  • Avoid it when the required output is not balanced binary search tree.

What It Does

  • Stores ordered keys
  • Restores balance with recoloring and rotations

Use Cases

  • Ordered maps
  • Ordered sets
  • Runtime library containers

Inputs

  • Comparable keys or values

Outputs

  • Balanced binary search tree

Pseudocode

  1. 1.Insert or delete like a binary search tree
  2. 2.Color new nodes according to the rules
  3. 3.Fix violations with rotations and recoloring
  4. 4.Keep black-height balanced
  5. 5.Search by normal key comparisons

Canonical Example

Input
operations = insert 5, insert 2, query 5
Output
query result = found
Explanation
Red-Black Tree: The structure stores data so later operations can answer efficiently.

Implementation Notes

  • Keep the input contract explicit: Comparable keys or values.
  • Write operation-level tests that check both returned values and internal invariants.
  • Test updates and queries as sequences, not only one operation at a time.

Common Pitfalls

  • Red-Black Trees keep balance less strictly than AVL Trees but often update faster.
  • Forgetting to maintain invariants after insert, delete, merge, or update operations.
  • Handle empty, invalid, and boundary inputs before trusting balanced binary search tree.
  • Incorrect updates can leave stale pointers, counts, balance metadata, or cached summaries.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show red and black nodes rotating to preserve balance rules.

Red-Black Tree mechanism walkthrough step 1 of 5suvwxt
Step 1 of 5: Insert or delete like a binary search tree
colored-tree-rotations

Notes

Red-Black Tree operates in O(log n) time and O(n) space within the Balanced Search Tree family. Often compared with Binary Search Tree and B-Tree.

Sources (2)

What each reference supports for this entry.

Introduction to Algorithms (CLRS)

Book

Reference for red-black tree rotations, color invariants, and logarithmic search-tree operations.

A Dichromatic Framework for Balanced Trees

Paper

Original reference for red-black tree color invariants and balanced tree update behavior.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discoveryOpen map
Variant ofBinary Search Tree

Data Structures · Foundation

Red-black trees are balanced binary search trees with color-based invariants.

Compare with this
AlternativesAVL Tree

Data Structures · Core

AVL trees and red-black trees are balanced binary search trees with different rebalancing tradeoffs.

Compare with this
AlternativesB-Tree

Data Structures · Core

B-trees optimize block-oriented ordered search, while red-black trees optimize pointer-based memory search.

Compare with this
Used byCompletely Fair Scheduler

Scheduling · Core

CFS uses a red-black tree ordered by virtual runtime to pick the runnable task with the smallest vruntime.

Compare with this
Has specializationsInterval Tree

Data Structures · Core

Interval trees specialize balanced search trees by augmenting nodes with interval endpoints and subtree maxima.

Compare with this
Has specializationsOrder Statistic Tree

Data Structures · Core

Order-statistic trees specialize balanced search trees by augmenting nodes with subtree sizes for rank and select.

Compare with this

Relationships

View full relationship page
Variant ofBinary Search Tree

Red-black trees are balanced binary search trees with color-based invariants.

Related Algorithms

Binary Search TreeB-Tree

Tags

Data StructureBalanced TreeTreeSorted Data