Mastering Red-Black Trees: From BST Basics to Insertion, Deletion, and Rotations

Binary Search Tree (BST) Overview

A binary search tree stores keys so that for any node the left subtree contains only keys smaller than the node’s key and the right subtree contains only keys larger. The height of the tree determines operation cost: ideal height log₂N gives average‑case O(log N) for search, insertion and deletion; a degenerate chain of N nodes degrades to O(N).

// BST search
Node search(Node root, T key) {
    while (root != null) {
        if (key.equals(root.value)) return root;
        if (key.compareTo(root.value) < 0) {
            root = root.left;
        } else {
            root = root.right;
        }
    }
    return null;
}

// BST insertion (returns new root)
Node insert(Node root, Node node) {
    Node parent = null;
    while (root != null) {
        parent = root;
        if (node.value.compareTo(root.value) <= 0) {
            root = root.left;
        } else {
            root = root.right;
        }
    }
    if (parent == null) {
        return node; // tree was empty
    }
    if (node.value.compareTo(parent.value) <= 0) {
        parent.left = node;
    } else {
        parent.right = node;
    }
    return node; // caller may need to rebalance
}

Locate the node to delete.

If it is a leaf, remove it directly.

If it has two children, replace it with its in‑order successor (the smallest node in its right subtree) and delete that successor.

Why a Balanced BST?

Insertion order can produce highly unbalanced trees whose height approaches N, causing linear‑time operations. A balanced BST keeps height within a logarithmic factor of N, guaranteeing O(log N) performance.

Red‑Black Tree (RBT) Definition

Each node is colored either red or black.

The root is black.

Red nodes cannot have red children (no two consecutive reds).

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

Null leaves are considered black.

class Node<T> {
    T value;
    Node<T> parent;
    Node<T> left;
    Node<T> right;
    boolean isRed; // true = red, false = black
}

These constraints bound the height of an RBT to [log₂N, 2·log₂N], so search, insertion and deletion all run in O(log N) time.

Tree Rotations

Rotations restructure the tree while preserving the binary‑search‑tree order. They are the primitive operations used by the fix‑up phases.

// Left rotation around node x
void leftRotate(Node x) {
    Node y = x.right;          // y becomes new root of the subtree
    x.right = y.left;          // turn y's left subtree into x's right subtree
    if (y.left != null) y.left.parent = x;
    y.parent = x.parent;        // link x's parent to y
    if (x.parent == null) {
        // x was root
    } else if (x == x.parent.left) {
        x.parent.left = y;
    } else {
        x.parent.right = y;
    }
    y.left = x;
    x.parent = y;
}

// Right rotation around node y (mirror of leftRotate)
void rightRotate(Node y) {
    Node x = y.left;
    y.left = x.right;
    if (x.right != null) x.right.parent = y;
    x.parent = y.parent;
    if (y.parent == null) {
        // y was root
    } else if (y == y.parent.left) {
        y.parent.left = x;
    } else {
        y.parent.right = x;
    }
    x.right = y;
    y.parent = x;
}

Search in a Red‑Black Tree

Search uses the same algorithm as a plain BST (see the code above). The color information does not affect the search path.

Insertion Algorithm

Insertion proceeds in two phases:

Standard BST insertion : insert the new node as a red leaf using the BST insertion logic.

Fix‑up phase : while the parent of the inserted node is red, restore the red‑black properties. Three cases are considered, based on the color of the uncle and the relative orientation of the new node.

Case 1 – Uncle is red (recoloring)

Recolor parent and uncle to black, recolor grandparent to red, then continue the fix‑up from the grandparent.

Case 2 – Uncle is black and the new node forms a line (left‑left or right‑right)

Perform a rotation on the grandparent (right rotation for left‑left, left rotation for right‑right) and swap colors of parent and grandparent.

Case 3 – Uncle is black and the new node forms a triangle (left‑right or right‑left)

First rotate the parent to convert the configuration into Case 2, then apply the Case 2 steps.

After the appropriate case is handled, the algorithm climbs toward the root, recoloring the root black at the end.

Deletion Algorithm

Deletion also consists of two phases:

Standard BST deletion : remove the target node or replace it with its in‑order successor if it has two children.

Fix‑up phase : if a black node was removed, the black‑height property may be violated. The fix‑up examines the sibling of the node that replaced the deleted node and applies one of four cases.

Case 1 – Sibling is red

Rotate the parent toward the sibling, recolor sibling black and parent red, which transforms the situation into one of the remaining cases.

Case 2 – Sibling and sibling's children are black

Recolor the sibling red and move the fix‑up up to the parent.

Case 3 – Sibling is black, sibling's near child is red, far child is black

Rotate the sibling toward the far side and recolor to convert to Case 4.

Case 4 – Sibling is black and sibling's far child is red

Rotate the parent toward the sibling, recolor sibling black, and recolor the far child black (the former red child). This restores the black‑height property and terminates the fix‑up.

The fix‑up may propagate upward until the root is reached; the root is always recolored black.

Complexity Summary

Because a red‑black tree maintains height within a constant factor of log₂N, the three fundamental operations—search, insertion (including fix‑up), and deletion (including fix‑up)—all run in O(log N) time in the worst case.