Albero 2-3

Da Wikipedia, l'enciclopedia libera.

Un albero 2-3 è un tipo di struttura dati ad albero che gode delle seguenti proprietà:

  • ogni nodo può avere 2 o 3 figli
  • tutte le foglie sono alla stessa profondità
  • gli elementi sono contenuti nelle foglie
  • le chiavi sono crescenti nelle foglie da sinistra a destra

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

2^h \le f \le 3^h

Le operazioni di ricerca, inserzione e cancellazione hanno costo, nel caso peggiore, O(log n).

Bibliografia[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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