03. Alberi e grafi

Albero o tree

Una struttura ad albero è costituita da elementi di tipo nodo e di tipo arco, collegati tra loro, come illustrato in figura.

Gli archi sono orientati e per ogni nodo si distinguono gli archi entranti e quelli uscenti. Di solito sugli archi non sono rappresentate frecce per indicare il verso perché esso si evince facilmente dal contesto, una volta che si è identificato il nodo radice.

Solitamente in una rappresentazione grafica la radice è il nodo che occupa la posizione più in alto.

La nomenclatura che si accompagna agli alberi è un misto di termini derivati dalla botanica, dalla matematica e dalla genealogia:

• nodi: sono tutti i circoli rappresentati in figura; ai nodi si accompagnano i dati in forma strutturata;

• rami: sono gli archi che collegano i nodi;

• radice: è l'unico nodo che non ha archi entranti;

• foglie: sono i nodi che non hanno archi uscenti;

• nodo figlio: il nodo figlio di un nodo x è un nodo che ha un arco entrante che parte da x;

• nodo padre: il nodo padre di un nodo x è quell'unico nodo da cui parte l'arco entrante nel nodo x; la radice non ha un nodo padre;

• albero binario: è un albero nel quale ogni nodo ha al più due nodi figli;

• livello di un nodo: è la distanza dalla radice, espressa come numero di archi di cui è composto il cammino dalla radice al nodo; la radice è a livello 0;

• altezza (o profondità) dell'albero: massimo livello dei nodi dell'albero;

• albero bilanciato in altezza: è un albero in cui le foglie si trovano tutte al più su due livelli consecutivi.

Una caratteristica fondamentale degli alberi è che gli archi sono connessi sempre in modo da non creare aree chiuse e quindi dei ricircoli.

Gli alberi si prestano ad organizzare dati in modo efficace in numerosi scenari.

La situazione più ricorrente e comune anche al di fuori del contesto informatico, è relativa alle strutture gerarchiche, come ad esempio l'organigramma aziendale o la sua strutturazione in reparti.

Qualora la struttura ad albero sia adeguata ad organizzare dei dati, il progettista ha il vantaggio di disporre di una serie di strumenti già collaudati e sorretti da una copiosa letteratura di settore.

Ad esempio la struttura ad albero si presta ad implementare un indice basato su chiavi.

La ricerca in tale struttura avviene in modo molto efficiente e l'inserimento di nuove chiavi è gestito in modo molto rapido.

L'albero raffigurato in figura è un albero binario di ricerca su chiave primaria.

Tale albero è caratterizzato dal fatto che tutte le chiavi il cui valore è maggiore di quello della radice, si trovano nel sottoalbero di destra (evidenziato in azzurro) mentre tutte le chiavi con un valore minore si trovano nel sottoalbero di sinistra (evidenziato in giallo).

Questa caratteristica si ripete per tutti i nodi.

Questa proprietà dell'albero consente di ricercare una chiave, a partire dalla radice, con un numero massimo di confronti pari a log N, dove N è il numero di chiavi presenti nell'albero e log è il logaritmo binario di N.

Per fare un po' di esempi la ricerca su un miliardo di chiavi richiede al massimo log 1000000000 ≅ 30 confronti, mentre la ricerca su due miliardi di chiavi richiede circa 31 confronti.

A partire dall'albero raffigurato nell'immagine precedente, analizziamo i passi che devono essere compiuti per effettuare la ricerca di una chiave, ad esempio della chiave 19:

• confronto di 19 con la radice che vale 50: poiché la chiave cercata è minore di 50, la chiave si trova nel sottoalbero di sinistra;

• confronto di 19 con 17 (quest'ultimo nodo può essere visto come radice del sottoalbero evidenziato in giallo): poiché 19 è maggiore di 17, la chiave cercata si trova nel sottoalbero destro del nodo 17;

• confronto di 19 con 23: poiché 19 è minore di 23 la chiave cercata si troverà nel sottoalbero sinistro di 23;

• confronto di 19 (chiave cercata) con 19 (nodo del sottoalbero): i due valori sono uguali e quindi la chiave è stata trovata.

Naturalmente anche l'inserimento di una nuova chiave deve essere fatto senza alterare la "caratteristica strutturale" dell'albero.

Appositi algoritmi consentono di effettuare agevolmente inserimenti e ricerche.

Senza preoccuparsi del bilanciamento dell'albero, l'inserimento di una chiave inesistente si effettua procedendo come per la ricerca con la differenza che ad un certo punto non si può più procedere perché si giunge su un nodo che non ha il figlio nel sottoalbero verso cui ci si dovrebbe dirigere. In quel punto si innesta il nuovo nodo con la nuova chiave. Nella seguente immagine è mostrato l'inserimento del nodo con chiave 53 (in giallo).

Il caso in cui la chiave dovesse già esistere corrisponde ad un tentativo di "violazione" sull'indice, perché un indice su chiave primaria ha sempre tutte le chiavi diverse.

Grafi

I grafi sono una struttura molto efficace per organizzare dati in moltissime circostanze. Per completezza bisogna aggiungere che i grafi rivestono grande importanza anche in moltissime altre aree applicative che includono la matematica, la topologia, la geometria dei poliedri, la teoria degli automi ecc.

Storicamente si attribuisce l'invenzione di questo modello al matematico Eulero che fu chiamato ad esprimersi su un problema noto come l'attraversamento dei ponti di Königsberg nell'anno 1736.

La questione era così posta: è possibile organizzare la visita della citta in modo tale da attraversare tutti i ponti della città una sola volta?

La mappa allegata raffigura la città di Königsberg così some si presentava in quegli anni, quando apparteneva alla Prussia orientale (oggi la città si chiama Kaliningrad ed appartiene alla Russia).

Per rispondere a questo problema, Eulero gettò le basi di quella che oggi è indicata come teoria dei grafi.

Informalmente si può dire che un grafo è un insieme di nodi collegati tra loro tramite archi.

Questa definizione è simile a quella degli alberi ma non esclude la possibilità di creare ricircoli. E' anche possibile che un arco colleghi un nodo con se stesso.

Se gli archi sono orientati, il grafo si dice orientato. In questo caso due nodi possono essere collegati tra loro con due differenti archi, purché orientati nei due versi.

Su un grafo i dati possono essere associati sia ai nodi che agli archi, con significati diversi dipendenti dal contesto.

Ad esempio un grafo può essere utilizzato per rappresentare la viabilità. In questo caso i nodi rappresentano gli snodi stradali mentre gli archi fanno riferimento alle strade. Sugli archi può essere riportato il tempo di percorrenza o la distanza stradale come nel seguente esempio.

Gli algoritmi che si sviluppano a partire dai grafi sono generalmente più articolati rispetto a quelli usati con gli alberi e anche la complessità algoritmica normalmente è maggiore.

Sito: 7ecnologie

Sezione: 10. Algoritmi e strutture dati

Capitolo: 03. Alberi e grafi

Indice dei capitoli: 00. Risorse - 01. Tipi base - 02. Strutture lineari dinamiche - 03. Alberi e grafi