¿Cómo son los árboles rojo-negro isomorfos a 2-3-4 árboles?

Question

Tengo una comprensión básica de árboles de color rojo-negro y 2-3-4 árboles y cómo mantienen el equilibrio de altura para asegurarse de que las operaciones en el peor de los casos sean O (n logn).

Pero, no soy capaz de entender este texto de Wikipedia

2-3-4 árboles son una isometría de árboles rojo-negro, que significa que son estructuras de datos equivalentes. En otras palabras, para cada árbol 2-3-4, existe al menos un árbol rojo-negro con elementos de datos en el mismo orden. Además, las operaciones de inserción y eliminación en 2-3-4 árboles que causan expansiones, divisiones y fusiones de nodo son equivalentes a los cambios de color y las rotaciones en árboles rojo-negro.

No veo cómo las operaciones son equivalentes. ¿Es esta cita en Wikipedia precisa? ¿Cómo puede uno ver que las operaciones son equivalentes?

Answer 1

rb-tree (red-black-tree) no es isomorfo a 2-3-4-tree. Debido a que el 3-node en 2-3-4-tree puede inclinarse hacia la izquierda o hacia la derecha si tratamos de asignar este 3-node a un árbol-rb. Pero llrb-tree (árbol rojo-negro de inclinación hacia la izquierda) sí.

Palabras de Robert Sedgewick (En Introduction sección):

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 

También pág29 y pág30 de presentation de Robert Sedgewick. Esta es una presentación sobre el árbol LLRB.

Y la sección "Analogy to B-trees of order 4" de "Red-black Tree" en el wikipedia, contiene un buen gráfico.