Fundamentals of Red-Black Trees
Learn subroutines of red-black trees and their relation with 2-4 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, , 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 having only black nodes.
Every internal node in 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 transformation. A black node that started out with two red children will have four children after this transformation. Furthermore, the black-height property now guarantees that every root-to-leaf path in has the same length. In other words, is a 2-4 tree!
The 2-4 tree ...