Alberi

L’albero è una struttura dati dinamica gerarchica, che possiede una radice, o nodo padre, che è l’unico nodo dell’albero che non ha padre. Scendendo in profondità, abbiamo i figli del nodo padre, che a loro volta possono avere altri figli. L’ultimo livello degli alberi, è costituito dalle foglie. Le foglie sono i nodi che non possono avere figli. Ricordate che, ogni nodo ha un padre, tranne la radice, che come ho detto prima, E’ L’UNICO NODO CHE NON POSSIEDE UN PADRE.

Di un nodo possiamo conoscere IL GRADO, che corrisponde al numero dei figli. Non è difficile capire quindi, che le foglie hanno grafo 0, visto che non possono avere figli.

Un albero può essere visitato tramite vari tipi di visita, partiamo col descrivere la VISITA PER LIVELLI. Per implementare questo algoritmo dobbiamo fare uso di un’altra struttura dati, che è la CODA, o QUEUE. (La coda ricordiamo, è una struttura dati FIFO (First in First Out, ovvero il primo elemento ad essere inserito in coda, sarà anche il primo ad essere estratto da essa) L’idea in pseudolinguaggio delle visita per livelli è questa:

VISITA IL NODO RADICE

INSERISCILO IN CODA

while(CODA NON VUOTA)

{

ESTRAI UN NODO DALLA CODA

for(i=0; i<grado_nodo; i++)

{

VISITA L’IESIMO FIGLIO DEL NODO

METTILO IL CODA

}

}

STRUTTURA DINAMICA GERARCHICA: ALBERO BINARIO (BINARY TREE)

Un albero binario è un tipo di albero che ha al massimo due figli per ogni nodo e può definirsi completo, o quasi completo.

Si dice completo, un albero binario che ha esattamente due figli per ogni nodo, escluse ovviamente le foglie.

Si dice quasi completo, un albero binario che ha tutti i suoi livelli completi, tranne al più l’ultimo. Ad esempio l’ultimo livello è riempito da sinistra, ma mancano eventualmente delle foglie a destra.

Il numero delle foglie è calcolabile con la seguente formula matematica: 2^(livelli-1)

Il numero dei nodi è calcolabile con la seguente formula matematica: (2^livelli)-1

Abbiamo tre tipi di visita per visitare un albero binario: VISITA PREORDER, INORDER E POSTORDER

La visita PREORDER è una visita che parte col visitare la RADICE, poi IL SOTTOALBERO SINISTRO, e poi il SOTTOALBERO DESTRO

La visita INORDER è una visita che parte col visitare SOTTOALBERO SINISTRO, LA RADICE e poi IL SOTTOALBERO DESTRO.

La visita POSTORDER è una visita che parte col visitare SOTTOALBERO SINISTRO, SOTTOALBERO DESTRO e in ultima la radice.

STRUTTURA DINAMICA GERARCHICA: ALBERO BINARIO DI RICERCA (SEARCH BINARY TREE)

Gli alberi binari di ricerca, sono degli alberi ordinati in base a una chiave. Ovvero è un particolare albero che tramite la visita inorder, permette di accedere alle informazioni in ordine crescente di chiave key(NODO). La ricerca binaria in questi alberi è particolarmente semplice ed efficiente. Ma non in tutti i casi!

L’albero binario di ricerca gode di due proprietà fondamentali e che lo definiscono tale:

Se prendo un nodo Y che è un nodo qualsiasi dell’albero si ha che:

1) Per ogni nodo x del sottoalbero sinistro di Y, si ha che key(x)<=key(y)

2) Per ogni nodo z del sottoalbero destro di Y, si ha che key(z)>=key(y)

Dunque in un albero binario di ricerca, si ha che:

1) La chiave di valore minimo, si trova nella foglia del sottoalbero più a sinistra. Ovvero la prima foglia che si visita usando la visita INORDER.

2) La chiave di valore massimo, si trova nella foglia del sottoalbero più a destra. Ovvero l’ultima foglia che si visita usando la visita INORDER.

STRUTTURA DINAMICA GERARCHICA: HEAP

Un heap è un albero binario quasi completo, in cui i nodi sono etichettati tramite chiavi.

Lo heap gode di una proprietà fondamentale, ovvero:

Se x è un nodo qualsiasi dell’heap, ad esclusione della radice, si ha che: key(x)<=key(padre(x))

Ovvero, l’elemento con valore massimo, è SEMPRE situato nel nodo radice.

PROCEDURA HEAPIFY

La procedura Heapify consente di ripristinare la proprietà heap fondamentale descritta in precedenza, quando trasformiamo un array in un heap, oppure un albero binario in un heap.

Per ripristinare la proprietà heap, si considera un nodo e i suoi figli: si determina il figlio con chiave massima e, se non verificano la proprietà heap, si scambia tale chiave con quella del padre. Se lo scambio è avvenuto, si scende/sale nel relativo sottoalbero per andare a ripristinare anche lì la proprietà heap, se non è verificata.

Questa proceduta, può essere eseguita in due modi: BOTTOM-UP, oppure TOP-DOWN. La Bottom Up parte dai livelli più bassi, ovvero dalle foglie ed esegue il ripristino della proprietà heap fino alla radice. La Top-Down, parte dalla radice ed esegue il ripristino della proprietà heap fino alle foglie.

Cosa importante da tenere a mente, è che le foglie costituiscono già di per se degli heap, quindi è opportuno partire dal penultimo livello, quando si esegue la visita BOTTOM-UP.