Un RB-Albero (o anche red-black tree, in italiano albero rosso-nero) è un tipo di albero binario di ricerca bilanciato, una struttura dati usata in Informatica, tipicamente utilizzata per implementare insiemi o array associativi. La struttura originale è stata inventata nel 1972 da Rudolf Bayer che la chiamò "B-alberi binari simmetrici", ma ha acquisito il nome attuale a partire da un articolo del 1978 di Leo J. Guibas e Robert Sedgewick. È complessa, ma ha un eccellente tempo di esecuzione nel caso peggiore ed è molto efficiente: effettua ricerche, inserimenti e cancellazioni in un tempo di , dove è il numero di elementi nell'albero.

Concetti di base e terminologia Un albero rosso-nero è un tipo speciale di albero binario, che è una struttura utilizzata in informatica per organizzare dati comparabili, ad esempio numeri. Ciascuna unità di dati è conservata in un nodo. Uno dei nodi funge sempre da punto di partenza, e non è figlio di nessun nodo; viene di solito chiamato nodo root o semplicemente root. Questo nodo ha al massimo due figli, ovvero altri nodi ai quali è connesso. Ciascuno di questi figli ha a sua volta al massimo due figli, e così via. Il nodo root inoltre ha un path (percorso) che lo collega a qualsiasi altro nodo nell'albero.

Se un nodo non ha figli, viene chiamato nodo foglia, poiché, intuitivamente, fa parte della "periferia" dell'albero. Un sottoalbero è una porzione dell'albero che si estende a partire da un dato nodo. Negli alberi rosso-neri, si assume che le foglie abbiano valore null, ovvero esse non contengono dati.

Poiché gli alberi rosso-neri sono anche alberi binari di ricerca, essi soddisfano il vincolo per cui ogni nodo contiene un valore minore o uguale a quello di tutti i nodi del suo sottoalbero destro, e maggiore o uguale a quello di tutti i nodi del suo sottoalbero sinistro. Ciò rende veloce la ricerca di un dato valore nell'albero, e consente un ordinamento efficiente degli elementi.

Utilizzi e vantaggi Gli alberi rosso-neri, assieme agli alberi AVL, offrono le migliori performance nel caso peggiore dei tempi di ricerca, inserimento e cancellazione. Ciò li rende non soltanto importanti nelle applicazioni sistema real-time, ma fondamentali "mattoni" di altre strutture dati che forniscono garanzie nel caso peggiore; ad esempio, molte strutture dati usate nella geometria computazionale sono basate su alberi rosso-neri.

Gli alberi rosso-neri sono inoltre importanti nella programmazione funzionale, in cui sono una delle strutture dati persistenti più comuni, utilizzati per costruire array associativi e set in grado di mantenere stati precedenti alla modifica. La versione persistente degli alberi rosso-neri richiede uno spazio di O(log n) per ciascun inserimento o cancellazione, in aggiunta al tempo.

Gli alberi rosso-neri sono un'isometria degli alberi 2-3-4. In altre parole, per ciascun albero 2-3-4, esiste almeno un albero rosso-nero con gli elementi nello stesso ordine. Le operazioni di inserimento e cancellazione sugli alberi 2-3-4 sono equivalenti a quelle di ricolorazione e rotazione negli alberi rosso-neri. Gli alberi 2-3-4, dunque, sono uno strumento importante per comprendere la logica esistente dietro gli alberi rosso-neri, ed è questo il motivo per cui molti testi sugli algoritmi introducono gli alberi 2-3-4 subito prima di quelli rosso-neri, benché quelli 2-3-4 non vengano quasi mai utilizzati nella pratica.

Proprietà

Un albero rosso-nero è un albero binario di ricerca in cui ciascun nodo ha un attributo colore, il cui valore può essere rosso oppure nero. In aggiunta ai requisiti ordinari per un albero binario di ricerca, un albero rosso-nero soddisfa le seguenti proprietà:

Ogni nodo ha colore rosso o nero. Il nodo root inizialmente è nero. Ogni foglia è nera e contiene elemento null; Entrambi i figli di ciascun nodo rosso sono neri; Ogni cammino da un nodo a una foglia nel suo sottoalbero contiene lo stesso numero di nodi neri.

