Advanced Trees

Red-Black Tree

What is a Red-Black Tree?

A Red-Black Tree is a self-balancing Binary Search Tree that keeps itself roughly balanced by coloring every node either red or black and enforcing a small set of rules about how those colors can be arranged. Unlike an AVL tree, which balances strictly by height, a Red-Black Tree balances by color — and that looser constraint is exactly what makes it cheaper to maintain.

The Five Red-Black Properties

The five rules (the "red-black properties") together guarantee that the longest possible root-to-leaf path is never more than twice as long as the shortest one. That's a weaker balance guarantee than AVL's, but it's enough to keep every operation at O(log n), and it means Red-Black Trees need at most one or two rotations per insertion or deletion — compared to AVL, which can cascade rotations back up the tree. This is why Red-Black Trees are the default choice inside C++'s `std::map`/`std::set`, Java's `TreeMap`/`TreeSet`, and the Linux kernel's process scheduler and virtual memory management.

1. Every node is red or black

Each node stores one extra bit of information: its color.

2. The root is always black

If an insertion colors the root red, it's flipped back to black once the fixup finishes.

3. Every NIL leaf is black

The (implicit) null children at the bottom of the tree are treated as black leaves.

4. No red node has a red child

Two reds can never appear back-to-back on any path — this is the rule a new red insertion can violate.

5. Equal black-height on every path

Every path from a node to any of its descendant NIL leaves passes through the same number of black nodes.

How Does Insertion Fix a Violation?

Insertion always starts the same way a plain BST insertion does, and the new node is always colored red. Coloring it red (rather than black) means it can never violate the "same black-height on every path" rule by itself — the only rule a fresh red leaf can break is "a red node can't have a red parent." If that happens, a fixup procedure runs, walking back up the tree recoloring nodes and, when recoloring alone isn't enough, performing at most two rotations to restore all five properties.

Inserting 3 creates a red-red violation (5 → 3)

A right rotation at 10 fixes it — black-height unchanged

Red nodeBlack nodeViolation (red parent, red child)

Algorithm Steps (Insertion)

Insert the new node the normal BST way, and color it red
While the new node's parent is red (property 4 is violated), look at the uncle (the grandparent's other child):
- Uncle is red → recolor the parent and uncle to black, the grandparent to red, then continue fixing up from the grandparent
- Uncle is black (or missing) and the node forms a 'zig-zag' with its parent → rotate at the parent first to straighten it into a line
- Uncle is black (or missing) and the node forms a straight line with its parent → recolor parent black and grandparent red, then rotate at the grandparent
Color the root black (in case it was colored red during the loop)

Time Complexity

Best/Average/Worst Case: Height is always O(log n) → O(log n).

Time Complexity Analysis

Insertion (with fixup) needs O(1) extra space beyond the recursion/loop state — only a constant number of pointers get rewired or recolored, no matter how large the tree is.

Daily DSA Challenge by Scale Engineer

Insert a value and watch the tree recolor and rotate to stay red-black valid

Tree is empty

No tree yet — insert a value or generate a random tree

Red nodeBlack nodeRootRecolored / rotated by this insert

Test Your Knowledge before moving forward!

Red-Black Tree Quiz

How it works:

+1 point for each correct answer
0 points for wrong answers
-0.5 point penalty for viewing explanations
Earn stars based on your final score (max 5 stars)

Red-Black Tree Insertion Implementation

// Red-Black Tree node
class RBNode {
  constructor(value) {
    this.value = value;
    this.color = "RED"; // new nodes always start red
    this.left = null;
    this.right = null;
    this.parent = null;
  }
}

const isRed = (node) => node !== null && node.color === "RED";

function rotateLeft(root, x) {
  const y = x.right;
  x.right = y.left;
  if (y.left) y.left.parent = x;
  y.parent = x.parent;
  if (!x.parent) root = y;
  else if (x === x.parent.left) x.parent.left = y;
  else x.parent.right = y;
  y.left = x;
  x.parent = y;
  return root;
}

function rotateRight(root, x) {
  const y = x.left;
  x.left = y.right;
  if (y.right) y.right.parent = x;
  y.parent = x.parent;
  if (!x.parent) root = y;
  else if (x === x.parent.right) x.parent.right = y;
  else x.parent.left = y;
  y.right = x;
  x.parent = y;
  return root;
}

function fixInsert(root, z) {
  while (z.parent && z.parent.color === "RED") {
    const parent = z.parent;
    const grandparent = parent.parent;

    if (parent === grandparent.left) {
      const uncle = grandparent.right;
      if (isRed(uncle)) {
        // Case 1: uncle is red -> recolor
        parent.color = "BLACK";
        uncle.color = "BLACK";
        grandparent.color = "RED";
        z = grandparent;
      } else {
        if (z === parent.right) {
          // Case 2: zig-zag -> rotate to a line
          z = parent;
          root = rotateLeft(root, z);
        }
        // Case 3: straight line -> recolor and rotate
        z.parent.color = "BLACK";
        grandparent.color = "RED";
        root = rotateRight(root, grandparent);
      }
    } else {
      // Mirror image of the above
      const uncle = grandparent.left;
      if (isRed(uncle)) {
        parent.color = "BLACK";
        uncle.color = "BLACK";
        grandparent.color = "RED";
        z = grandparent;
      } else {
        if (z === parent.left) {
          z = parent;
          root = rotateRight(root, z);
        }
        z.parent.color = "BLACK";
        grandparent.color = "RED";
        root = rotateLeft(root, grandparent);
      }
    }
  }
  root.color = "BLACK"; // property 2: the root is always black
  return root;
}

function insert(root, value) {
  const node = new RBNode(value);
  let y = null;
  let x = root;
  while (x) {
    y = x;
    if (value < x.value) x = x.left;
    else if (value > x.value) x = x.right;
    else return root; // no duplicates
  }
  node.parent = y;
  if (!y) root = node;
  else if (value < y.value) y.left = node;
  else y.right = node;

  return fixInsert(root, node);
}

// Usage example
let root = null;
[10, 5, 15, 3, 7, 1].forEach((value) => {
  root = insert(root, value);
});

Done With the Learning

Mark Red-Black Tree as done and view it on your dashboard

Explore Other Tree Topics

B-Tree

Trie (Prefix Tree)

Segment Tree

Fenwick Tree

AVL Balancing

BST Insertion

BST Deletion

In-order Traversal

Structure & Properties