我对红黑树和2-3-4棵树以及它们如何保持高度平衡有基本的了解，以确保最坏情况下的操作为O(n logn)。
但是，我无法从Wikipedia理解此文本
我看不到这些操作是如何等效的。维基百科上的这句话准确吗？怎么能看到这些操作是等效的？
最佳答案
rb-tree(red-black-tree)与2-3-4-tree不是同构的。因为如果我们尝试将此3节点映射到rb-tree，则2-3-4-tree中的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的presentation的Page29和Page30。这是有关LLRB树的演示。
wikipedia中“红黑树”的“对4阶B树的类比”部分包含一个不错的图。
关于algorithm - 红黑树如何与2-3-4树同构？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8765689/