Algoritmi/Le tabelle di simboli

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.