Red-Black Tree Visualizer

Learn red-black tree balancing through animated insertion, recoloring, rotations, invariant tracking, and responsive controls.

Current status: Ready. Insert a value or generate a new example to inspect the color rules.
Color-rule playground

Red-Black Tree Visualizer

Follow every recolor and rotation that preserves black height while keeping the tree approximately balanced.

Red-Black operations

Choose a value, then watch every repair step

ready

Press Enter to insert the entered value.

Tree setup

Ready. Insert a value or generate a new example to inspect the color rules.
Properties (live)
✓ Root is black
✓ No red-red parent/child
✓ Equal black heights
Black height: 0
Tree is empty - insert a value or Randomize
Nodes: 0Black height: 0Drag to pan · scroll to zoom

RBT Visual Legend

R
Red Node: Often new nodes. Cannot have a Red parent.
B
Black Node: The foundation. Root is always Black.
Recolor Action: Nodes flipping color to fix violations.

Tree Properties

Rule 1: Every node is either Red or Black.

Rule 2: The Root is always Black.

Rule 3: Red nodes cannot have Red children (No Double Reds).

Rule 4: Every path from root to null must have same number of Black nodes.

What is a Red-Black Tree?

A Red-Black Tree is a self-balancing Binary Search Tree (BST) where each node has an extra bit representing "color" (Red or Black). These colors are used to ensure the tree remains approximately balanced during insertions and deletions.

Unlike AVL trees which are strictly balanced, Red-Black trees provide a looser balance criterion but are often faster for heavy insertion/deletion workloads because they require fewer rotations to rebalance.

The 5 Properties

  • 1. Every node is either Red or Black.
  • 2. The Root is always Black.
  • 3. Every Leaf (NIL) is Black.
  • 4. If a node is Red, both its children must be Black (No Double Reds).
  • 5. Every path from a node to any of its descendant NIL nodes has the same number of Black nodes.

Real-World Use Cases

  • ✓
    Standard LibrariesJava's TreeMap and TreeSet, and C++ STL std::map and std::set are typically implemented using Red-Black Trees.
  • ✓
    Linux KernelUsed in the "Completely Fair Scheduler" (CFS) to manage process scheduling efficiently.

Concept guide

Review the mental model, tradeoffs, and practical use cases after you experiment.

Red-Black Tree Complete Info Card

Self-BalancingColor-Coded

A Red-Black Tree is a self-balancing binary search tree that uses color coding (RED/BLACK) to maintain approximate balance. Provides efficient O(log n) operations with fewer rotations than AVL trees, making it ideal for frequent insertions and deletions.

Tree Characteristics

Search Complexity

Guaranteed height bound

O(log n)

Insert/Delete

With rotations and recoloring

O(log n)

Space Complexity

Node storage + color bits

O(n)

Height Bound

Worst-case height guarantee

2 log(n+1)

Balancing

Less strict than AVL

Approximate

Rotations per Insert

Amortized constant

O(1)

Red-Black Properties

Color Property

Every node is RED or BLACK

Fundamental invariant

Root Property

Root is always BLACK

Base case

Red Property

No two RED nodes adjacent

Prevents long red chains

Black Property

Equal black nodes to null leaves

Balances tree height

Leaf Property

All leaves (NIL) are BLACK

Consistent termination

Insertion & Balancing Operations

1

Insert: Standard BST insertion with RED node

2

Fix: Recolor and rotate if red property violated

3

Cases: Handle uncle's color and position

4

Rotate: Left/Right rotations to restore balance

5

Recolor: Change colors to maintain properties

Rotation Cases

CaseSituationAction
Left-Left (LL)Right rotation neededSingle right rotation
Right-Right (RR)Left rotation neededSingle left rotation
Left-Right (LR)Left then right rotationDouble rotation
Right-Left (RL)Right then left rotationDouble rotation

Comparison with Other Trees

AVL Tree

✓ Stricter balance, faster lookups✗ More rotations on updates

Splay Tree

✓ Self-optimizing, simple✗ No balance guarantees

B-Tree

✓ Better for disk, higher branching✗ More complex node structure

Treap

✓ Probabilistic balance✗ Random priorities needed

Optimal Use Cases

  • •Language libraries (Java TreeMap, C++ map)
  • •Databases and file systems
  • •Real-time systems with mixed operations
  • •Applications with frequent insertions/deletions

Implementation Challenges

  • •Complex insertion/deletion algorithms
  • •Multiple cases for balancing operations
  • •Debugging color property violations
  • •Memory overhead for color storage
Pro Tip: Red-Black Trees provide the best balance between lookup performance and update efficiency. They're the preferred choice for standard library implementations where both search and modification operations are common.
Approximate BalanceFewer RotationsLibrary Standard