FANDOM


Nota disambigua
Il titolo di questa voce non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 8. Le tabelle di simboli.
Blue Glass Arrow RTL  7. Gli heapCrystal Clear app kfm home  Algoritmi e programmazioneBlue Glass Arrow  9. Alberi binari di ricerca (BST)
Gli appunti che seguono sono contenuti nella sottopagina /sub (modifica · cronologia · aggiorna)

2 tabella di simboli (o dizionario) = struttura dati formata da record, ovvero struct con dati aggregati di cui uno è la chiave.

4 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 ricercaModifica

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

Strutture lineariModifica

  • 5 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:
    • 7 vantaggio: ogni dato in un suo sottoinsieme K ha un indice → l'accesso è diretto (ricerca indicizzata per chiave);
    • 9 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 alberoModifica

  • 6 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.

OperazioniModifica

  • 3 data una chiave → inserimento di un nuovo elemento
  • data una chiave → ricerca di un elemento[1]
  • 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 peggioreModifica

11-12 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.

13 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 medioModifica

15 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.

NoteModifica

  1. 15 Si distinguono le ricerche con successo (hit) e quelle con insuccesso (miss).
Blue Glass Arrow RTL  7. Gli heapCrystal Clear app kfm home  Algoritmi e programmazioneBlue Glass Arrow  9. Alberi binari di ricerca (BST)

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Inoltre su FANDOM

Wiki casuale