Alberi – Introduzione
Tra i problemi di base che la programmazione deve affrontare vi è quello di rappresentare nella maniera più adeguata, più economica e più semplice possibile tutti i tipi di dati che si possono incontrare nella implementazione di algoritmi destinati alla soluzione dei più svariati problemi.
È stato a questo fine introdotto il concetto di Tipo. Con esso si sono caratterizzati dati numerici di tipo intero, decimale, caratteri, strutture come i vettori a una o più dimensioni, record con i quali si rappresenta, con un’unica struttura, dati di natura diversa, le liste che sfruttando lo strumento dei puntatori permettono di superare quel vincolo di dimensioni predeterminate che strutture del tipo array impongono.
Alberi – Introduzione (segue)
In maniera analoga è possibile introdurre nuove strutture che siano in grado di rappresentare dati, o insiemi di dati, legati tra loro da una qualche relazione.
A tal fine ricordiamo che, in matematica, dato un insieme di elementi S = {x1,x2,…,xn}, dicesi relazione R su S, ogni sottoinsieme del prodotto cartesiano SxS.
Per indicare che l’elemento xi è nella relazione R con l’elemento xj si scrive: xi R xj.
Alberi – Introduzione (segue)
Una relazione binaria su un insieme S di n elementi può essere rappresentata tramite una matrice quadrata di ordine n, in cui l’elemento di indici i e j vale 1 se xi R xj, zero altrimenti.
Tale matrice è detta matrice di adiacenza.
Alberi – Introduzione (segue)
Essa può anche essere rappresentata graficamente nel seguente modo: ogni elemento xi di S è rappresentato da un punto del piano, ed ogni coppia (xi , xj), appartenente ad R, è rappresentato da un arco congiungente xi con xj.
Questa rappresentazione grafica è detta grafo.
Alberi – Introduzione (segue)
Alberi – Introduzione (segue)
Esempi di problemi reali che possono essere rappresentati adeguatamente da un grafo sono ad esempio la rete stradale di una regione. Possiamo infatti riprodurre le connessioni tra diversi comuni, insediati in un dato territorio, attraverso un grafo come si può vedere in figura. Ogni comune è identificato da un punto (detto nodo del grafo) e la connessione tra due comuni è raffigurata da un segmento che unisce i due punti (detto arco).
Ogni arco può avere un suo peso che, ad esempio, rappresenta la distanza tra i due nodi che esso connette, oppure il tempo medio necessario per percorrere la distanza tra i due nodi (città).
Alberi – Introduzione (segue)
Alberi – Introduzione (segue)
Uno dei tanti problemi che si incontrano sui grafi è, ad esempio, l’individuazione del minimo percorso tra due assegnati nodi.
Nel grafo di figura, sono presenti degli archi a cui sono associati dei pesi rappresentanti delle lunghezze.
Il percorso minimo tra i nodi A-D è quello segnato con il tratto intero mentre il percorso minimo tra i nodi A-F è quello segnato tratteggiato.
Alberi – Introduzione (segue)
Come precedentemente ricordato un grafo può essere rappresentato dalla sua matrice di adiacenza nella quale le righe e le colonne identificano i nodi del grafo mentre gli elementi diversi da 0 rappresentano, nel caso in esame, le distanze fra i nodi. Gli elementi in cui appare lo 0 implicano che tra i due nodi che lo identificano non c’è nessuna relazione.
Alberi – Introduzione (segue)
Se in un grafo è possibile, a partire da un nodo, fare un percorso che ci riporti sul nodo stesso, senza percorrere mai lo stesso arco, diremo allora che quel percorso è un circuito o ciclo. Ad esempio in fig.a {A,B,E,F,A} costituisce un circuito.
Alberi – Introduzione (segue)
Si definisce albero un grafo senza circuiti come mostrato in figura.
Gli Alberi come strutture dati
Ci occuperemo in questo corso di particolari tipi di alberi: gli alberi binari, cioè quegli alberi nei quali ogni nodo può essere al più connesso ad altri due nodi.
La rappresentazione attraverso un albero binario di un insieme di dati permette di sviluppare algoritmi di ricerca delle informazioni molto efficienti.
Un Search Tree (o albero di ricerca) memorizza informazioni in maniera tale che possano essere ritrovate molto velocemente e le operazioni di inserimento e cancellazione dei nodi, cioè delle informazioni, sono molto efficienti.
Definizioni
- Un albero è binario se ogni nodo è al più collegato ad altri due;
- Un albero binario è:
- l’albero vuoto
- oppure è costituito da una radice, da un sottoalbero sinistro e da un sottoalbero destro;
- L’albero è una struttura ricorsiva non lineare.
- I suoi elementi sono detti nodi.
Gli Alberi come strutture dati
I due disegni rappresentano due alberi uguali in termini di nodi ma due alberi binari diversi in quanto nel primo albero il nodo B ha un sottoalbero sinistro C, mentre, nel secondo albero, C è sottoalbero destro.
Gli Alberi come strutture dati (segue)
Per le liste abbiamo introdotto nodi costituiti da un struttura contenente il valore dell’informazione e un puntatore al nodo successivo.
Nel caso degli alberi utilizziamo nodi con una struttura contenente l’informazione (o chiave) e due puntatori uno indirizzato ad un nodo posto a destra ed uno indirizzato ad un nodo posto a sinistra, come in figura.
Albero Binario
Un albero binario. Esso ha una radice o root, e dei sotto alberi, destri e sinistri.
Albero Binario (segue)
Un esempio di albero binario contenente dei nomi di persona è il seguente. I puntatori a NULL sono indicati con il segno grafico ⊥.
La relazione che con questo albero si può pensare sia rappresentata è che ogni nodo rappresenta il padre di al più due figli ai quali è connesso.
Sotto Albero
Definiamo sotto albero ogni nodo in cui almeno un puntatore non è uguale a NULL ma punta ad almeno un altro nodo o sotto albero.
Definiamo radice di un sotto albero quel nodo che punta ad almeno un altro nodo (NB Negli alberi binari si può al massimo puntare a due nodi (destro e sinistro).
Sotto Albero (segue)
Un albero può essere definito attraverso la sua radice, il nodo a partire dal quale si possono raggiungere tutti gli altri nodi della struttura.
Un albero (sotto albero), che punta a NULL e cioè non contiene nodi è detto albero (sotto albero) vuoto.
Albero binario
Nella figura seguente si illustrano graficamente le definizioni di:
- Sotto_albero
- genitore
- figlio
- fratello
- foglio
- cammino
Mentre definiamo come:
- Livello di un nodo A il numero di archi che bisogna attraversare per andare dalla radice ad A.
- Altezza dell’albero il numero massimo di livelli dell’albero
Albero Binario (segue)
Definizione
Un albero binario è ordinato, e viene anche chiamato albero binario di ricerca, binary search tree (BST), quando il campo chiave di ogni nodo è minore del campo chiave di ogni nodo del suo sottoalbero destro ed è maggiore del campo chiave di ogni nodo del suo sottoalbero sinistro.
Un esempio di BST
In questo caso l'ordine è quello lessicografico.
Un esempio di BST
Gli stessi dati possono essere contenuti in alberi BST di forma diversa.
