Embedded Files
Gli archivi con un'organizzazione ad indice consentono ricerche molto veloci sul campo chiave, essendo quest'ultimo indicizzato.
E' interessante osservare che l'ordinamento alfabetico, così come siamo abituati ad usarlo per ricercare parole nel vocabolario, è molto efficace ma esistono tecniche molto più sofisticate utilizzate nei sistemi informatici.
Tra queste è di particolare interesse la tecnica basata sugli alberi binari.
Ricordiamo che una struttura ad albero si ottiene collegando i nodi tramite i rami, come mostrato in figura.
Non è ammesso realizzare dei cicli, né lasciare nodi disconnessi.
Una struttura con un solo nodo e senza rami è ancora un albero.
Nella seguente figura in blu è rappresentata la radice (o nodo radice) dell'albero e in rosso le foglie (o nodi foglia).
Un nodo può avere uno o più figli (o nodi figlio). Nell'esempio precedente la radice ha tre figli.
Le foglie, ovviamente, non hanno figli.
Di seguito sono mostrati in rosso gli antenati del nodo in blu.
Un albero binario è un particolare albero, caratterizzato dal fatto che ogni nodo ha al massimo due figli, identificati come figlio sinistro e figlio destro.
Nella precedente immagine in rosso è rappresentato un nodo con due figli (sinistro e destro) mentre in blu è rappresentato un nodo con il solo figlio destro.
In un albero binario di ricerca i nodi contengono le chiavi e l'organizzazione è tale per cui, comunque scegliamo un nodo x, il sottoalbero sinistro del nodo x contiene chiavi con valore inferiore a x mentre il sottoalbero destro contiene chiavi con valori maggiore di x.
L'albero sopra rappresentato è un albero di ricerca, infatti risponde alla definizione precedentemente data. Analizziamo, ad esempio, il nodo radice che ha il valore 6.
Nel sottoalbero sinistro tutti i nodi hanno un valore più piccolo di 6.
Nel sottoalbero destro tutti i nodi hanno un valore più grande di 6.
Questa caratteristica vale per tutti i nodi dell'albero.
Ad esempio, il nodo con valore 8 ha solo il sottoalbero destro e in esso tutti i nodi contengono un valore più grande di 8.
In un albero per ricercare un valore si parte sempre dalla radice e si procede spostandosi nel sottoalbero sinistro o destro a seconda che il valore ricercato sia più piccolo o più grande. La ricerca ha termine quando si trova il valore desiderato o non è più possibile continuare la ricerca.
Il seguente esempio mostra come procedere per ricercare il valore 3 nell'albero precedente.
Si parte dalla radice che ha valore 6.
Poiché il valore ricercato è minore di 6, il valore del nodo corrente, ci si sposta nel sottoalbero sinistro.
Poiché 3 è maggiore di 2, il valore del nodo corrente, ci si sposta nel sottoalbero destro.
Poiché 3 è minore di 4, il valore del nodo corrente, ci si sposta nel sottoalbero sinistro.
Poiché il nodo corrente ha il valore ricercato, la ricerca ha termine con successo.
Il seguente esempio mostra come procedere per ricercare il valore 5, che in realtà non è presente nell'albero.
Si parte dalla radice che ha valore 6.
Poiché il valore ricercato è minore di 6, il valore del nodo corrente, ci si sposta nel sottoalbero sinistro.
Poiché 5 è maggiore di 2, il valore del nodo corrente, ci si sposta nel sottoalbero destro.
Poiché 5 è maggiore di 4, il valore del nodo corrente, dovremmo spostarci nel sottoalbero destro. Poiché il nodo corrente non ha un figlio destro, la ricerca termina con insuccesso (cioè il valore ricercato non esiste).
L'inserimento di un nodo con un nuovo valore (cioè un valore non presente nell'albero), può sempre essere fatto aggiungendo una foglia ad un nodo già esistente.
Il seguente esempio mostra come inserire un nodo con il valore 13 nell'albero già utilizzato per le ricerche precedenti.
Si procede come se si ricercasse il valore 13 e quindi si visitano in successione i nodi 6, 8, 12, 15.
Arrivati alla foglia la ricerca ha termine ed è a questo punto che si inserisce il nuovo nodo: nel nostro esempio, poiché il nodo da inserire è più piccolo del nodo corrente che vale 15, si aggiunge il figlio sinistro.
Da evidenziare che la ricerca si velocizza se l'albero binario è bilanciato in altezza.
In modo informale si può dire che un albero bilanciato in altezza è tale se non ci sono percorsi "sensibilmente" più lunghi di altri.
Esistono tecniche per inserire un nodo mantenendo un albero bilanciato.
La seguente immagine mostra un albero di ricerca bilanciato in altezza.
Sito: 7ecnologie
Sezione: 11. Base di dati
Capitolo: 02. Gli archivi
Paragrafo: 02. Tecniche di indicizzazione
Indice dei capitoli: 00. Risorse - 01. Sistema informativo, informazione e dato - 02. Gli archivi - 03. Il progetto informatico - 04. La progettazione concettuale - 05. La progettazione logica - 06. La progettazione fisica - 07. Tutorial - 98. Esercizi
Indice dei paragrafi: 01. Organizzazione degli archivi - 02. Tecniche di indicizzazione
Page updated
Google Sites
Report abuse