Alberi rosso-neri

Algoritmi · Strutture dati bilanciate

Alberi rosso-neri

Un albero rosso-nero è un albero binario di ricerca che limita lo sbilanciamento usando colori, ricolorazioni e rotazioni. Non è perfettamente bilanciato, ma garantisce altezza logaritmica.

Dal BST semplice a una garanzia nel caso peggiore

Un BST costruito inserendo chiavi ordinate può degenerare in una catena alta n. Un albero rosso-nero conserva la proprietà BST e impone vincoli sui colori lungo i cammini: nessun cammino può diventare più del doppio di un altro.

Ordine

Le chiavi restano organizzate come in qualsiasi BST; l’in-order è crescente.

Colore

Ogni nodo aggiunge un solo bit logico: rosso oppure nero.

Riparazione locale

Dopo una modifica bastano ricolorazioni e un numero costante di rotazioni.

I cinque invarianti rosso-neri

1
Ogni nodo è rosso oppure nero.
2
La radice è nera.
3
Ogni foglia NIL, cioè ogni puntatore vuoto, è nera.
4
Un nodo rosso ha padre e figli neri: non esistono due rossi consecutivi.
5
Da un nodo a ogni NIL discendente passa lo stesso numero di nodi neri: la black-height.

Convenzione sulle NIL. Nel disegno i puntatori vuoti non sono mostrati, ma il verificatore li conta come foglie nere. Questa convenzione rende uniformi invarianti e algoritmi.

Laboratorio: osserva il fix-up

Ogni nuova chiave entra rossa. Avanza passo passo per vedere quale violazione compare e come ricolorazioni e rotazioni la spostano o la eliminano.

Velocità1×

Nodi: 0
Altezza: 0
Black-height: 0
Rotazioni: 0
Ricolorazioni: 0

BST-INSERT(T, z) z.color ← RED
while color(parent(z)) = RED
if color(uncle(z)) = RED color(parent(z)) ← BLACK color(uncle(z)) ← BLACK color(grandparent(z)) ← RED z ← grandparent(z)
else
if z is an inner child z ← parent(z) rotate z toward the line configuration
color(parent(z)) ← BLACK color(grandparent(z)) ← RED
rotate grandparent(z) to promote parent(z)
T.root.color ← BLACK

nodo rosso nodo nero nodo corrente z modificato nel passo

Inserire come in un BST, poi riparare

Trova una foglia NIL con la normale ricerca BST e collega il nuovo nodo.
Coloralo rosso: così la black-height di tutti i cammini resta invariata.
Se il padre è nero e il nuovo nodo non è la radice, gli invarianti sono già soddisfatti.
Se il padre è rosso, esamina zio e forma geometrica; applica il fix-up.
Alla fine forza la radice nera.

Perché il nuovo nodo è rosso? Inserirlo nero aumenterebbe immediatamente la black-height di un solo cammino. Inserirlo rosso può violare la regola rosso–rosso oppure il colore della radice se l’albero era vuoto: entrambe sono anomalie locali.

Inserimento: i tre casi, passo per passo

Chiamiamo z il nodo corrente, p suo padre, g il nonno e u lo zio, cioè l’altro figlio di g. Entriamo nel ciclo solo se p è rosso; g esiste ed è nero. Descriviamo prima p = g.left. Un puntatore NIL vale come zio nero.

Negli schemi B = nero, R = rosso; i NIL neri sono omessi. Gli stati intermedi possono violare temporaneamente gli invarianti.

Caso 1 · Zio rosso: sposta il problema verso l’alto

Condizione: p e u sono rossi. Ricolora p e u di nero e g di rosso, poi assegna z ← g. Non serve alcuna rotazione.

       20B                     20R ← z
      /   \                   /   \
    10R   30R      →        10B   30B
    /                       /
   5R ← z                  5R

Perché funziona: ogni cammino che attraversa g perde il nero di g ma guadagna quello di p oppure di u, quindi il numero di neri resta uguale. La coppia rossa originaria scompare; può comparirne una tra g e il suo padre. Il ciclo riparte più in alto. Se g è la radice, la ricolorazione finale a nero chiude la riparazione.

Caso 2 · Zio nero e triangolo: prepara il caso 3

Condizione: u è nero e z è il figlio destro di p, mentre p è figlio sinistro di g: configurazione sinistra–destra. Assegna z ← p e ruota a sinistra su z. La rotazione non cambia i colori.

      30B                   30B
      /                     /
    10R         →         20R
      \                   /
      20R ← z           10R ← z

