# Algoritmi/Le tabelle di simboli

Algoritmi
Copertina Tutti i moduli · Sviluppo
    CopertinaAlgoritmi/Copertina
* Gli algoritmiAlgoritmi/Gli algoritmi
* L'analisi di complessità degli algoritmiAlgoritmi/L'analisi di complessità degli algoritmi
* Gli algoritmi di ordinamentoAlgoritmi/Gli algoritmi di ordinamento
* Grafi e alberiAlgoritmi/Grafi e alberi
* La ricorsioneAlgoritmi/La ricorsione
* Il paradigma "divide et impera"Algoritmi/Il paradigma "divide et impera"
* Gli heapAlgoritmi/Gli heap
* Le tabelle di simboliAlgoritmi/Le tabelle di simboli
* Alberi binari di ricerca (BST)Algoritmi/Alberi binari di ricerca (BST)
* Tipologie di problemiAlgoritmi/Tipologie di problemi
* Le tabelle di hashAlgoritmi/Le tabelle di hash
* L'ADT grafo non orientatoAlgoritmi/L'ADT grafo non orientato
* Gli algoritmi di visita dei grafiAlgoritmi/Gli algoritmi di visita dei grafi
* Le applicazioni degli algoritmi di visita dei grafiAlgoritmi/Le applicazioni degli algoritmi di visita dei grafi
* Gli alberi ricoprenti minimiAlgoritmi/Gli alberi ricoprenti minimi
* I cammini minimiAlgoritmi/I cammini minimi
Modifica il sommario
tabella di simboli (o dizionario) = struttura dati formata da record, ovvero struct con dati aggregati di cui uno è la chiave.
Si può estrarre la chiave dal record e stabilire se una chiave è minore o uguale a un'altra determinando una relazione d'ordine.

## Algoritmi di ricerca

Gli algoritmi di ricerca, cioè le implementazioni delle tabelle di simboli, possono avere strutture lineari, ad albero o a tabella di hash.

### Strutture lineari

* array: ordinati o non ordinati;
* liste: ordinate o non ordinate;
* tabelle ad accesso diretto: l'insieme K contenente tutti i dati memorizzati è un sottoinsieme dell'insieme universo U:
** vantaggio: ogni dato in un suo sottoinsieme K ha un indice → l'accesso è diretto (ricerca indicizzata per chiave);
** svantaggio: il vettore dovrà avere un numero di celle pari alla cardinalità di U → rimangono delle celle vuote → spreco di memoria lineare nel numero di dati, soprattutto se la cardinalità di K è molto minore di quella di U.

### Strutture ad albero

* alberi binari di ricerca (BST): efficienti;
* alberi bilanciati: (es. RB-tree) garantiscono che le operazioni siano sempre di complessità logaritmica e non degenerino in lineari.

## Operazioni

* data una chiave → inserimento di un nuovo elemento
* data una chiave → ricerca di un elemento
* data una chiave → cancellazione di elemento specificato
* dato un numero k → selezione del k-esimo elemento più piccolo
* ordinamento della tabella di simboli in base alla chiave
* unione di due tabelle di simboli

### Complessità di caso peggiore

La complessità dell'inserimento di un nuovo elemento all'interno di una lista o di un array varia a seconda se gli elementi sono ordinati:
* non ordinati: l'inserimento ha un costo unitario (per es. inserimento sempre in testa);
* ordinati: l'inserimento ha un costo lineare, perché bisogna inserire il nuovo elemento mantenendo l'ordinamento:
** array: bisogna spostare tutti gli elementi di una cella per far spazio al nuovo elemento;
** liste: l'inserimento implica una ricerca per scansione.
La ricerca binaria si deve effettuare su un array ordinato → può essere inefficiente se l'array varia molto e bisogna ordinarlo spesso.

### Complessità di caso medio

Nel caso medio:
* le operazioni sulle strutture lineari sono quasi sempre lineari nel numero dei dati;
* le operazioni sulle strutture ad albero sono quasi sempre logaritmiche nel numero dei dati (nel caso peggiore sono lineari);
* le operazioni sulle tabelle di hash hanno costo unitario, ma senza spreco di memoria come nelle tabelle ad accesso diretto.

## Note

* ↑ Si distinguono le ricerche con successo (hit) e quelle con insuccesso (miss).