A Beginner-Friendly Illustrated Guide to Red-Black Trees (Part 1)

Preface

Red‑black trees are essentially binary search trees (BST) enhanced with a red/black color attribute and five balancing constraints. Understanding BSTs is a prerequisite because search operations are identical; the main new challenges are node insertion and deletion.

What Is a Red‑Black Tree?

A red‑black tree (invented in 1972) is a self‑balancing binary search tree, sometimes called a "symmetric B‑tree". It guarantees O(log n) time complexity for search, insertion, and deletion, and is used in Java's HashMap/TreeMap/TreeSet, Nginx timer management, Linux virtual memory, C++ STL, and many interview questions.

Big‑O Notation

Big‑O describes the worst‑case growth of algorithm time or space as input size increases. For example, O(1) is constant time, O(n) is linear, and O(log n) is logarithmic.

Binary Search Tree (BST)

A BST is an ordered binary tree where each node's left subtree contains only smaller keys, the right subtree only larger keys, both subtrees are themselves BSTs, and duplicate keys are not allowed.

Left subtree values < root value

Right subtree values > root value

Both subtrees are BSTs

No duplicate keys

BST Traversal

Pre‑order (DLR) : visit root, then left subtree, then right subtree.

preOrderTraverse(node) {
  if (node) {
    this.visitNode(node);
    this.preOrderTraverse(node.left);
    this.preOrderTraverse(node.right);
  }
}

In‑order (LDR) : left subtree, root, right subtree.

inOrderTraverse(node) {
  if (node) {
    this.inOrderTraverse(node.left);
    this.visitNode(node);
    this.inOrderTraverse(node.right);
  }
}

Post‑order (LRD) : left subtree, right subtree, root.

postOrderTraverse(node) {
  if (node) {
    this.postOrderTraverse(node.left);
    this.postOrderTraverse(node.right);
    this.visitNode(node);
  }
}

Why Use a Red‑Black Tree?

Unlike plain BSTs, which can degenerate into a linked list (O(n) operations) in the worst case, red‑black trees remain balanced, ensuring O(log n) performance. They achieve balance through rotations and recoloring.

Red‑Black Tree Properties

Each node is either red or black.

The root is black.

All leaves (null) are black.

If a node is red, its children must be black (no two reds in a row).

Every path from a node to its descendant leaves contains the same number of black nodes.

Balancing Operations

Balancing is achieved via two mechanisms: rotations (left/right) and recoloring.

Left Rotation

/**
 * Left rotation example:
 *        P                     R
 *       / \                   / \
 *      L   R   ===>         P   RR
 *          / \             / \
 *         RL  RR         L   RL
 * @param node Rotation pivot
 */
rotateLeft(node) {
  // R
  const rchild = node.right;
  // P.right = RL
  node.right = rchild.left;
  if (rchild.left) {
    rchild.left.parent = node;
  }
  // R.parent = P.parent
  rchild.parent = node.parent;
  if (!node.parent) {
    this.root = rchild;
  } else {
    if (node === node.parent.right) {
      node.parent.right = rchild;
    } else {
      node.parent.left = rchild;
    }
  }
  // R.left = P
  rchild.left = node;
  node.parent = rchild;
}

Right Rotation

/**
 * Right rotation example:
 *        R                     P
 *       / \                   / \
 *      P   RR   ===>        L   R
 *     / \                     / \
 *    L   RL                 RL  RR
 * @param node Rotation pivot
 */
rotateRight(node) {
  const lchild = node.left;
  node.left = lchild.right;
  if (lchild.right) {
    lchild.right.parent = node;
  }
  lchild.parent = node.parent;
  if (!lchild.parent) {
    this.root = lchild;
  } else {
    if (node === node.parent.right) {
      node.parent.right = lchild;
    } else if (node === node.parent.left) {
      node.parent.left = lchild;
    }
  }
  lchild.right = node;
  node.parent = lchild;
}

Node Insertion Scenarios

Insertion can be broken into five cases, each requiring specific adjustments (rotations and/or recoloring) to preserve the red‑black properties.

Case 1 – Empty Tree: Insert the new node as the black root.

Case 2 – Duplicate Key: Replace the existing node's value and adopt its color.

Case 3 – Parent is Black: No further action needed.

Case 4 – Parent and Uncle are Red: Recolor parent and uncle black, grandparent red, then continue fixing from the grandparent.

Case 5 – Parent Red, Uncle Black (or null): Perform rotations (left or right) depending on the configuration, followed by recoloring.

Node Definition

/**
 * Node
 */
class Node {
  constructor(key, value, color = COLOR.RED) {
    this.key = key;
    this.value = value;
    this.color = color;
    this.left = null;
    this.right = null;
    this.parent = null;
  }
}

Insertion and Balancing Code

/**
 * Insert key, value
 */
insert(key, value) {
  if (this.root) {
    let parent;
    let node = this.root;
    const newNode = new Node(key, value, COLOR.RED);
    while (node) {
      parent = node;
      if (key === node.key) {
        newNode.color = node.color;
        this.update(node, newNode);
        return;
      } else if (key < node.key) {
        node = node.left;
      } else {
        node = node.right;
      }
    }
    newNode.parent = parent;
    if (key < parent.key) {
      parent.left = newNode;
    } else {
      parent.right = newNode;
    }
    this.balanceInsertion(newNode);
  } else {
    // Case 1: empty tree
    this.root = new Node(key, value, COLOR.BLACK);
  }
}

// Fix insertion violations
balanceInsertion(node) {
  while (node.parent != null && node.parent.color === COLOR.RED) {
    let uncle = null;
    if (node.parent === node.parent.parent.left) {
      uncle = node.parent.parent.right;
      if (uncle != null && uncle.color === COLOR.RED) {
        node.parent.color = COLOR.BLACK;
        uncle.color = COLOR.BLACK;
        node.parent.parent.color = COLOR.RED;
        node = node.parent.parent;
        continue;
      }
      if (node === node.parent.right) {
        node = node.parent;
        this.rotateLeft(node);
      }
      node.parent.color = COLOR.BLACK;
      node.parent.parent.color = COLOR.RED;
      this.rotateRight(node.parent.parent);
    } else {
      uncle = node.parent.parent.left;
      if (uncle != null && uncle.color === COLOR.RED) {
        node.parent.color = COLOR.BLACK;
        uncle.color = COLOR.BLACK;
        node.parent.parent.color = COLOR.RED;
        node = node.parent.parent;
        continue;
      }
      if (node === node.parent.left) {
        node = node.parent;
        this.rotateRight(node);
      }
      node.parent.color = COLOR.BLACK;
      node.parent.parent.color = COLOR.RED;
      this.rotateLeft(node.parent.parent);
    }
  }
  this.root.color = COLOR.BLACK;
}

Conclusion

This first part introduced the basic properties of red‑black trees, their search behavior, and detailed insertion operations with code examples. The next article will cover deletion, which also relies on rotations and recoloring.

Call to Action

If you found this article helpful, please click "In Review" to increase its visibility and follow the "Zhoucai Cloud Frontend Team" public account for more curated content.

Recruitment

The Zhoucai Cloud Frontend Team (ZooTeam) in Hangzhou is hiring passionate front‑end engineers. If you are interested, send your resume to [email protected] .