algorithm - 红黑树如何同构于 2-3-4 树？

Question

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

但是，我无法理解 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.

我不明白这些操作是如何等效的。维基百科上的这句话准确吗？如何看出操作是等价的？

Answer 1

rb-tree(red-black-tree) 与 2-3-4-tree 不同构。因为如果我们尝试将这个 3 节点映射到 rb 树，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

还有 presentation 的第 29 页和第 30 页|来自罗伯特·塞奇威克。这是关于 LLRB 树的介绍。

wikipedia 中“红黑树”的“4 阶 B 树类比”部分, 它包含一个很好的图表。