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.
E’ 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.
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.
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 .
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 orientato congiungente xi con xj.
Questa rappresentazione grafica è detta grafo.
Esempi di problemi reali che possono essere rappresentati
adeguatamente da un grafo sono ad esempio la rete stradale
di una regione. Possiamo infatti rappresentare le connessioni
tra diversi comuni, insediati in un dato territorio, attraverso un
grafo come si può vedere in figura. Ogni comune è
rappresentato da un punto (detto nodo del grafo) e la
connessione tra due comuni è rappresentata 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à).
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
B
5
D
2
3
20
A
D
1
1
15
15
F
C
5
2
3
20
A
B
C
3
E
Min(A-D) = {A,B,E,F,C,D} -->14
F
3
E
Min(A-F) = {A,B,E,F} -->11
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.
B
C
5
D
1
15
F
A
2
3
20
A
A
3
E
B C D
E F
5
0 20
0 15
0
0
3
0
2
0
1
0
0
B
5
C
0
0
D
20
0
2
E
0
3
0
0
F
15
0
1
0
3
3
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.
B
C
5
2
3
20
A
D
1
15
F
3
E
Si definisce albero un grafo senza circuiti come mostrato in
figura.
B
C
5
20
A
D
1
15
F
3
E
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
A
A
B
D
B
D
C
C
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.
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.
P_sin
P_sin
chiave
P_des
chiave
P_des
P_sin
chiave
P_des
Un albero binario si presenta come in figura.
Esso ha una radice o root, e dei sotto alberi, destri e sinistri.
Albero Binario
Radice (root)
Sotto albero
Un esempio di albero binario contenente dei nomi di persona è il
seguente. I puntatori a NULL sono indicati con il segno grafico
Ugo
Carlo
Giulio
Emma
Anna
Carla
Guido
Peppe
Maria
Angela
Nicola
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.
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).
Radice
xxx
yyy
zzz
Sottoalbero
Sottoalbero
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.
Radice
xxx
yyy
zzz
Sottoalbero
Sottoalbero
NULL
Sottoalbero
vuoto
Nella figura seguente si illustrano graficamente le
definizioni di:
Sotto_albero, genitore, figlio, fratello, foglia, 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
Altezza dell’albero= Massimo numero di livelli
H=3
Albero Binario
Radice (root)
Livello del nodo X = 3
Cammino
(path)
Sotto albero
Nodi fratelli
Genitore
X
Figlio
Foglie