Esito: ora z è figlio sinistro di un padre sinistro. La coppia rosso–rosso esiste ancora, ma è allineata: esegui subito il caso 3, nella stessa iterazione. Dopo la rotazione vanno riletti padre e nonno del nuovo z.

Caso 3 · Zio nero e linea: termina la riparazione

Condizione: u è nero e z è figlio sinistro di p, a sua volta figlio sinistro di g. Colora p di nero e g di rosso, poi ruota a destra su g. Il padre viene promosso a radice del sottoalbero.

      30B                  20B
      /                   /   \
    20R         →       10R   30R
    /
  10R ← z

Perché termina: il nuovo padre di z è nero, l’ordine in-order è invariato e i sottoalberi mantengono lo stesso contributo nero verso l’esterno. Non si propaga alcuna violazione al padre del sottoalbero. Il ciclo termina.

Casi speculari: quando p è figlio destro di g
Caso	Condizione	Operazione
1	Zio sinistro rosso	Stesse ricolorazioni; z ← g
2	Zio nero, z figlio sinistro di p	z ← p; RIGHT-ROTATE(T, z)
3	Zio nero, z figlio destro di p	p.color ← BLACK; g.color ← RED; LEFT-ROTATE(T, g)

Da ricordare: il caso 1 può ripetersi O(log n) volte; il caso 2 conduce al 3, che termina. Per un inserimento si eseguono al massimo due rotazioni.

Pseudocodice completo dell’inserimento

Usiamo z.p per il padre. La sentinella NIL è nera e il padre della radice è NIL. BST-INSERT collega un nuovo nodo aggiornandone il padre; restituisce NIL se la chiave è già presente. Le rotazioni aggiornano anche genitori e radice. Chiavi duplicate ignorate, come nel laboratorio.

RB-INSERT(T, key)
    z ← BST-INSERT(T, key)
    if z = NIL
        return                  // duplicate key
    z.left ← NIL
    z.right ← NIL
    z.color ← RED
    RB-INSERT-FIXUP(T, z)

RB-INSERT-FIXUP(T, z)
    while z.p.color = RED
        if z.p = z.p.p.left
            u ← z.p.p.right
            if u.color = RED                 // case 1
                z.p.color ← BLACK
                u.color ← BLACK
                z.p.p.color ← RED
                z ← z.p.p
            else
                if z = z.p.right             // case 2
                    z ← z.p
                    LEFT-ROTATE(T, z)
                z.p.color ← BLACK            // case 3
                z.p.p.color ← RED
                RIGHT-ROTATE(T, z.p.p)
        else
            u ← z.p.p.left
            if u.color = RED                 // mirror 1
                z.p.color ← BLACK
                u.color ← BLACK
                z.p.p.color ← RED
                z ← z.p.p
            else
                if z = z.p.left              // mirror 2
                    z ← z.p
                    RIGHT-ROTATE(T, z)
                z.p.color ← BLACK            // mirror 3
                z.p.p.color ← RED
                LEFT-ROTATE(T, z.p.p)
    T.root.color ← BLACK

Perché l’altezza resta logaritmica

Definiamo bh(x) come il numero di nodi neri da x a un NIL discendente, escludendo x e includendo NIL; bh(NIL) = 0. Per induzione, un sottoalbero radicato in x contiene almeno 2^bh(x) − 1 nodi interni: ciascun figlio ha altezza nera almeno bh(x) − 1.

Sia h il numero di archi del cammino più lungo dalla radice a NIL, equivalente al numero di nodi interni su quel cammino. Non essendoci rossi consecutivi, almeno metà dei nodi dopo la radice sono neri: bh(radice) ≥ h/2. Quindi n ≥ 2^h/2 − 1 e:

h \leq 2 \log_{2} (n + 1)

Il limite usa una disuguaglianza: bh(radice) non è sempre uguale a h/2. Il contatore del laboratorio include anche la radice nel conteggio dei neri: per un albero non vuoto e valido mostra bh(radice) + 1.

Operazione	Tempo peggiore	Nota
Ricerca	Θ(log n)	Segue un solo cammino.
Inserimento	Θ(log n)	Ricerca + fix-up; al massimo 2 rotazioni.
Eliminazione	Θ(log n)	Ricerca + fix-up; al massimo 3 rotazioni.
Spazio per nodo	Θ(1)	Colore e puntatori.

Eliminazione: prima il BST, poi il deficit di nero

Separiamo z, il nodo di cui vogliamo eliminare la chiave, da y, il nodo che scolleghiamo fisicamente. La distinzione è essenziale quando z ha due figli.

