Как красно-черные деревья изоморфны 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

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

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