In che modo gli alberi rosso-neri sono isomorfi a 2-3-4 alberi?

Question

Ho una conoscenza di base sia degli alberi neri rossi che degli alberi 2-3-4 e di come mantengono il bilancio dell'altezza per garantire che le operazioni del caso peggiore siano O (n logn).

Ma, io non sono in grado di capire questo testo da Wikipedia

2-3-4 alberi sono un'isometria di alberi rosso-neri, nel senso che sono strutture di dati equivalenti. In altre parole, per ogni albero 2-3-4 esiste almeno un albero rosso-nero con elementi di dati nello stesso ordine. Inoltre, le operazioni di inserimento e cancellazione su 2-3-4 alberi che causano espansioni di nodi, divisioni e fusioni sono equivalenti al ribaltamento del colore e alla rotazione in alberi rosso-neri.

Non vedo come le operazioni siano equivalenti. Questa citazione su Wikipedia è accurata? Come si può vedere che le operazioni sono equivalenti?

Answer 1

albero rb (albero nero-rosso) non isomorfo a 2-3-4-albero. Perché il 3-nodo in 2-3-4-tree può essere snello a sinistra oa destra se proviamo a mappare questo 3-nodo a un albero-albero. Ma llrb-tree (albero rosso-nero a sinistra) lo fa.

Parole Robert Sedgewick (In Introduction sezione):

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 

anche Page29 e pagina 30 di presentation da Robert Sedgewick. Questa è una presentazione sull'albero LLRB.

E la sezione "Analogy to B-trees of 4" di "Red-black Tree" nello wikipedia contiene un buon grafico.