Wikibooks

Algoritmi/Le tabelle di simboli: differenze tra le versioni

Naviga nella cronologia in modo interattivo
Contenuto cancellato Contenuto aggiunto
VisualeWikitesto
 
 
Riga 8:
 
===Strutture lineari===
* <span style="fonttext-decoration: underline">array:</span> ordinati o non ordinati;
* <span style="fonttext-decoration: underline">liste:</span> ordinate o non ordinate;
* <span style="fonttext-decoration: underline">tabelle ad accesso diretto:</span> 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 [[Wikipedia:it:Cardinalità|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===
* <span style="fonttext-decoration: underline">alberi binari di ricerca (BST):</span> efficienti;
* <span style="fonttext-decoration: underline">alberi bilanciati:</span> (es. RB-tree) garantiscono che le operazioni siano sempre di complessità logaritmica e non degenerino in lineari.
 
==Operazioni==
* data una chiave → <span style="fonttext-decoration: underline">inserimento</span> di un nuovo elemento
* data una chiave → <span style="fonttext-decoration: underline">ricerca</span> di un elemento<ref>Si distinguono le ricerche con successo ('''hit''') e quelle con insuccesso ('''miss''').</ref>
* data una chiave → <span style="fonttext-decoration: underline">cancellazione</span> di elemento specificato
* dato un numero k → <span style="fonttext-decoration: underline">selezione</span> del ''k''-esimo elemento più piccolo
* <span style="fonttext-decoration: underline">ordinamento</span> della tabella di simboli in base alla chiave
* <span style="fonttext-decoration: underline">unione</span> 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:
* <span style="fonttext-decoration: underline">non ordinati:</span> l'inserimento ha un costo unitario (per es. inserimento sempre in testa);
* <span style="fonttext-decoration: underline">ordinati:</span> 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.
Estratto da "https://it.wikibooks.org/wiki/Algoritmi/Le_tabelle_di_simboli"