Programmazione 2

Rappresentazione di un albero binario completo con n=2^k - 1 nodi

Un albero binario completo con n=2^k - 1 nodi è rappresentato tramite un array a =(a1, a2, ..., an) e per qualsiasi nodo a si ha:

1. Se i diverso da 1, si ha il padre (a_i) = a_k dove k = [i/2];
2. Se i = 1 allora a è radice e non ha padre.
3. Se 2i <= n si ha un figlio sinistro (a_i) = a_k dove k=2i;
4. Se 2i > n allora a non ha figlio sinistro;
5. Se 2i + 1 <= n si ha un figlio destro (a_i) = a_k dove k=2i + 1;
6. Se 2i + 1 > n allora a non ha figlio destro.

Tali formule non sono applicabili in C, poiché lo shape di un array C è [0 ... n-1]. Una possibile soluzione al problema è quella di usare un array C sovradimensionato di un elemento, di cui la prima componente (quella di indice 0) rimane inutilizzata. In questo modo lo shape utilizzato diventa [1 ... n] e le formule appena riportate possono essere applicate senza alcun problema.

Uso di lista multipla

Un albero binario può essere memorizzato attraverso l'uso delle

1. Permettono di evitare eventuali shifting (a causa di uso dei puntatori)
2. Non è necessario completare l'albero
3. Il doppio puntatore facilita l'identificazione del figlio sinistro e di quello destro.

Algoritmi di visita iterativi di un albero binario

L'algoritmo di visita deve necessariamente far uso di uno stack, dove conservare l'informazione sull'ordine dei nodi di cui non si è completata la visita dei sottoalberi.

Lo stack va gestito esplicitamente nell'algoritmo di visita iterativo mentre va gestito implicitamente nell'algoritmo di visita ricorsivo. Lo stack conserva i nodi di cui non si è ancora visitato il sottoalbero.

Algoritmi di visita ricorsivi di un albero binario

Ha gli stessi procedimenti di quello sopra ma qui con l'istruzione return si torna indietro e si conservano i nodi per le successivi esplorazioni. La function si

conclude quando il nodo visitato è una foglia dell'albero.

A cura di Giovanna Di Mauro

Alberi tramati

Gli alberi tramati sono quegli alberi in cui è possibile risalire da ogni nodo al suo nodo padre grazie agli archi di ritorno, questi archi permettono la risalita al nostro padre in modo semplice.

La struttura di un nodo contiene i seguenti campi:

1. Informazione, che può essere diviso in sottocampi;
2. Grado del nodo, ossia il numero di figli;
3. Puntatori ai figli, è un array di puntatori, ognuno dei quali punta ad un figlio del nodo corrente;
4. Puntatore al padre, un altro puntatore che punta al padre del nodo corrente. La struttura lista multipla di un albero tramato presenta oltre i puntatori per figlio destro e sinistro, un altro puntatore che è il padre.

A cura di Giovanna Di Mauro

Alberi binari di ricerca

Un albero di ricerca in un contesto informatico è un albero binario i cui valori dei figli di un nodo sono ordinati. Solitamente a sinistra vi

Sono valori minori di destra. Ricerca binaria mediante albero binario di ricerca.

Tale organizzazione rende estremamente performante il meccanismo della ricerca binaria in quanto per ogni livello dell'albero è effettuato un singolo confronto e poiché la profondità di un albero è pari al floor di log (n+1), la complessità asintotica risulta logaritmica e quindi molto efficiente.

Può essere scritto in maniera ricorsiva. Quando si confronta il nodo corrente con la chiave che si sta cercando, possono verificarsi 3 casi:

1. I due valori coincidono
2. Il valore della chiave è minore del valore del nodo, si continua la ricerca nel sottoalbero sinistro
3. Il valore della chiave è maggiore del valore del nodo, si continua la ricerca nel sottoalbero destro

Escludendo il caso banale in cui il contenuto del nodo corrente coincide con la chiave oppure quello in cui si sono esaurite tutte le componenti dell'albero binario. Si innesca una

autoattivazione sul sottoalbero destro o sinistro che può essere visto come un nuovo albero binario giustificando la descrizione ricorsiva dell'algoritmo.

La funzione ritorna un char, infatti è come se fosse un tipo logico: se la chiave non è presente ritorna 0 (false), se la chiave è presente ritorna 1 (true).

Abbiamo due parametri:

1. La chiave e supponiamo che il suo tipo sia stato dichiarato come globale
2. E il puntatore che punta ai nodi dell'albero e supponiamo che il suo tipo sia stato dichiarato globale.

La function ricorsiva inizia con un costrutto IF dove si controlla uno dei casi banali, quello dove la chiave cercata non è presente. Questo controllo lo si effettua verificando che il puntatore sia NULL, ciò vuol dire che siamo andati oltre la foglia dell'albero. In questo caso si ritorna a 0.

