Red-Black Tree Data Structure Tutorial

What Is a Red-Black Tree?

A Red-Black Tree is a self-balancing binary search tree in which every node has an additional color: red or black. The color rules are used to control the height of the tree and prevent it from becoming excessively skewed.

Like other binary search trees, a Red-Black Tree keeps smaller values in the left subtree and larger values in the right subtree. The difference is that it uses a set of balancing rules to maintain a controlled tree height after insertions and deletions.

Red-Black Trees are particularly useful when a data structure needs efficient searching, insertion, and deletion while maintaining balance dynamically.

Red-Black Tree Properties

A valid Red-Black Tree follows a set of properties that determine how red and black nodes can appear in the tree.

Every node is either red or black.
The root of the tree is black.
Every null leaf is considered black.
A red node cannot have a red child.
Every path from a node to its descendant null leaves contains the same number of black nodes.

These rules do not require every path to have exactly the same length. Instead, they place restrictions on how red and black nodes can be arranged, which keeps the tree approximately balanced.

Why Does the Color Matter?

The colors are not used to order values. They are used as balancing information. A Red-Black Tree can temporarily become structurally uneven after an insertion or deletion, but its color rules ensure that the imbalance remains bounded.

Without balancing, inserting sorted values into a binary search tree could produce a structure similar to a linked list:

A Red-Black Tree uses recoloring and rotations to prevent this type of unbounded skew.

Basic Red-Black Tree Structure

A node typically stores its value, color, and references to its children. Implementations may also store a reference to the parent node.

class RBNode {
  constructor(value, color = 'RED') {
    this.value = value;
    this.color = color;
    this.left = null;
    this.right = null;
    this.parent = null;
  }
}

A production implementation commonly uses a shared black sentinel node instead of storing JavaScript null references for every leaf.

Red and Black Nodes

The color of a node is part of the balancing state. A red node cannot have a red child. This restriction prevents long chains of red nodes from forming.

       20(B)
       /   \
    10(R)  30(R)

This structure satisfies the rule that a red node cannot directly have another red node as a child.

Black Height

Black height is the number of black nodes encountered along a path from a node to a descendant leaf, following the convention used by the particular implementation. Red-Black Tree balancing requires corresponding paths to have the same black height.

This property is important because it limits how much longer one root-to-leaf path can be compared with another.

How Red-Black Trees Stay Balanced

Red-Black Trees use two main techniques to repair violations:

Recoloring changes a node from red to black or black to red.
Rotation changes the structure of a subtree while preserving BST ordering.

In many insertion cases, recoloring is enough. In other cases, rotations are required to restore the required properties.

Rotations in a Red-Black Tree

Red-Black Trees use the same fundamental left and right rotations used by other balanced binary search trees.

Left Rotation

    x                         y
     \                       / \
      y          →          x   T3
     / \                   / \
    T2  T3                 T1  T2
   /
  T1

A left rotation moves the right child upward and moves the original node downward to the left.

Right Rotation

        y                    x
       / \                  / \
      x   T3      →        T1  y
     / \                      / \
    T1  T2                    T2  T3

A right rotation moves the left child upward and moves the original node downward to the right.

Red-Black Tree Insertion

Insertion begins like a normal binary search tree insertion. The newly inserted node is initially colored red.

New nodes are generally inserted as red because inserting a black node could immediately increase the black count on paths through that node. A red insertion can instead create a local red-red violation that can be repaired.

After insertion, the tree checks for violations and applies recoloring or rotations when necessary.

Insertion Case: Root Node

If the inserted node becomes the root, it must be colored black because the root property requires the root to be black.

Before:

10(R)

After:

10(B)

Insertion Case: Red Parent

A newly inserted red node creates a violation if its parent is also red. The repair depends on the color of the node's uncle.

If the parent and uncle are both red, recoloring can move the problem upward:

        20(B)
       /    \
    10(R)  30(R)
    /
   5(R)

