Un albero Red-Black è un albero binario di ricerca in cui:

• ogni nodo contiene (oltre ad un valore) un campo colore (rosso-nero) che indica il colore del lato che lo collega al padre
• non ci sono due lati rossi consecutivi (il cammino da un qualunque nodo a un nipote di quel nodo ha almeno un lato nero)
• ogni cammino dalla radice ad una foglia ha lo stesso numero di lati neri

Corrispondenza 2-3-4 / R-B:

Lemma: Sia T un albero 2-3-4 di altezza h. Allora ogni albero RB equivalente a T ha altezza al massimo 2h

Dimostrazione: per attraversare (il corrispondente di) un nodo 2-3-4 in un albero RB servono al massimo due lati

Dal lemma precedente segue che un albero RB con n valori ha altezza $O(\log n)$. La famiglia degli alberi RB è quindi bilanciata

Quanti alberi R-B sono traducibili nell'albero 2-3-4 qui sopra?

Ogni nodo con 2 link di colore diverso rappresenta un 3-nodo. Ogni 3-nodo può essere rappresentato in 2 modi, quindi $2^{\text{\#3-nodi}}$

nel caso specifico $2^4=16$

Scomposizione

La scomposizione di un 4-nodo nella sua rappresentazione RB avviene con una semplice inversione dei colori (in 3 nodi)!

Caso facile: figlio di un 2-nodo