红黑树和2-3-4树是同构的吗？

Question

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

但是，我无法理解来自Wikipedia的这段文字：

“2-3-4树是红黑树的等距变换，这意味着它们是等效的数据结构。换句话说，对于每个2-3-4树，至少存在一个红黑树，其数据元素顺序相同。此外，导致节点扩展、分裂和合并的2-3-4树上的插入和删除操作等价于红黑树中的颜色翻转和旋转。”

我看不出这些操作是等价的。这段维基百科上的引文准确吗？如何看出这些操作是等价的？

- Lazer

---

似乎一个图表和真值表就足以证明或反驳这个问题。你做了吗？ - Warren P

数据结构的真值表？我不明白。。 - Lazer

一种映射方式，可以展示 2-叉树的操作，并与红黑树进行等价性展示。试试看。我认为 3-叉树是另一种情况，而 4-叉树则是另外一种情况。 - Warren P

Answer 1

红黑树（rb-tree）与2-3-4树不同构。这是因为如果我们尝试将2-3-4树中的3节点映射到红黑树中，它可以向左或向右倾斜。但是左倾红黑树（llrb-tree）可以做到这一点。

引用自Robert Sedgewick（位于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树”部分包含一张很好的图表。

- Lai Jiangshan