Questi vincoli rafforzano una proprietà critica degli alberi rosso-neri: che il cammino più lungo dal nodo root a una foglia è al massimo lungo il doppio del cammino più breve. Ne risulta dunque un albero fortemente bilanciato. Poiché le operazioni di ricerca di un valore, inserimento e cancellazione richiedono un tempo di esecuzione nel caso peggiore proporzionale all'altezza dell'albero, questo limite superiore teorico sull'altezza rende gli alberi rosso-neri molto efficienti nel caso peggiore, al contrario di quanto accade con gli ordinari alberi binari di ricerca.

Per vedere in che modo tali proprietà vengono garantite, è sufficiente notare che nessun cammino può avere due nodi rossi in fila, per la proprietà 4. Il cammino più breve possibile ha tutti nodi neri, e il più lungo alterna nodi rossi e nodi neri. Poiché tutti i cammini massimi hanno lo stesso numero di nodi neri, per la proprietà 5, ciò dimostra che nessun cammino è lungo più del doppio di qualsiasi altro cammino.

In molte strutture dati "alberi", è possibile che un nodo abbia un solo figlio, e che i nodi foglia contengano dati. È possibile presentare anche gli alberi rosso-neri secondo questo paradigma, ma ciò modificherebbe alcune delle proprietà e complicherebbe l'algoritmo. Per questa ragione, in questo articolo parliamo di "foglie nulle", che non contengono dati e servono semplicemente ad indicare dove finisce l'albero. Questi nodi vengono spesso omessi nella rappresentazione grafica, e l'albero rappresentato sembra contraddire i principi esposti, ma di fatto non è così. La conseguenza è che tutti i nodi interni (non foglia) hanno due figli, sebbene uno o entrambi questi figli possano essere una foglia nulla.

Alcune trattazioni illustrano gli alberi rosso-neri come alberi binari di ricerca i cui archi (invece dei nodi) sono colorati di rosso o di nero; ma ciò non fa alcuna differenza. Nella nostra terminologia, il colore di un nodo corrisponde al colore dell'arco che connette il nodo al padre, escluso il nodo root che è sempre nero (proprietà 2) in considerazione del fatto che l'arco corrispondente non esiste.