The parent and uncle can be recolored black, while the grandparent may become red. The repair process then continues upward if necessary.

Insertion Case: Black Uncle

When the uncle is black and a red-red violation exists, rotations are used. The required rotation depends on the shape of the subtree.

For a straight-line configuration, a single rotation can resolve the structural problem. For a zig-zag configuration, the first rotation converts it into a straight-line case, followed by another rotation.

Example of Recoloring

Consider inserting 10, 20, and 30 into a Red-Black Tree. After ordinary BST insertion, the structure can temporarily contain a red parent and red child.

10(B)
   \
   20(R)
      \
      30(R)

The red-red violation is repaired using a rotation and recoloring, producing a balanced structure:

      20(B)
     /    \
  10(R)  30(R)

Red-Black Tree Deletion

Deletion is more complicated than insertion because removing a black node can change the black height of paths through the tree.

A deletion generally starts with the normal binary search tree deletion process. The balancing algorithm then examines the colors of the deleted node, its replacement, its sibling, and related nodes.

Depending on the situation, deletion repair can involve recoloring, rotations, or both. Some implementations describe the temporary imbalance as a "double black" condition.

Red-Black Tree Search

Searching works exactly like searching in a binary search tree. At each node, compare the target value with the current node and move left or right accordingly.

function search(root, value) {
  let current = root;

  while (current !== null) {
    if (value === current.value) {
      return current;
    }

    if (value < current.value) {
      current = current.left;
    } else {
      current = current.right;
    }
  }

  return null;
}

Red-Black Tree Complexity

The balancing rules keep the height of a Red-Black Tree logarithmic relative to the number of nodes. As a result, search, insertion, and deletion have logarithmic worst-case complexity.

Operation	Average / Typical	Worst Case
Search	O(log n)	O(log n)
Insertion	O(log n)	O(log n)
Deletion	O(log n)	O(log n)
Rotation	O(1)	O(1)

Red-Black Tree vs AVL Tree

Both Red-Black Trees and AVL Trees are self-balancing binary search trees, but they use different balancing strategies.

Characteristic	Red-Black Tree	AVL Tree
Balancing method	Colors, rotations, and recoloring	Height and rotations
Balance strictness	Less strictly height-balanced	More strictly height-balanced
Search	O(log n)	O(log n)
Insertion	O(log n)	O(log n)
Deletion	O(log n)	O(log n)

Where Red-Black Trees Are Used

Red-Black Trees are useful when a system needs an ordered collection with predictable logarithmic operations while allowing frequent insertions and deletions.

Ordered maps and sets
In-memory indexing structures
Operating-system data structures
Language-library implementations
Schedulers and systems that maintain ordered data
Applications requiring dynamic sorted collections

Common Implementation Mistakes

Forgetting that the root must be black.
Allowing a red node to have a red child.
Ignoring the black-height property.
Forgetting to update parent references after rotations.
Using the wrong rotation direction during insertion repair.
Failing to recolor nodes after rotations.
Treating null leaves as ordinary missing references without considering their black status.
Implementing deletion without handling black-height violations.

When to Learn Red-Black Trees

Red-Black Trees are an important advanced data structure because they combine the ordering behavior of binary search trees with guaranteed logarithmic-height balancing.

Before implementing one from scratch, it helps to understand binary search trees, tree rotations, AVL trees, recursion, and tree traversal. Once those concepts are familiar, Red-Black Tree insertion and deletion become easier to reason about.

Key Takeaways

A Red-Black Tree is a self-balancing binary search tree.
Every node is either red or black.
The root must be black.
A red node cannot have a red child.
Every root-to-leaf path maintains the required black-height property.
Rotations change the tree structure while preserving BST ordering.
Recoloring and rotations are used to repair balancing violations.
Search, insertion, and deletion take O(log n) worst-case time.
Red-Black Trees are useful for dynamic ordered collections.

Topics

Red-Black Tree Data Structure