Zero o un figlio non NIL: y = z. Collega al padre l’unico figlio, oppure NIL se z è una foglia interna senza figli reali.
Due figli non NIL: scegli y = minimo(z.right), il successore. y non ha figlio sinistro, quindi si stacca con il caso precedente. In questa versione copiamo chiave e dati di y in z, conservando il colore di z.
Chiama x il figlio che prende il posto di y, anche se è NIL. Salva il colore originario di y: è questo, non necessariamente il colore di z, a decidere se serve il fix-up.

Esempio: radice 20B con figli 10R e 30R. Eliminare la chiave 20 significa copiare 30 nella radice e staccare il nodo rosso 30: non manca alcun nero, anche se la chiave richiesta era in un nodo nero.

Questa è la variante che copia i dati: se altri oggetti conservano riferimenti all’identità dei nodi, si può usare una variante a trapianti che sposta fisicamente il successore. Le regole sui colori e i casi di fix-up restano gli stessi.

Quando compare il “doppio nero”?

y era rosso: nessun cammino perde un nodo nero; non serve riparazione.
y era nero e x è rosso: colora x di nero e hai finito. In un RB valido, un nodo con un solo figlio reale è nero e quel figlio è rosso.
y era nero e x è nero o NIL: ai cammini che passano per x manca un nero. Attribuiamo a x un nero extra, detto “doppio nero”, e lo risolviamo con il ciclo di fix-up.

Il doppio nero è un artificio contabile, non un terzo colore memorizzato. Se x è la radice, il nero extra si può scartare: tutti i cammini hanno perso lo stesso contributo. Se x è rosso, il nero extra viene assorbito colorandolo nero.

Pseudocodice: scollegamento del nodo

RB-DELETE(T, z)
    if z.left = NIL or z.right = NIL
        y ← z
    else
        y ← TREE-MINIMUM(z.right)

    removedColor ← y.color
    if y.left ≠ NIL
        x ← y.left
    else
        x ← y.right

    x.p ← y.p                   // also when x = NIL
    if y.p = NIL
        T.root ← x
    else if y = y.p.left
        y.p.left ← x
    else
        y.p.right ← x

    if y ≠ z
        z.key ← y.key
        z.data ← y.data         // keep z.color unchanged
    if removedColor = BLACK
        RB-DELETE-FIXUP(T, x)
    return y                    // detached node

La procedura riceve un nodo z esistente; se si parte da una chiave, prima si esegue la ricerca. La sentinella condivisa ha left e right uguali a sé stessa. Durante la cancellazione impostiamo temporaneamente NIL.p al padre del posto lasciato vuoto: il fix-up deve poterlo leggere. Un’implementazione con null deve invece passare il padre separatamente.

I quattro casi del fix-up

Supponiamo x figlio sinistro. Indichiamo con p il padre e con w = p.right il fratello. Il nipote vicino è w.left, quello lontano è w.right. Negli appunti corrispondono rispettivamente ad A (x), B (p), D (w), C (vicino), E (lontano). I figli NIL sono neri.

          p
         / \
   x (+B)   w
           / \
        near far

Caso 1 · Fratello rosso

Condizione: w è rosso; allora p e i figli di w sono neri. Colora w di nero e p di rosso, ruota a sinistra su p, poi ricalcola w ← x.p.right.

Effetto: x mantiene il nero extra e lo stesso padre, ma il suo nuovo fratello è nero. Il caso 1 prepara uno dei casi 2, 3 o 4; non è terminale e non implica necessariamente il caso 3.

Caso 2 · Fratello nero, entrambi i nipoti neri

Operazione: colora w di rosso e assegna x ← p. Togliendo un nero al lato del fratello, i due lati tornano allo stesso livello; il deficit passa al padre.

Esito: se il nuovo x è rosso, l’uscita dal ciclo lo colora nero e termina. Se è nero e non è la radice, il ciclo continua più in alto. Questo è l’unico caso che può ripetersi O(log n) volte; non richiede rotazioni.

Caso 3 · Nipote vicino rosso, lontano nero

Condizione: w è nero, w.left rosso e w.right nero. Colora w.left di nero e w di rosso; ruota a destra su w e ricalcola il fratello di x.

Effetto: il nuovo fratello è nero e il nuovo nipote lontano è rosso. x conserva il deficit, ma la configurazione è pronta per il caso 4, da eseguire immediatamente.

Caso 4 · Nipote lontano rosso: risolvi e termina

Condizione: w è nero e w.right rosso; il vicino può avere qualunque colore. Assegna w.color ← p.color, p.color ← BLACK e w.right.color ← BLACK. Ruota a sinistra su p e termina ponendo x ← T.root.

