Red-Black Tree Rotations Explained: Self-Balancing Trees in Java

Stock trading engines process millions of orders arriving sequentially with monotonically increasing transaction IDs (1001, 1002, 1003...).

In Part 13, we discovered that inserting sorted data into a standard Binary Search Tree causes the tree to collapse into a long, single line.

Instead of taking 20 steps to search a 1,000,000-item tree, your system executes 1,000,000 steps. Your server CPU spikes to 100%, and incoming trade executions freeze.

This production failure is why Java’s TreeMap, TreeSet, and HashMap (JDK 8+ bucket treeification) rely on Red-Black Trees.

---

The Self-Balancing Guarantee

A Red-Black tree is a binary search tree where every node carries a color attribute: RED or BLACK.

By enforcing color rules during insertions and deletions, the tree guarantees that no path from root to leaf is more than twice as long as any other path. Search time remains strictly bounded to $O(\log N)$.

               [ 30 (BLACK) ]
              /              \
     [ 20 (BLACK) ]       [ 40 (BLACK) ]
     /
[ 10 (RED) ]

---

The 5 Red-Black Invariants

To keep the tree balanced, the JVM enforces five rules:

1. Every node is either RED or BLACK.
2. The root node is always BLACK.
3. All leaf nodes (null references) are treated as BLACK.
4. If a node is RED, both of its children must be BLACK. (No two consecutive RED nodes on any path).
5. Every path from a node to any descendant null leaf contains the exact same number of BLACK nodes. (Black-height equality).

When a new insertion violates Rule 4 (two consecutive RED nodes), the tree restores balance using two operations: recoloring and rotations.

---

Tree Rotations: Changing Shape Without Breaking BST Order

A rotation alters the parent-child pointer relationships of three nodes while preserving the binary search tree ordering invariant ($Left < Parent < Right$).

Left Rotation

A left rotation pivots a node down to the left, raising its right child to take its place.

BEFORE LEFT ROTATE on Node X:

      X                                Y
     / \                             /   \
    A   Y     == Left Rotate ==>    X     C
       / \                         / \
      B   C                       A   B

Notice that binary search order is strictly preserved: $A < X < B < Y < C$.

private Node leftRotate(Node x) {
    Node y = x.right;
    x.right = y.left;
    if (y.left != null) {
        y.left.parent = x;
    }
    y.parent = x.parent;
    if (x.parent == null) {
        root = y;
    } else if (x == x.parent.left) {
        x.parent.left = y;
    } else {
        x.parent.right = y;
    }
    y.left = x;
    x.parent = y;
    return y;
}

---

Right Rotation

A right rotation pivots a node down to the right, raising its left child to take its place.

BEFORE RIGHT ROTATE on Node Y:

        Y                            X
       / \                         /   \
      X   C   == Right Rotate ==> A     Y
     / \                               / \
    A   B                             B   C

private Node 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) {
        root = x;
    } else if (y == y.parent.left) {
        y.parent.left = x;
    } else {
        y.parent.right = x;
    }
    x.right = y;
    y.parent = x;
    return x;
}

---

Insertion Fixup Logic

When inserting a new node, we always insert it as RED.

If the parent of the new node is also RED, we have a double-red violation. We examine the uncle node (the sibling of the parent):

• Case 1: Uncle is RED $\rightarrow$ Recolor parent and uncle to BLACK, recolor grandparent to RED, and move inspection up to grandparent.
• Case 2: Uncle is BLACK (Triangle shape) $\rightarrow$ Rotate parent to transform into line shape.
• Case 3: Uncle is BLACK (Line shape) $\rightarrow$ Rotate grandparent and recolor.

CONSECUTIVE RED VIOLATION:

         [ 50 (BLACK) ]  (Grandparent)
        /
   [ 30 (RED) ]         (Parent)
  /
[ 10 (RED) ]            (Newly inserted child)

== Right Rotate Grandparent & Recolor ==

         [ 30 (BLACK) ]
        /              \
  [ 10 (RED) ]    [ 50 (RED) ]

---

Quick Summary

• Standard BSTs degrade to $O(N)$ when data arrives pre-sorted.
• Red-Black trees maintain balance via 5 color rules, guaranteeing $O(\log N)$ worst-case performance.
• Rotations rearrange pointer links to reduce tree height without breaking binary search ordering.

References & Further Reading

1. Goetz, B., et al. (2006). Java Concurrency in Practice — Chapter 5: CopyOnWriteArrayList. Addison-Wesley.
2. OpenJDK Repository. OpenJDK 21 Source Code: java.util.concurrent.CopyOnWriteArrayList. GitHub.
3. Oracle Corporation. Java SE 21 API Documentation: java.util.concurrent.CopyOnWriteArraySet. Oracle Docs.

---