Red-Black Trees

It is possible to represent 2-3-4 trees as standard binary trees
(2-nodes only) by using only one extra bit per node. The idea is to
represent 3-nodes and 4-nodes as small binary trees bound together 
by "red" links; these contrast with the "black links that bind 2-3-4
trees together.



We can represent the final 2-3-4 tree from figure 15.3 as a red-black
tree:





These trees have some proprties.