Master Red-Black Trees: Definitions, Properties, and Insertion/Deletion Walkthrough

Red‑Black Tree Definition and Properties

A red‑black tree is a self‑balancing binary search tree that satisfies the following five properties:

Each node is either red or black.

The root node is black.

All leaf nodes (the NIL sentinel nodes) are black.

Red nodes have black children (no two red nodes appear consecutively on a path).

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

Property 5 guarantees a black‑perfect balance : the tree may be height‑unbalanced, but the number of black nodes on any root‑to‑leaf path is identical, which bounds the height to O(log N).

Rotations and Recoloring

Balancing is achieved through three primitive operations:

Left rotation : the right child of a pivot becomes the new parent; the pivot’s right‑child’s left subtree becomes the pivot’s right subtree.

Right rotation : symmetric to left rotation.

Recoloring : change a node’s color from red to black or vice‑versa.

Search in a Red‑Black Tree

The search algorithm is identical to that of an ordinary binary search tree because it never modifies the structure.

Node* RBSearch(Node* root, Key k) {
    Node* cur = root;
    while (cur != NIL) {
        if (k == cur->key) return cur;
        cur = (k < cur->key) ? cur->left : cur->right;
    }
    return nullptr; // not found
}

Time complexity: O(log N) in the worst case.

Insertion

Insertion consists of two phases:

BST insertion : locate the appropriate NIL leaf using the same steps as RBSearch and insert a new node I there. The new node is coloured red because inserting a red child under a black parent does not violate the black‑height property.

Fix‑up : restore the red‑black properties. The fix‑up algorithm examines the colour of I ’s parent P and proceeds as follows:

Case 1 – Tree is empty : insert I as the root and recolour it black.

Case 2 – Key already exists : replace the existing node’s value and adopt its colour (no structural changes).

Case 3 – Parent P is black : the tree already satisfies all properties; no further action is required.

Case 4 – Parent P is red (violates property 4). Let U be the uncle of I and G the grandparent.

4.1 – Uncle U is red : recolour P and U black, recolour G red, then set I = G and repeat the fix‑up (this may propagate upward).

4.2 – Uncle U is black (or NIL) and I is a left child of a left‑child parent : recolour P black, recolour G red, and perform a right rotation on G.

4.3 – Uncle U is black and I is a right child of a left‑child parent : perform a left rotation on P to transform into case 4.2, then apply the steps of 4.2.

Symmetric cases exist when I lies in the right subtree (mirror the actions of 4.2 and 4.3).

After the appropriate recolouring and rotations, the tree satisfies all five red‑black properties.

Deletion

Deletion also has two phases:

BST deletion : locate the node D to delete. If D has two children, replace it with its in‑order successor (the smallest node in the right subtree) or predecessor; the replacement node R is treated as the node actually removed.

Fix‑up : if the removed node (or the replacement node) was black, the black‑height property may be violated. The algorithm examines the sibling S of the node that replaced D (or the NIL leaf that took its place) and proceeds through the following cases (mirrored for left/right):

Case 1 – Replacement node is red : simply recolour it black.

Case 2 – Sibling S is red : recolour S black, recolour the parent P red, and perform a rotation (left if R is a left child, right otherwise). This transforms the situation into one of the subsequent cases where the sibling is black.

Case 3 – Sibling S is black and both of S ’s children are black : recolour S red and move the fix‑up problem up to the parent P (repeat the algorithm on P).

Case 4 – Sibling S is black, the far child of S is black and the near child is red : recolour the near child black, recolour S red, and rotate around S (right rotation if R is a left child, left otherwise). This converts the configuration to Case 5.

Case 5 – Sibling S is black and the far child of S is red : recolour S with the colour of P, recolour P black, recolour the far child black, and rotate around P (left rotation if R is a left child, right otherwise). The tree is now balanced.

These nine cases (including left/right symmetry) guarantee that after deletion the tree again satisfies all red‑black properties.

Online Red‑Black Tree Visualizer

For interactive experimentation, use the following URL (copy‑paste into a browser): https://sandbox.runjs.cn/show/2nngvn8w