Un albero 2-3 è un tipo di struttura dati ad albero di ricerca bilanciato che mantiene i dati ordinati e garantisce prestazioni logaritmiche per le operazioni fondamentali. Deve il suo nome al fatto che ogni nodo interno può avere esattamente 2 o 3 figli.

Definizione

Un albero 2-3 è un albero tale che: ogni nodo interno ha almeno 2, al più 3 figli; tutti i cammini radice-foglia hanno la medesima lunghezza, in altre parole le foglie si trovano tutte alla stessa altezza.

Struttura dei nodi Per un 2-3 albero valgono le seguenti proprietà:

Le chiavi sono memorizzate nelle foglie, in ordine crescente, da sinistra a destra. Ogni nodo interno v contiene due informazioni: la massima chiave nel sottoalbero del primo figlio di v; se v ha 3 figli contiene anche la massima chiave nel sottoalbero del secondo figlio di v.

Proprietà matematiche

Se indica il numero di foglie, l'altezza dell'albero ed il numero di nodi, valgono le seguenti disuguaglianze:

Numero di foglie

Se indica il numero di foglie ed l'altezza dell'albero, vale la seguente disuguaglianza:

Numero totale di nodi Siano ed come sopra ed il numero di nodi dell'albero, vale la seguente disuguaglianza:

Dimostrazione

Le due proprietà possono essere dimostrate per induzione sull'altezza dell'albero.

Caso base (): per si ha e in effetti l'albero ha solo una foglia, cioè la radice. Allo stesso modo verifichiamo che , infatti si ha un solo nodo.

Passo induttivo: Supponiamo che le due disuguaglianze valgano per un albero 2-3 di altezza . Consideriamo un albero 2-3 con altezza e di altezza , ottenuto a partire da eliminandone l'ultimo livello. Siano il numero di nodi e il numero di foglie dell'albero . Per ipotesi induttiva si ha:

e

Poiché ogni foglia di ha almeno 2 o al più 3 figli in si avrà:

Per il numero totale di nodi, osserviamo che . Utilizzando le disuguaglianze ottenute:

Limite inferiore per n:

Limite superiore per n:

Quindi si ottiene , che è esattamente ciò che volevamo dimostrare per l'altezza .

Altezza dell'albero

Usando la limitazione sul numero totale di nodi si ha , quindi l'altezza di un albero 2-3 è .

Relazioni con altre strutture dati

Gli alberi 2-3 sono strettamente correlati ai B-alberi (di cui sono un caso speciale con ordine minimo 2) e agli alberi rosso-nero (con cui esiste una corrispondenza biunivoca). Condividono con gli alberi AVL la proprietà di essere alberi di ricerca bilanciati, ma utilizzano strategie di bilanciamento diverse.

Applicazioni

Gli alberi 2-3 trovano applicazione nei sistemi di gestione database per l'indicizzazione efficiente, negli algoritmi di ordinamento come base per algoritmi esterni, e come modello teorico per lo studio del bilanciamento degli alberi.

Varianti

Tra le principali varianti si annoverano gli alberi 2-3-4 (che permettono nodi con 4 figli), i B+ alberi (generalizzazione utilizzata nei database) e gli alberi (a,b) (generalizzazione parametrica).

Bibliografia

(EN)

(IT)

(EN)

Voci correlate Albero (informatica) Albero di ricerca binario B-albero Albero rosso-nero Albero AVL Struttura dati

Altri progetti

Collegamenti esterni

Visualizzazione interattiva degli alberi 2-3 (in inglese) Tutorial sugli alberi 2-3 (in inglese)

2-3 Categoria:Strutture dati Categoria:Algoritmi di ricerca