What are Red-Black properties?

Every node is either red or black, the root is black, no two red nodes are adjacent, and every path from a node to descendant leaves contains the same number of black nodes.

Red-Black vs AVL Trees?

AVL trees are more strictly balanced but require more rotations. Red-Black trees are more efficient for frequent insertions and deletions.

Commercial uses of Red-Black Trees?

They are used in many production libraries: C++ STL (std::map, std::set), Java TreeMap, and Linux kernel process scheduling.

Red-Black Tree

A self-balancing binary search tree where each node is colored red or black, ensuring the tree remains approximately balanced during insertions and deletions.

READY

Insert values to watch the fix-up. A new node is always red; the rules then recolour and rotate until no red node has a red parent.

Value

Intuition

Standard BSTs can degrade into linked lists (O(n)) with sorted input. AVL trees are strictly balanced but require frequent rotations. Red-Black trees trade some balance for faster insertion/deletion (fewer rotations), guaranteeing O(log n) operations while maintaining a height at most 2 * log(n+1).

Concept

A Red-Black Tree is a BST with 5 properties:

Nodes are Red or Black.
Root is always Black.
Leaves (NIL) are Black.
If a node is Red, both children are Black (no double reds).
Every path from a node to its descendant NIL nodes has the same number of Black nodes.

How it Works

Insertion: Insert like BST (red node). Fix violations (recoloring or rotation) if parent is also red.
Deletion: Complex. If a black node is deleted, tree height reduces, violating black-height. Requires restructuring.
Rotations: Left and Right rotations are used to rebalance.
Recoloring: Changing node colors to fix parent-child conflicts.

Step-by-Step Breakdown

Insertion Logic:

Insert node as RED.
If parent is Black: Done.
If parent is Red: Check uncle's color.
Uncle Red: Recolor Parent+Uncle Black, Grandparent Red. Repeat for GP.
Uncle Black: Rotate (LL, RR, LR, RL cases) and recolor.

When to Use

General purpose self-balancing tree (used in C++ std::map, Java TreeMap).
When insertions/deletions are frequent (faster than AVL).
Implementing associative arrays.

When NOT to Use

When lookups are the dominant operation (AVL is strictly balanced, so slightly faster lookups).
Simple scenarios where O(n) is acceptable.

How to Identify

Keywords: "Map Implementation", "Self-Balancing", "Associative Array", "Ordered Set".

Sample Problems

TreeMap Implementation

Can be implemented with RBT for ordered keys.

Data Stream as Disjoint Intervals

Efficiently solved with balanced trees.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description

Fenwick Tree

Singly Linked List

Complexity

Time (Best)

O(log n)

Time (Average)

O(log n)

Time (Worst)

O(log n)

Space

O(n)

Red-Black Tree Code

1const RED = true;
2const BLACK = false;
3
4class Node {
5  constructor(data, color = RED) {
6    this.data = data;
7    this.color = color;
8    this.left = null;
9    this.right = null;
10    this.parent = null;
11  }
12}
13
14class RedBlackTree {
15  constructor() {
16    this.root = null;
17  }
18
19  leftRotate(x) {
20    let y = x.right;
21    x.right = y.left;
22    if (y.left !== null) y.left.parent = x;
23    y.parent = x.parent;
24    if (x.parent === null) this.root = y;
25    else if (x === x.parent.left) x.parent.left = y;
26    else x.parent.right = y;
27    y.left = x;
28    x.parent = y;
29  }
30
31  rightRotate(y) {
32    let x = y.left;
33    y.left = x.right;
34    if (x.right !== null) x.right.parent = y;
35    x.parent = y.parent;
36    if (y.parent === null) this.root = x;
37    else if (y === y.parent.left) y.parent.left = x;
38    else y.parent.right = x;
39    x.right = y;
40    y.parent = x;
41  }
42
43  insert(data) {
44    let node = new Node(data);
45    let y = null;
46    let x = this.root;
47
48    while (x !== null) {
49      y = x;
50      if (node.data < x.data) x = x.left;
51      else x = x.right;
52    }
53
54    node.parent = y;
55    if (y === null) this.root = node;
56    else if (node.data < y.data) y.left = node;
57    else y.right = node;
58
59    if (node.parent === null) {
60      node.color = BLACK;
61      return;
62    }
63    if (node.parent.parent === null) return;
64
65    this.fixInsert(node);
66  }
67
68  fixInsert(k) {
69    while (k.parent && k.parent.color === RED) {
70      if (k.parent === k.parent.parent.right) {
71        let u = k.parent.parent.left;
72        if (u && u.color === RED) {
73          u.color = BLACK;
74          k.parent.color = BLACK;
75          k.parent.parent.color = RED;
76          k = k.parent.parent;
77        } else {
78          if (k === k.parent.left) {
79            k = k.parent;
80            this.rightRotate(k);
81          }
82          k.parent.color = BLACK;
83          k.parent.parent.color = RED;
84          this.leftRotate(k.parent.parent);
85        }
86      } else {
87        let u = k.parent.parent.right;
88        if (u && u.color === RED) {
89          u.color = BLACK;
90          k.parent.color = BLACK;
91          k.parent.parent.color = RED;
92          k = k.parent.parent;
93        } else {
94          if (k === k.parent.right) {
95            k = k.parent;
96            this.leftRotate(k);
97          }
98          k.parent.color = BLACK;
99          k.parent.parent.color = RED;
100          this.rightRotate(k.parent.parent);
101        }
102      }
103      if (k === this.root) break;
104    }
105    this.root.color = BLACK;
106  }
107}

Related Lessons

Red-Black Tree

Intuition

Concept

How it Works

Step-by-Step Breakdown

When to Use

When NOT to Use

How to Identify

Sample Problems

TreeMap Implementation

Data Stream as Disjoint Intervals

AI resume checker — match your resume to the job description

Frequently Asked Questions

What are Red-Black properties?

Red-Black vs AVL Trees?

Commercial uses of Red-Black Trees?