- Una struttura dati per ricerche molto veloci è un albero multichiave
- Quest'albero è costituito da una serie di record che contengono ciascuno n chiavi
ed n + 1 puntatori a record dello stesso tipo.
- Ogni chiave avrà un puntatore a sinistra ed un puntatore a destra
- Tutti i record che si raggiungono con il puntatore a sinistra hanno solo chiavi con valori
inferiori alla nostra chiave
- Tutti i record che si raggiungono con il puntatore a destra hanno solo chiavi con valori
superiori alla nostra chiave
- Ovviamente, un puntatore compreso tra due chiavi punterà a records che avrenno esclusivamente
valori compresi tra quelli delle due chiavi tra cui si trova
- Si può vedere facilmente che con un simile albero si può trovare un qualunque valore
cercando in logn x records, dove n è il numero di chiavi nel record
ed x il numero totale di chiavi che è inferiore ai log2 x
dell'albero binario
|
