Please enable JavaScript.
Coggle requires JavaScript to display documents.
Grafi e alberi, Tabelle di hash e Indici - Coggle Diagram
Grafi e alberi, Tabelle di hash e Indici
Grafo
Un grafo è dato da: •
un insieme non vuoto di nodi
•
un insieme di coppie di nodi chiamate archi
Cammino, lunghezza, cicli
Un
cammino
tra due nodi x,y è una sequenza ordinata di archi (x,v1), (v1,v2),…, (vl-1,vl), (vl,y)
Lunghezza
del cammino (l ≥ 0) è il numero di archi che lo formano
Si dice che il
grafo è connesso
se, presi due nodi distinti qualsiasi x,y esiste un cammino tra essi
Un cammino chiuso (x = y) senza archi né nodi ripetuti viene detto
ciclo
Albero
Un albero è un grafo
connesso senza cicli
Definizione ricorsiva di un albero(su slide)
Il
grado
di un nodo u è il numero di archi uscenti del tipo (u,v)
Alberi binari
il
grado
di un nodo qualsiasi è al massimo uguale a 2, ovvero quando ciascun nodo ha al massimo due figli che sono chiamati "figli sinistro" e "figlio destro"
Profondità
d di un nodo u di un albero con radice r è la lunghezza dalla radice al nodo u. Se u = r allora la profondità è zero
L’
altezza
di un albero è la massima profondità rintracciabile nell’albero
Visitare un albero
in
ordine
(in order)
2 more items...
in
pre-ordine
(pre-order)
1 more item...
in
post-ordine
(post-order)
2 more items...
Quando la differenza tra la massima profondità e la minima profondità rintracciabili in un albero non è maggiore di 1 allora si dice che l'albero è
bilanciato
Nel caso di un albero binario, si dice che questo è
perfettamente bilanciato
quando tutte le foglie sono al medesimo livello
Le
foglie
dell'albero invece sono tutti quei nodi che hanno grado nullo
Da ciò ne consegue che se il grado è 0 o 1, allora l'albero è una
lista lineare
Possiamo anche dire che un albero è un grafo nel quale due vertici qualsiasi sono connessi da uno e un solo cammino
B-tree
Un albero bilanciato o B-tree si dice bilanciato perché la differenza tra profondità massima e minima è al più 1. Quello riportato di seguito è un albero di ordine 5 perché ha un massimo di 4 chiavi con un massimo di 5 figli per nodo
un B-tree di ordine m soddisfa tutte le seguenti condizioni:
ogni nodo ha al massimo m figli
un nodo che non è foglia con k figli contiene k—1 chiavi
la radice ha almeno due figli
ogni nodo che non è foglia (eccetto la radice) ha almeno ⌈m/2⌉figli
tutte le foglie hanno la stessa profondità
B-tree e B+-tree
I B-tree sono particolarmente vantaggiosi per la loro efficienza nella gestione dei dati perché se ci sono n ≥ 1 nodi in un B-tree di altezza h e grado t ≥ 2, allora si ha che l'altezza h non è più grande del logaritmo della metà del numero di nodi
Formula slide
Una variante maggiormente utilizzata del B-tree è il B+-tree dove le foglie sono collegate tra loro in modo da passare da una all'altra senza dover risalire l'albero (il "+" nel nome indicato proprio questo)
Ricerca
Si parte dalla radice trasferendo in memoria il blocco con le sue chiavi
Si ricerca k nel blocco trasferito: se è presente, la ricerca è terminata
Altrimenti, se k è minore della chiave più a sinistra del nodo, allora si trasferisce i nodo puntato dal puntatore di sinistra (se non è nullo); se k è maggiore della chiave più a destra allora si trasferisce il nodo puntato dal puntatore più a destra (se non è nullo); se è compreso tra due chiavi del nodo allora si trasferisce il nodo puntato dal puntatore compreso tra le due chiavi (se non è nullo). Si procede quindi in ricorsione dal punto 2
Se il puntatore in questione è nullo, la chiave non è presente
Tabelle di hash
La tabella di hash è una struttura dati usata per mettere in corrispondenza una data chiave con un dato valore
disegno slide
Una tabella di hash è un vettore di taglia n, ovvero formato da n
bucket
o contenitori che utilizza una
funzione di hash h(k)
che riceve come argomento una chiave k e restituisce un numero naturale compreso tra 0 ed n—1.
Operazioni su tabelle di hash
l
'inserimento:
ovvero cerco il bucket in corrispondenza di k e scrivo il bucket se è libero
la
ricerca
: cerco il bucket in corrispondenza di k e restituisco l'esito della ricerca
Gestione delle collisioni
Collisione
: ogniqualvolta ci sono due chiavi su cui la funzione di hash ci da lo stesso risultato
La collisione sarà tanto più frequente quanto più sarà frequente la collisione su alcuni bucket. Ciò che si può fare per mitigare questo effetto è distribuire uniformemente la probabilità di collisione su tutti i bucket. Due metodi per gestire le collisioni:
concatenamento
(chaining o catena di overflow)
1 more item...
l'
indirizzamento aperto
(open adressing)
1 more item...
la
cancellazione
: cerco il bucket in corrispondenza di k e libero il bucket
Indici
Un indice è una struttura dati i cui elementi sono chiavi
Organizzazione degli indici
Un record è un insieme di campi
L'associazione tra chiave e record corrispondente avviene mediante l'indirizzo di memoria che, nel caso di accesso diretto su disco, è
l'indirizzo del blocco che contiene il record
Una chiave ha due caratteristiche
una chiave è d'
identificazione
quando c'è un solo record per essa
una chiave è
d'ordinamento
quando i record sono ordinati per essa
Calcolo del numero di blocchi
Formula ed esempio slide