红黑树如何与2-3-4棵树同构？

Question

我对红黑树和2-3-4树都有基本的了解,以及它们如何保持高度平衡,以确保最坏情况下的操作是O(n logn).

但是,我无法理解维基百科的这篇文章

2-3-4树是红黑树的等轴测图,这意味着它们是等效的数据结构.换句话说,对于每2-3-4树,存在至少一个具有相同顺序的数据元素的红黑树.此外,2-3-4树上的插入和删除操作会导致节点扩展,拆分和合并,这相当于红黑树中的颜色翻转和旋转.

我不知道这些操作是如何相同的.维基百科上的引用是否准确？怎么能看到操作是等效的？

Answer 1

rb-tree(红黑树)与2-3-4树不同构.因为如果我们尝试将这个3节点映射到rb树,2-3-4树中的3节点可以向左或向右倾斜.但是llrb-tree(左倾红黑树)呢.

从词罗伯特·塞奇威克(在Introduction部分):

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

还有Robert Sedgewick 的演讲第 29页和第30页.这是关于LLRB树的演示文稿.

与维基百科中的"红黑树"中的"4类B树类比"一样,它包含了一个很好的图形.