(Carrano, p. 569-72)

By adding one bit of information to the parent-child link (referred to a color for the red-black tree), we can represent a red-black tree as a binary tree.

• "Black" link:  this is a parent-child link in the 2-3-4 tree.

• "Red" link:  this is a link to a node that is conceptually part of a single 3-node or 4-node.  Leftward link is to a value less than the node value; rightward, to a value greater than the node value.

Traversal is straight BST traversal.

Splitting a 4-node is simply a matter of changing the two red links out of the middle value node into black links.  That may generate an illegal situation (if the parent is not a 2-node), which is handled by rotations and further color changes.

Contrary to Carrano's opinion on p. 577, however, I believe the AVL tree is appreciably easier to implement.

Consequently we will not pursue all the details of the red-black tree.