Altrimenti si entra nella ricerca andando ad analizzare le possibilità elencate in precedenza. Si

La costruzione di un albero binario di ricerca viene effettuata in questo modo:

1. Consideriamo il flusso di dati (ad esempio un array)
2. Per ogni dato in arrivo lo si confronta con la radice per poi farlo scendere nel sottoalbero opportuno fino ad assegnargli la posizione definitiva
3. La posizione viene determinata confrontando il valore della chiave con quello del nodo corrente, stabilendo dunque se si può trattare di un suo figlio destro o sinistro.
4. Arriva la prima informazione e la vado a mettere nella radice, arriva la seconda, la confronto con la radice, dall'esito del confronto stabilisco se questa informazione dovrà scendere nel sottoalbero sinistro o nel sottoalbero destro.

A cura di Giovanna Di Mauro

Bilanciamento

Il bilanciamento di un albero binario dipende fortemente dall'ordine di arrivo dei nodi. Un albero binario ordinato risulta molto efficiente nella ricerca solo se questo si presenta bilanciato. Nel caso di un albero sbilanciato invece, il costo

dell'algoritmo degrada ad una complessità dell'ordine di n, ossia lineare.

Struttura dati Heap

Un heap è una struttura dati utilizzata in informatica (un albero binario completo o quasi completo) usato per la memorizzazione di collezione di dati (dette dizionari).

Proprietà dell'heap: Se x è un qualsiasi nodo dell'heap si ha key(x) <= key(padre(x)). Ne consegue che in un heap, la chiave di valore massimo è memorizzata nella radice.

Memorizzazione di un Heap

Poiché l'heap di fatto è un albero binario la sua implementazione riprende le tecniche già viste in precedenza di indicizzazione su array statici o di costruzione con liste multiple.

Nel caso di memorizzazione con array statici, poiché l'heap deve essere un albero binario almeno quasi completo ne consegue che non vi saranno sprechi di memoria nella sua implementazione.

La mancanza di alcune foglie determina l'eliminazione di componenti

Che nell'array, si sarebbero trovate in fondo e che dunque non vanno colmate con nodi fittizi.

Traduzione di un array in un heap - costruzione top-down

Le componenti dell'array struttureranno un albero binario quasi completo rispettante la proprietà di heap.

L'heapify è l'operazione che consente di ripristinare la proprietà heap sui nodi di un albero binario quasi completo (coinvolge nodo e figli).

A cura di Giovanna Di Mauro

Quando arriva una chiave viene inserita nella prima componente disponibile dell'array, si verifica la proprietà dell'heap e si ripristina dove non vale. Inizialmente l'array è vuoto non contiene informazioni viene inserita nella prima componente dell'array.

L'albero binario è composto solo dalla radice quindi non viene avviata la procedura per verificare la proprietà dell'heap.

Arriva la seconda informazione, si controlla se questi nodi verificano le

proprietà dell'heap se no la procedura heapify li scambia. E così via. Quindi: per ogni inserimento si effettuano le seguenti operazioni:

1. Si aggiunge il nuovo elemento nella prima componente disponibile dell'array
2. Se non sono nell'ordine corretto, i due nodi vengono scambiati e si ritorna al passo precedente.

Costruzione bottom-up di un heap

Ora invece partiamo da un albero binario e vogliamo tradurlo in heap. Usiamo la procedura heapify in bottom-up (basso verso l'alto). (quella vista sopra) Il vantaggio è che sicuramente i nodi foglie sono degli heap a se stanti, quindi applicare l'heapify è possibile. Il meccanismo si ripete finché non arriviamo alla radice.

Capitolo 10: Strutture dati dinamiche reticolari

Grafo orientato e non orientato

Il grafo è una struttura reticolare ed è un insieme di nodi (o vertici) e archi (o lati). Possono essere di due tipi:

1. Un grafo non orientato è un grafo che presenta

archi che possono essere percorsi in entrambi i sensi (non unidirezionali).

Un grafo orientato presenta archi a cui è assegnato un verso di percorrenza (unidirezionali).

A cura di Giovanna Di Mauro

Un grafo può essere rappresentato mediante una matrice le cui righe identificano gli archi e le cui colonne rappresentano i nodi.

Nella matrice di un grafo orientato vi sono presenti 3 valori:

1. -1 -> indica l'origine
2. 0 -> assenza di collegamento
3. 1 -> punto di arrivo, ossia la fine

Cammino di un grafo

Per cammino si intende una lista di vertici connessi da archi che va da X ad Y.

Abbiamo due tipi di cammini:

1. Cammino semplice: in cui non è possibile percorrere 2 volte lo stesso nodo
2. Cammino minimo: un cammino semplice composto dal minimo numero di nodi e archi possibili.

Rap