Operazioni Le operazioni di lettura su un albero rosso-nero non richiedono modifiche rispetto a quelle utilizzate per gli alberi binari di ricerca, poiché gli alberi rosso-neri sono una loro specializzazione. Al contrario, il risultato immediato di un inserimento o di una cancellazione può violare le proprietà dell'albero rosso-nero, e ristabilire tali proprietà richiede un piccolo numero (O(log n) o O(1) ammortizzato) di ricolorazioni (che sono molto veloci nella pratica) e non più di tre rotazioni dell'albero (due per l'inserimento). Nonostante l'inserimento e la cancellazione siano operazioni complicate, i loro tempi di esecuzione rimangono dell'ordine di O(log n).

Inserimento

Si comincia aggiungendo un nodo come se si trattasse di un albero binario di ricerca classico, e colorandolo di rosso. Il passo successivo dipende dal colore degli altri nodi attigui. Useremo il termine nodo zio per riferirci al fratello del nodo padre. Si noti che: la proprietà 3 (tutte le foglie, incluse quelle nulle, sono nere) persiste; la proprietà 4 (entrambi i figli di ogni nodo rosso sono neri) è minacciata soltanto dall'inserimento di un nodo rosso, dalla ricolorazione in rosso di un nodo nero, o da una rotazione; la proprietà 5 (tutti i cammini a partire da un dato nodo verso le sue foglie contengono lo stesso numero di nodi neri) è minacciata soltanto dall'inserimento di un nodo nero, dalla ricolorazione in nero di un nodo rosso, o da una rotazione.

Nota: utilizzeremo la seguente simbologia: N per il nodo inserito, P per il nodo padre di N, G per il nodo padre di P, e U per il "nodo zio" di N. Si noti che in qualche caso è possibile che ruoli e simboli dei nodi vengano scambiati; in ogni caso, ciascun simbolo continua a rappresentare lo stesso nodo che rappresentava all'inizio del caso. Ciascun caso viene dimostrato con del codice d'esempio in linguaggio C, i nodi "zio" e "nonno" si trovano tramite le seguenti funzioni: node grandparent(node n) { return n->parent->parent;

node uncle(node n) { if (n->parent == grandparent(n)->left) return grandparent(n)->right; else return grandparent(n)->left;

Caso 1 il nuovo nodo N è nella root dell'albero. In questo caso, viene colorato di nero per soddisfare la proprietà 2 (la root è nera). Poiché questo inserimento aggiunge un nodo nero a ciascun cammino, la proprietà 5 (tutti i cammini a partire da un dato nodo verso le sue foglie contengono lo stesso numero di nodi neri) non è violata. void insert_case1(node n) { if (n->parent == NULL) n->color = BLACK; else insert_case2(n);

Caso 2 il padre P del nuovo nodo è nero, quindi la proprietà 4 (entrambi i figli di ogni nodo rosso sono neri) non è invalidata. In questo caso, l'albero è ancora valido. La proprietà 5 (tutti i cammini a partire da un dato nodo verso le sue foglie contengono lo stesso numero di nodi neri) sembrerebbe minacciata, perché il nuovo nodo N ha due foglie nere, ma poiché N è rosso, i cammini attraverso ognuno dei suoi figli hanno lo stesso numero di nodi neri poiché sono cammini separati, per cui la proprietà rimane soddisfatta. void insert_case2(node n) { if (n->parent->color == BLACK) return; /* Tree is still valid */ else insert_case3(n);

Nota: nei casi che seguono si assume che N abbia un nodo "nonno" G, perché il padre P è rosso, e se fosse stato root sarebbe stato nero. Inoltre, N ha anche un nodo "zio" U, sebbene esso possa essere una foglia nei casi 4 e 5.

Caso 3 se sia il padre P sia lo zio U sono rossi, allora è possibile ricolorare entrambi di nero e ricolorare di rosso il nonno G per mantenere la proprietà 5 (tutti i cammini a partire da un dato nodo verso le sue foglie contengono lo stesso numero di nodi neri). Adesso il nuovo nodo N ha un padre nero. Poiché qualsiasi cammino attraverso il padre o lo zio deve passare attraverso il nonno, il numero di nodi neri su questi cammini non cambia. Però il nonno G ora potrebbe violare la proprietà 2 (il nodo root è nero) o la 4 (entrambi i figli di ogni nodo rosso sono neri) perché potrebbe avere un padre rosso. Per risolvere il problema, la procedura va ripetuta ricorsivamente su G a partire dal caso 1. Si noti che questa è l'unica chiamata ricorsiva, e che avviene prima di qualsivoglia rotazione, il che prova che si avrà un numero costante di rotazioni. void insert_case3(node n) { if (uncle(n) != NULL && uncle(n)->color == RED) { n->parent->color = BLACK; uncle(n)->color = BLACK; grandparent(n)->color = RED; insert_case1(grandparent(n));

else insert_case4(n);

Nota: nei casi seguenti, si assume che il nodo padre P è figlio sinistro del proprio padre. Se fosse figlio destro, left e right dovrebbero essere invertiti nei casi 4 e 5.

Caso 4 il padre P è rosso ma lo zio U è nero; il nuovo nodo N è il figlio destro di P, e P a sua volta è figlio sinistro di G. In questo caso, si effettua una rotazione a sinistra che scambia i ruoli del nuovo nodo N e del padre P; quindi ci si occupa dell'ex nodo padre P utilizzando il caso 5 (scambiando i nomi N e P). Ciò fa sì che alcuni cammini (quelli etichettati con "1" nel grafico) passino ora attraverso il nuovo nodo senza che prima ciò accadesse; ma entrambi questi nodi sono rossi, perciò la proprietà 5 (tutti i cammini a partire da un dato nodo verso le sue foglie contengono lo stesso numero di nodi neri) non è violata. La proprietà 4 (entrambi i figli di ogni nodo rosso sono neri) è ancora violata, ma si può risolvere continuando con il caso 5. void insert_case4(node n) { if (n == n->parent->right && n->parent == grandparent(n)->left) { rotate_left(n->parent); n = n->left; } else if (n == n->parent->left && n->parent == grandparent(n)->right) { rotate_right(n->parent); n = n->right;

insert_case5(n);