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

Albero 2-3

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

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

Le operazioni di ricerca, inserzione e cancellazione hanno costo, nel caso peggiore, ${\displaystyle O(logn)}$.

Bibliografia

• (EN) Robert Sedgewick, Balanced Trees, in Algorithms, Addison Wesley, giugno 1983, ISBN 978-0-201-06672-2.

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

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