Timeline
Chat
Prospettiva

Albero 2-3

Da Wikipedia, l'enciclopedia libera

Albero 2-3
Remove ads

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.

Thumb
Albero 2-3
Remove ads

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

Remove ads

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

  • (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.
Remove ads

Voci correlate

Altri progetti

Collegamenti esterni

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica
Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads