mastorna.it
EN

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. 1

    Ogni nodo è rosso oppure nero.

  2. 2

    La radice è nera.

  3. 3

    Ogni foglia NIL, cioè ogni puntatore vuoto, è nera.

  4. 4

    Un nodo rosso ha padre e figli neri: non esistono due rossi consecutivi.

  5. 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.

Casi guidati

Nodi
0
Altezza
0
Black-height
0
Rotazioni
0
Ricolorazioni
0
  1. BST-insert(z); z.color ← RED
  2. while color(parent(z)) = RED
  3. if color(uncle(z)) = RED: recolor and move z up
  4. else if z is an inner child: rotate parent(z)
  5. recolor parent and grandparent
  6. rotate grandparent(z)
  7. root.color ← BLACK
nodo rosso nodo nero nodo corrente z modificato nel passo

Inserire come in un BST, poi riparare

  1. Trova una foglia NIL con la normale ricerca BST e collega il nuovo nodo.
  2. Coloralo rosso: così la black-height di tutti i cammini resta invariata.
  3. Se il padre è nero, gli invarianti sono già soddisfatti.
  4. Se il padre è rosso, esamina zio e forma geometrica; applica il fix-up.
  5. 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 soltanto la regola rosso–rosso, che si ripara localmente.

I casi fondamentali del fix-up

Caso 1

Zio rosso: ricolora

Padre e zio diventano neri, il nonno diventa rosso e z risale al nonno. La violazione può propagarsi verso la radice.

Caso 2

Triangolo: raddrizza

z è figlio interno. Una rotazione sul padre trasforma il triangolo in una linea, riconducendo al caso successivo.

Caso 3

Linea: ricolora e ruota

Il padre diventa nero, il nonno rosso e una rotazione sul nonno elimina la coppia rosso–rosso.

I casi destra–sinistra sono immagini speculari dei casi sinistra–destra. Il simulatore descrive esplicitamente la direzione scelta.

Perché l’altezza resta logaritmica

Contrai ogni nodo rosso nel suo padre nero. Per la regola rosso–rosso ogni nodo nero assorbe al massimo due figli rossi; per la black-height l’albero risultante ha tutti i cammini della stessa lunghezza. Ne segue:

h ≤ 2 log₂(n + 1)

OperazioneTempo peggioreNota
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.

Perché l’eliminazione è più delicata

Eliminare un nodo rosso non cambia la black-height. Eliminare un nodo nero, invece, sottrae un nero ai cammini che lo attraversavano: l’algoritmo rappresenta temporaneamente il deficit come “doppio nero” e lo risolve esaminando fratello e nipoti. I casi sono più numerosi, ma usano gli stessi strumenti: ricolorazioni e rotazioni.

Il laboratorio si concentra sull’inserimento, perché rende leggibili tutti i principi essenziali senza comprimere in una sola vista i numerosi casi simmetrici dell’eliminazione.

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.