Perché funziona: il lato di x guadagna il contributo nero che mancava; il lato opposto viene compensato dalla ricolorazione del nipote lontano. La nuova radice locale conserva il vecchio colore di p, quindi la riparazione non altera il conteggio nero visto dagli antenati.

Se x è figlio destro: scambia sinistra e destra in tutti i passaggi. Il fratello è p.left, il nipote vicino è w.right e quello lontano w.left; le rotazioni sinistre diventano destre e viceversa. Complessivamente: al massimo tre rotazioni (casi 1, 3 e 4), oltre alle eventuali risalite del caso 2.

Esempio svolto: eliminare 10, casi 3 → 4

       20B             20B             20B              30B
      /   \           /   \           /   \            /   \
    10B   40B   →  NIL+B  40B   →  NIL+B  30B   →    20B   40B
          /               /                 \
        30R             30R                 40R
      DELETE 10               CASE 3              CASE 4

Dopo aver staccato 10B, x è il NIL sinistro di 20: w = 40B, vicino = 30R, lontano = NIL. Il caso 3 ruota su 40 e rende 30 il nuovo fratello; il caso 4 ruota su 20 e ottiene radice 30B con figli 20B e 40B. Tutti i cammini hanno di nuovo lo stesso numero di neri.

Pseudocodice completo del fix-up, inclusi i casi speculari

RB-DELETE-FIXUP(T, x)
    while x ≠ T.root and x.color = BLACK
        if x = x.p.left
            w ← x.p.right
            if w.color = RED                 // case 1
                w.color ← BLACK
                x.p.color ← RED
                LEFT-ROTATE(T, x.p)
                w ← x.p.right

            if w.left.color = BLACK and w.right.color = BLACK
                w.color ← RED                // case 2
                x ← x.p
            else
                if w.right.color = BLACK     // case 3
                    w.left.color ← BLACK
                    w.color ← RED
                    RIGHT-ROTATE(T, w)
                    w ← x.p.right
                w.color ← x.p.color          // case 4
                x.p.color ← BLACK
                w.right.color ← BLACK
                LEFT-ROTATE(T, x.p)
                x ← T.root
        else
            w ← x.p.left
            if w.color = RED                 // mirror 1
                w.color ← BLACK
                x.p.color ← RED
                RIGHT-ROTATE(T, x.p)
                w ← x.p.left

            if w.right.color = BLACK and w.left.color = BLACK
                w.color ← RED                // mirror 2
                x ← x.p
            else
                if w.left.color = BLACK      // mirror 3
                    w.right.color ← BLACK
                    w.color ← RED
                    LEFT-ROTATE(T, w)
                    w ← x.p.left
                w.color ← x.p.color          // mirror 4
                x.p.color ← BLACK
                w.left.color ← BLACK
                RIGHT-ROTATE(T, x.p)
                x ← T.root
    x.color ← BLACK

Dopo ogni rotazione dei casi 1 e 3 si ricalcola w. I controlli successivi non sono tutti collegati da “else if”: più casi possono essere eseguiti nella stessa iterazione. In uno stato valido con deficit, il fratello w non è NIL; possono invece esserlo i suoi figli.

Il laboratorio sopra visualizza l’inserimento; gli schemi e lo pseudocodice di questa sezione descrivono la cancellazione.

Creare un RB albero da un array non ordinato

Parti dall’albero vuoto e inserisci le chiavi nell’ordine dell’array, eseguendo il fix-up dopo ogni inserimento. Non serve ordinare prima l’array. L’albero resta rosso-nero dopo ogni prefisso della sequenza, quindi l’inserimento successivo beneficia già dell’altezza logaritmica.

RB-BUILD(A)
    T ← EMPTY-RB-TREE()          // root = NIL, NIL.color = BLACK
    for key in A
        RB-INSERT(T, key)       // includes fix-up after each insertion
    return T

L’array vuoto produce radice NIL. Per i duplicati adottiamo la semantica di insieme: una chiave già presente non crea un altro nodo. Per rappresentare un multinsieme si può aggiungere un contatore di occorrenze al nodo.

Esempio: A = [41, 38, 31, 12, 19, 8]

Un inserimento alla volta, con fix-up completo
Chiave	Posizione iniziale	Riparazione	Risultato locale
41	Radice	Radice a nero	41B
38	Sinistra di 41B	Padre nero: nessun caso	38 resta rosso
31	Sinistra di 38R	Caso 3; rotazione destra su 41	Radice 38B, figli 31R e 41R
12	Sinistra di 31R	Caso 1: zio 41R; poi radice nera	31B, 41B, 12R
19	Destra di 12R	Caso 2 su 12, poi caso 3 su 31	19B con figli 12R e 31R
8	Sinistra di 12R	Caso 1: zio 31R; 19 risale sotto 38B	19R, 12B, 31B, 8R

