Albero 2-3

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.

Albero 2-3

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:
  1. la massima chiave nel sottoalbero del primo figlio di v;
  2. se v ha 3 figli contiene anche la massima chiave nel sottoalbero del secondo figlio di v.

Proprietà matematiche

Se ${\displaystyle f}$ indica il numero di foglie, ${\displaystyle h}$ l'altezza dell'albero ed ${\displaystyle n}$ il numero di nodi, valgono le seguenti disuguaglianze:

${\displaystyle 2^{h}\leq f\leq 3^{h}}$

${\displaystyle 2^{h+1}-1\leq n\leq {\frac {3^{h+1}-1}{2}}}$

Numero di foglie

Se ${\displaystyle f}$ indica il numero di foglie ed ${\displaystyle h}$ l'altezza dell'albero, vale la seguente disuguaglianza:

${\displaystyle 2^{h}\leq f\leq 3^{h}}$

Numero totale di nodi

Siano ${\displaystyle f}$ ed ${\displaystyle h}$ come sopra ed ${\displaystyle n}$ il numero di nodi dell'albero, vale la seguente disuguaglianza:

${\displaystyle 2^{h+1}-1\leq f\leq (3^{h+1}-1)/2}$

Dimostrazione

Le due proprietà possono essere dimostrate per induzione sull'altezza ${\displaystyle h}$ dell'albero.

Caso base (${\displaystyle h=0}$): per ${\displaystyle h=0}$ si ha ${\displaystyle 2^{0}=1\leq f\leq 3^{0}=1}$ e in effetti l'albero ha solo una foglia, cioè la radice. Allo stesso modo verifichiamo che ${\displaystyle 2^{1}-1=1\leq n\leq (3^{1}-1)/2=1}$, infatti si ha un solo nodo.

Passo induttivo: Supponiamo che le due disuguaglianze valgano per un albero 2-3 di altezza ${\displaystyle h}$. Consideriamo un albero 2-3 ${\displaystyle T}$ con altezza ${\displaystyle h+1}$ e ${\displaystyle T'}$ di altezza ${\displaystyle h}$, ottenuto a partire da ${\displaystyle T}$ eliminandone l'ultimo livello. Siano ${\displaystyle n'}$ il numero di nodi e ${\displaystyle f'}$ il numero di foglie dell'albero ${\displaystyle T'}$. Per ipotesi induttiva si ha:

${\displaystyle 2^{h+1}-1\leq n'\leq {\frac {3^{h+1}-1}{2}}}$ e ${\displaystyle 2^{h}\leq f'\leq 3^{h}}$

Poiché ogni foglia di ${\displaystyle T'}$ ha almeno 2 o al più 3 figli in ${\displaystyle T}$ si avrà:

${\displaystyle 2\cdot 2^{h}\leq f\leq 3\cdot 3^{h}\Longrightarrow 2^{h+1}\leq f\leq 3^{h+1}}$

Per il numero totale di nodi, osserviamo che ${\displaystyle n=n'+f}$. Utilizzando le disuguaglianze ottenute:

Limite inferiore per n: ${\displaystyle n=n'+f\geq (2^{h+1}-1)+2^{h+1}=2\cdot 2^{h+1}-1=2^{h+2}-1}$

Limite superiore per n: ${\displaystyle n=n'+f\leq {\frac {3^{h+1}-1}{2}}+3^{h+1}={\frac {3^{h+1}-1+2\cdot 3^{h+1}}{2}}={\frac {3\cdot 3^{h+1}-1}{2}}={\frac {3^{h+2}-1}{2}}}$

Quindi si ottiene ${\displaystyle 2^{h+2}-1\leq n\leq {\frac {3^{h+2}-1}{2}}}$, che è esattamente ciò che volevamo dimostrare per l'altezza ${\displaystyle h+1}$.

Altezza dell'albero

Usando la limitazione sul numero totale di nodi si ha ${\displaystyle \log _{3}f\leq h\leq \log _{2}f}$, quindi l'altezza di un albero 2-3 è ${\displaystyle \Theta (\log n)}$.

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) Robert Sedgewick, Balanced Trees, in Algorithms, Addison-Wesley, 1983, ISBN 978-0-201-06672-2.

• (IT) Camil Demetrescu, Irene Finocchi e Giuseppe Francesco Italiano, Algoritmi e strutture dati, 2ª ed., McGraw-Hill Education, 2008, ISBN 978-88-386-6468-7.

• (EN) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein, Introduction to Algorithms, 4ª ed., MIT Press, 2022, ISBN 978-0-262-04630-5.

Voci correlate

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

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sull'albero 2-3

Collegamenti esterni

• (EN) 2-3 Trees as Search Trees, su cs.engr.uky.edu. URL consultato il 29 agosto 2012 (archiviato dall'url originale il 19 dicembre 2012).
• Visualizzazione interattiva degli alberi 2-3 (in inglese)
• Tutorial sugli alberi 2-3 (in inglese)

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica