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

Question

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

Но я не в состоянии понять этот текст с Wikipedia

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

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

Answer 1

rb-tree (red-black-tree) не изоморфно 2-3-4-дереву. Поскольку 3-узел в 2-3-4-дереве может быть хуким слева или справа, если мы попытаемся сопоставить этот 3-узел с rb-деревом. Но llrb-дерево (левое-красно-черное дерево).

Слова из 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 

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

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