Controllo: l’in-order è [8, 12, 19, 31, 38, 41]; nessun rosso ha un figlio rosso. Ogni cammino dalla radice a NIL contiene tre nodi neri contando radice e NIL, quindi bh(radice) = 2 con la convenzione che esclude la radice. Cambiando ordine di inserimento si può ottenere una forma diversa, comunque valida.

Costo e limite inferiore

Per n chiavi distinte, l’inserimento numero i costa O(log(i + 1)). Sommando si ottiene O(n log n) tempo e Θ(n) spazio per l’albero. Il limite superiore è ottimo nel caso peggiore per chiavi arbitrarie nel modello a confronti.

\sum_{i = 1}^{n} O (\log (i + 1)) = O (n \log n)

Dimostrazione del limite inferiore: se costruissimo un BST contenente n chiavi arbitrarie distinte in o(n log n), una visita in-order in Θ(n) restituirebbe quelle chiavi ordinate. Avremmo un ordinamento per confronti più veloce del limite Ω(n log n), una contraddizione. Dunque la costruzione ha costo Θ(n log n) nel caso peggiore.

Perché dividere l’array e fare Union non dà tempo lineare?

Dividere l’array per posizione non separa i valori: una metà può contenere [9, 1] e l’altra [4, 7]. Non si possono collegare i due alberi come se tutte le chiavi del primo fossero minori di quelle del secondo. Questa precondizione è richiesta dalle semplici operazioni di join.

Una possibile unione generale estrae le due sequenze in-order, le fonde e ricostruisce un RB valido, con un costo lineare nel numero totale di chiavi. Nello schema divide et impera questo produce T(n) = 2T(n/2) + Θ(n) = Θ(n log n), perché si paga Θ(n) a ogni livello. I casi base devono comprendere sia l’intervallo vuoto sia quello con un solo elemento; senza il secondo, una chiamata sulla stessa metà non termina.

Se l’array è già ordinato: esistono costruzioni dirette in Θ(n) con scelta dei mediani e colorazione coerente dei livelli. Colorare tutto di nero funziona solo se tutti i cammini verso NIL hanno la stessa lunghezza; un BST bilanciato generico non basta. Partendo da dati non ordinati, un ordinamento per confronti continua a costare Θ(n log n) nel caso peggiore.

Esercizi con soluzione

1. Inserisci [10, 30, 20] in un albero vuoto. Quali casi compaiono?

10 diventa radice nera, 30 suo figlio destro rosso. Inserendo 20 compare un triangolo destra–sinistra con zio NIL nero: caso 2 speculare, rotazione destra su 30; poi caso 3 speculare, ricolorazione e rotazione sinistra su 10. Risultato: radice 20B, figli 10R e 30R.

2. Da una radice 20B con figli 10B e 30B, elimina 10.

x è il NIL sinistro; w = 30B ha due figli NIL neri. Caso 2: 30 diventa rosso e x sale a 20. x è la radice, quindi si scarta il nero extra. Risultato: 20B con figlio destro 30R.

3. Da 20B con figlio sinistro 10R, elimina 20. Serve una rotazione?

No. y = 20B, x = 10R. Il figlio prende il posto della radice e viene colorato nero; il ciclo del fix-up non viene eseguito.

4. Perché costruire un RB albero da n chiavi distinte non ordinate in O(n) violerebbe il limite dell’ordinamento per confronti?

Costruzione O(n) + visita in-order Θ(n) darebbero un ordinamento O(n). Nel modello a confronti il costo peggiore è invece almeno Ω(n log n). Il ragionamento richiede chiavi arbitrarie; algoritmi per interi con ipotesi aggiuntive sul dominio possono usare operazioni diverse dai confronti.

Errori comuni

Trattare i puntatori NIL come assenti nell’analisi: sono foglie nere e partecipano alla black-height.
Pensare che rosso-nero significhi perfettamente bilanciato: la garanzia è h ≤ 2 log₂(n+1), non livelli completi.
Dimenticare i casi speculari quando padre è figlio destro del nonno.
Ruotare senza aggiornare radice e genitori, o ricolorare prima di aver identificato correttamente zio e nonno.
Contare tutti i nodi invece dei soli neri quando si verifica la black-height.

Percorso basato sui temi di Algoritmi, lezioni 16–18 (pp. 53–67): proprietà, rotazioni, inserimento, eliminazione e costruzione. Per approfondire: Dartmouth · Red-black trees; Princeton · Sorting and searching.