Albero 2-3

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

• Robert Sedgewick, Balanced Trees in Algorithms (in inglese), Addison Wesley, giugno 1983. ISBN 978-0201066722

Collegamenti esterni

• (EN) 2-3 Trees as Search Trees

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