Consider these three rules:
- Transform any 2-node in the 2-3-4 tree into a black node in the red-black tree.
- Transform any 3-node into a child node and a parent node. The child node has two children of its own: either W and X or X and Y. The parent has one other child: either Y or W. It doesn’t matter which item becomes the child and which the parent. The child is colored red and the parent is colored black.
- Transform any 4-node into a parent and two children, the first child has its own children W and X; the second child has children Y and Z. As before, the children are colored red and the parent is black.
The red-black rules are automatically satisfied if you follow these rules. Here’s the resulting example tree after applying the transformations.
Hopefully that should get you going. For easy to understand and detailed explanation, you can refer to Robert Lafore’s Data Structures book.
