Understanding Red‑Black Trees: Principles, Insertion, Deletion, Rotations and Java TreeMap Implementation

Binary Tree

A binary tree is a hierarchical structure where each node has at most two children, conventionally called the left and right sub‑trees. The order of these sub‑trees is significant and cannot be swapped arbitrarily.

class Node
{
    T data;
    Node left;
    Node right;
}

Binary Search Tree (BST)

A BST is a special binary tree that maintains the ordering property: all keys in the left sub‑tree are smaller than the node’s key, and all keys in the right sub‑tree are larger. This property enables logarithmic‑time search, insertion, and deletion in the average case.

Balanced Binary Tree (AVL)

AVL trees are self‑balancing BSTs where the height difference between left and right sub‑trees of any node (the balance factor) does not exceed one. This guarantees O(log n) height and thus O(log n) operations.

Red‑Black Tree

Red‑black trees are another form of balanced BST, introduced by Rudolf Bayer in 1972. Each node stores an extra color bit (RED or BLACK) and must satisfy five properties:

Every node is either red or black.

The root is always black.

All leaves (null children) are black.

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

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

These constraints ensure that the longest path is at most twice the shortest path, providing a guaranteed O(log n) height.

Insertion

Insertion starts like a normal BST insertion; the new node is initially colored red. After insertion, the tree may violate red‑black properties, so a fix‑up procedure recolors nodes and performs rotations to restore balance. The algorithm distinguishes cases based on the colors of the new node’s parent, uncle, and grand‑parent.

Rotations

Rotations are local restructuring operations that preserve the BST ordering:

Left rotation : the right child of a node becomes its parent, and the original node becomes the left child of that new parent.

Right rotation : the left child of a node becomes its parent, and the original node becomes the right child of that new parent.

Four classic scenarios (LL, LR, RL, RR) combine a rotation with recoloring to fix specific violation patterns.

Deletion

Deletion is more complex because removing a black node can disturb the black‑height property. The algorithm handles three main cases:

Node to delete is a leaf – simply remove it and possibly recolor its sibling.

Node has a single non‑null child – replace the node with its child and adjust colors.

Node has two children – replace the node’s key with its in‑order predecessor or successor, then delete that replacement node using one of the previous cases.

After removal, a series of recolorings and rotations (similar to insertion fix‑up) restore the red‑black invariants.

Java Implementation (TreeMap)

In Java, the standard library implements a red‑black tree as java.util.TreeMap . Each entry is represented by an inner static class Entry that stores key, value, left/right/parent references and a color flag.

static final class Entry
implements Map.Entry
{
    K key;
    V value;
    Entry
left;
    Entry
right;
    Entry
parent;
    boolean color = BLACK; // RED or BLACK
    ...
}

The put method locates the proper insertion point, creates a new Entry , links it as a left or right child, and then calls fixAfterInsertion(e) to rebalance the tree.

public V put(K key, V value) {
    Entry
t = root;
    if (t == null) {
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    // ... locate insertion point using comparator or natural ordering ...
    Entry
e = new Entry<>(key, value, parent);
    if (cmp < 0) parent.left = e; else parent.right = e;
    fixAfterInsertion(e);
    size++; modCount++;
    return null;
}

The fixAfterInsertion routine implements the recoloring and rotation logic described earlier, ensuring the root is black at the end.

private void fixAfterInsertion(Entry
x) {
    x.color = RED;
    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry
y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            // symmetric case where parent is right child
            ...
        }
    }
    root.color = BLACK;
}

Through these mechanisms, Java’s TreeMap provides a reliable, log‑time ordered map backed by a red‑black tree.