Why Red-Black Trees Beat AVL: Insertion, Deletion, and Java TreeMap

This article explains the classic implementation of red‑black trees, which Java’s TreeMap uses.

It first asks why red‑black trees are more widely applied than AVL trees, noting that under arbitrary sequences of insertions and deletions the amortized cost of red‑black trees remains O(1) while AVL trees incur O(log n) for deletions.

Red‑black trees are isomorphic to 2‑3‑4 search trees, offering lower balancing overhead than left‑leaning red‑black trees.

2‑3‑4 Search Tree

A 2‑3‑4 search tree extends a 2‑3 tree by adding 4‑nodes. Inserting a new key into a 4‑node requires first splitting the 4‑node into three 2‑nodes, then inserting the key into the appropriate 2‑node.

Further insertion cases for 2‑nodes, 3‑nodes, and 4‑nodes are illustrated with diagrams.

Classic Red‑Black Tree

The classic red‑black tree satisfies the following properties:

Each node is either red or black.

The root is black.

All leaf (null) nodes are black.

Red nodes have black children (no two consecutive red nodes).

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

Because a red‑black tree is a representation of a 2‑3‑4 tree, the black links correspond to the ordinary links of a 2‑3‑4 tree, guaranteeing perfect balance.

Node Definition

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;
    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
    // ...
}

Insertion

Insert into a 2‑node

Inserting into a 2‑node is straightforward; the 2‑node becomes a 3‑node.

Insert into a 3‑node

Insertion into a 3‑node requires handling left‑leaning and right‑leaning cases, potentially converting the node into a 4‑node.

Insert into a 4‑node

When inserting into a 4‑node, the node is split into three 2‑nodes and the appropriate 2‑node receives the new key, after which the split node is merged upward.

The Java TreeMap insertion method is shown below; note the call to fixAfterInsertion for rebalancing.

public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        compare(key, key);
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0) t = t.left;
            else if (cmp > 0) t = t.right;
            else return t.setValue(value);
        } while (t != null);
    } else {
        if (key == null) throw new NullPointerException();
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0) t = t.left;
            else if (cmp > 0) t = t.right;
            else return t.setValue(value);
        } while (t != null);
    }
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0) parent.left = e;
    else parent.right = e;
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

The fixAfterInsertion method recolors nodes and performs rotations to restore red‑black properties.

private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED;
    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry<K,V> 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 {
            Entry<K,V> y = leftOf(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 == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    root.color = BLACK;
}

Deletion

Deletion is the most complex operation. Removing a red node (3‑node or 4‑node) does not affect balance, while deleting a black 2‑node requires rebalancing.

Four cases are considered based on the sibling’s color and children’s colors, each involving recoloring and rotations to restore black‑balance.

Java TreeMap deletion method:

public V remove(Object key) {
    Entry<K,V> p = getEntry(key);
    if (p == null) return null;
    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
}

The supporting deleteEntry and fixAfterDeletion methods handle node replacement and rebalancing.

private void fixAfterDeletion(Entry<K,V> x) {
    while (x != root && colorOf(x) == BLACK) {
        if (x == leftOf(parentOf(x))) {
            Entry<K,V> sib = rightOf(parentOf(x));
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateLeft(parentOf(x));
                sib = rightOf(parentOf(x));
            }
            if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                if (colorOf(rightOf(sib)) == BLACK) {
                    setColor(leftOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateRight(sib);
                    sib = rightOf(parentOf(x));
                }
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(rightOf(sib), BLACK);
                rotateLeft(parentOf(x));
                x = root;
            }
        } else {
            // mirror image of the above (omitted for brevity)
        }
    }
    setColor(x, BLACK);
}

The deletion algorithm runs in O(log n) time; the rebalancing loop performs at most three rotations and may climb the tree O(log n) levels.

References

CLRS, Chapter 13 – Red‑Black Trees

Zhihu discussion on AVL vs. red‑black trees

LeetCode “Red‑Black Tree from Beginner to Advanced”

Blog post “Red‑Black Tree Deletion”