Fundamentals of Red-Black Trees

Red-Black trees and 2-4 trees

At first it might seem surprising that a red-black tree can be efficiently updated to maintain the black-height and no-red-edge properties, and it seems unusual to even consider these as useful properties. However, red-black trees were designed to be an efficient simulation of $2$–$4$ trees as binary trees.

Refer to the below figure.

Consider any red-black tree, $T$, having $n$ nodes and perform the following transformation: Remove each red node u and connect u's two children directly to the (black) parent of u. After this transformation we are left with a tree $T'$ having only black nodes.

Every internal node in $T'$ has two, three, or four children: A black node that started out with two black children will still have two black children after this transformation. A black node that started out with one red and one black child will have three children after this ...