How are red-black trees isomorphic to 2-3-4 trees?

Question

I have a basic understanding of both red black trees and 2-3-4 trees and how they maintain the height balance to make sure that the worst case operations are O(n logn).

But, I am not able to understand this text from Wikipedia

2-3-4 trees are an isometry of red-black trees, meaning that they are equivalent data structures. In other words, for every 2-3-4 tree, there exists at least one red-black tree with data elements in the same order. Moreover, insertion and deletion operations on 2-3-4 trees that cause node expansions, splits and merges are equivalent to the color-flipping and rotations in red-black trees.

I don't see how the operations are equivalent. Is this quote on Wikipedia accurate? How can one see that the operations are equivalent?

Seems like a diagram and a truth-table is enough to establish this, or refute this. Have you made one? — Warren P, Jan 13 '12 at 17:57
A mapping to show operations on 2-trees, to show equivalence to red-black trees. Try it. I assume 3-trees are another case, and 4-trees ye t another again. — Warren P, Jan 15 '12 at 03:01

Lai Jiangshan · Answer 1 · 2012-07-17T08:12:44.940

rb-tree(red-black-tree) is not isomorphic to 2-3-4-tree. Because the 3-node in 2-3-4-tree can be lean left or right if we try to map this 3-node to a rb-tree. But llrb-tree(Left-leaning red-black tree) does.

Words from Robert Sedgewick(In Introduction section):

In particular, the paper describes a way to maintain 
a correspondence between red-black trees and 2-3-4 trees, 
by interpreting red links as internal links in 3-nodes and 
4-nodes.  Since red links can lean either way in 3-nodes 
(and, for some implementations in 4-nodes), the correspondence is not necessarily 1-1

Also Page29 and Page30 of presentation from Robert Sedgewick. This a presentation about LLRB tree.

And "Analogy to B-trees of order 4" section of "Red-black Tree" in the wikipedia, it contains a good graph.

How are red-black trees isomorphic to 2-3-4 trees?

1 Answers1