Red-Black Tree

Self-Balancing BSTO(log n)height = 4

A self-balancing BST where each node carries a color bit (Red or Black). Five invariants guarantee O(log n) height. Violations are fixed via recoloring and rotations.

Use the controls below to insert, search, or delete nodes.

Operations

Custom list demo

Traversal / search order

RB Invariants

✓Root is Black

✓No consecutive Reds

✓Black heights consistent

height = 4

Legend

Red node (circle)

Black node (square)

NIL leaf (black sentinel)

Highlighted

Highlighted edge

Operation Log

Demo: inserted [10, 20, 30, 15, 25, 5, 1, 7, 35, 40]

Insert fix-up cases

Case 1 — Uncle Red

Parent & uncle both Red

Recolor parent + uncle Black, grandparent Red. Move z up.

Case 2 — Uncle Black, zig-zag

LR or RL shape with uncle Black

Rotate parent to straighten → becomes Case 3.

Case 3 — Uncle Black, straight

LL or RR shape with uncle Black

Rotate grandparent + swap colors of parent & grandparent.

The 5 Red-Black invariants

1.Every node is Red or Black.

2.The root is Black.

3.Every nil leaf is Black.

4.If a node is Red, both children are Black.

5.All paths root→nil have equal Black-node count.