Red-Black Tree Rotation Case Explorer

Fix-Up Scenario

Step duration 900 ms

Fix-Up State

Pick a scenario and press Run Scenario, or grow the tree with Insert Random Key.

Nodes

Black-height

Rotations (session)

Step

0 / 0

How it works

A red-black tree is a binary search tree where every node is colored RED or BLACK and five invariants hold: (1) root is black, (2) every leaf (null) is black, (3) a red node never has a red child, (4) every path from a node to any descendant null has the same number of black nodes (its black-height), and (5) it is a valid BST. Invariant (4) forces the longest root-to-leaf path to be at most twice the shortest, which bounds height at O(log n) and keeps search/insert/delete worst-case logarithmic.

Inserting a node as RED can only ever break invariant (3): a red node z with a red parent. The fix-up walks up the tree resolving this with three cases, using the node's uncle (grandparent's other child):

Case 1 (uncle RED):
  parent -> BLACK, uncle -> BLACK, grandparent -> RED
  z = grandparent   // violation may recur higher up

Case 2 (uncle BLACK, z is the "inner" child — triangle):
  z = parent; ROTATE at z toward the outside
  // falls through into Case 3

Case 3 (uncle BLACK, z is the "outer" child — line):
  parent -> BLACK, grandparent -> RED
  ROTATE at grandparent toward the outside
  // done — no violation remains

A single rotation (e.g. LEFT-ROTATE(x)) swaps x with its right child y: y takes x's place, x becomes y's left child, and y's old left subtree becomes x's new right subtree — an O(1) pointer operation that preserves the BST ordering.

Scenario dropdown + Run Scenario — builds a minimal tree that triggers exactly the chosen case and animates the fix-up step by step.
Insert Random Key — inserts a fresh key into the current tree and runs whatever real fix-up cases it happens to trigger, cascading through Case 1 if needed.
RED spheres are red nodes, dark slate spheres are black nodes; a gold glow marks the node(s) a step is acting on.

This is the exact mechanism inside C++ std::map/std::set, Java's TreeMap, and the Linux kernel's scheduler and virtual-memory trees.

Red node Black node Active in step

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.