Как красно-черные деревья изоморфны 2-3-4 деревьям?

Question

У меня есть общее представление о красно-черных деревьях и 2-3-4 деревьях и о том, как они поддерживают баланс высоты, чтобы убедиться, что наихудшими операциями являются O(n logn).

Но я не могу понять этот текст из Википедии

2-3-4 дерева - это изометрия красно-черных деревьев, что означает, что они являются эквивалентными структурами данных. Другими словами, для каждого 2-3-4 дерева существует хотя бы одно красно-черное дерево с элементами данных в том же порядке. Более того, операции вставки и удаления на 2-3-4 деревьях, которые вызывают расширение, расщепление и слияние узлов, эквивалентны переворачиванию и повороту цветов в красно-черных деревьях.

Я не вижу, как операции эквивалентны. Точна ли эта цитата из Википедии? Как можно увидеть, что операции эквивалентны?

Answer 1

rb-дерево (красно-черное дерево) не изоморфно 2-3-4-дереву. Потому что 3-узел в 2-3-4-дереве может быть наклонен влево или вправо, если мы попытаемся отобразить этот 3-узел в rb-дерево. Но 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

Также Page29 и Page30 презентации от Роберта Седжвика. Это презентация о дереве LLRB.

И раздел "Аналогия с B-деревьями порядка 4" в "Красно-черном дереве" в википедии, он содержит хороший график.