Master Red-Black Trees: Definitions, Operations, and Java Implementation

1. Definition

Red‑Black Tree is a special binary search tree with the following properties:

Each node is either red or black.

The root node is black.

All leaf nodes are black and represent null (sentinel) nodes.

If a node is red, both of its children are black.

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

Note: In Java implementations null is used for leaf nodes, so visible leaf nodes appear red.

Additional observations:

Property 3 means that the black‑height of a red‑black tree is at most twice the minimum black‑height, limiting the longest path to at most twice the shortest.

2. Operations

2.1 Insertion

When inserting a new node it is initially colored red. Depending on the colors of its parent and uncle, several cases arise.

Case 1 – Black parent

No violation; the tree remains valid.

Case 2 – Red parent (uncle is black)

Four sub‑cases require rotations and recoloring:

Case 1: Right‑rotate then recolor

Case 2: Left‑rotate, then right‑rotate and recolor

Case 3: Left‑rotate then recolor

Case 4: Right‑rotate, left‑rotate then recolor

Insertion consists of locating the position and then fixing violations using the cases above.

2.2 Deletion

Deletion handles three situations:

Removing a leaf node.

Removing a node with one child (the child replaces the node).

Removing a node with two children (replace with its in‑order successor, then delete the successor).

After removal, the tree may violate red‑black properties and removeFixUp is invoked to restore balance.

private void insert(RBTreeNode<T> node) {
    // insertion algorithm (traversal, placement)
    // ...
    node.color = COLOR_RED;
    insertFixUp(node);
}

private void insertFixUp(RBTreeNode<T> node) {
    // recoloring and rotations to restore properties
}

private void remove(RBTreeNode<T> node) {
    // deletion algorithm with cases and fix‑up
}

private void removeFixUp(RBTreeNode<T> node, RBTreeNode<T> parent) {
    // recoloring and rotations to restore properties
}

3. Summary

The article presented the essential properties of red‑black trees, detailed insertion and deletion cases with diagrams, and provided Java code snippets for the core operations. Understanding these mechanisms helps maintain balanced binary search trees with O(log n) operations.