我对红黑树和 2-3-4 树以及它们如何保持高度平衡以确保最坏情况下的操作为 O(n logn) 都有基本的了解。
但是，我无法理解来自维基百科的这段文字
2-3-4 树是红黑树的等距，这意味着它们是等效的数据结构。换句话说，对于每棵2-3-4树，至少存在一棵数据元素顺序相同的红黑树。而且，对2-3-4树的插入和删除操作会导致节点扩展、分裂和合并，相当于红黑树中的颜色翻转和旋转。
我看不出这些操作是如何等效的。维基百科上的这句话准确吗？怎么能看出这些操作是等价的呢？
问问题
2073 次
1 回答
5
rb-tree(red-black-tree) 不与 2-3-4-tree 同构。因为如果我们尝试将这个 3-node 映射到 rb-tree，2-3-4-tree 中的 3-node 可以向左或向右倾斜。但是 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树的类比”部分，它包含一个很好的图表。
于 2012-07-14T04:19:39.333 回答