Universita' di Ferrara
Facolta' di Scienze Matematiche, Fisiche e Naturali
Laurea Specialistica in Informatica
Algoritmi Avanzati
Grafi e Alberi
Copyright © 2006-2009 by Claudio Salati.
Lez. 8
1
GRAFI
• Un grafo e' una coppia G = (V, E ) dove
• V = insieme non vuoto e finito di vertici (o nodi)
• E = insieme di lati
• Se il grafo e' orientato
• un lato e' una coppia ordinata di vertici (v, w), dove v e' chiamato
coda e w testa
• un lato orientato puo' essere rappresentato come: v  w
• e' (v, w)  (w, v)
• possono esistere lati v  v
• Se il grafo e' non orientato
• un lato e' una coppia non ordinata di vertici {v, w}
• un lato non orientato puo' essere rappresentato come: v  w
• e' (v, w) = (w, v)
• non possono esistere lati v  v
2
GRAFI
• Qui indicheremo comunque un lato come (v, w)
indipendentemente dal fatto che il grafo sia o meno orientato
• E' POSSIBILE ASSOCIARE UN COSTO A CIASCUN LATO
• SE (v, w)  E ALLORA SI DICE CHE w E' adiacente A v
• IN_DEGREE(v) E' IL NUMERO DI NODI A CUI v E'
ADIACENTE
• OUT_DEGREE(v) E' IL NUMERO DI NODI ADIACENTI A v
• SE UN GRAFO E' NON ORIENTATO, PER TUTTI I SUOI NODI
E':
IN_DEGREE = OUT_DEGREE
• Esercizio:
Quanti sono al massimo i lati di un grafo orientato con n nodi?
Quanti sono al massimo i lati di un grafo non orientato con n
nodi?
3
GRAFI
•
PATH: SEQUENZA DI NODI DELLA FORMA
(v[1], v[2]), (v[2], v[3]), ..., (v[n-1], v[n])
dove (vj, vk) e' un lato del grafo
•
PATH DA v[1] A v[n]
•
PATH DI LUNGHEZZA (n-1)
•
TRA UN NODO E SE STESSO C'E' SEMPRE UN PATH DI
LUNGHEZZA 0
•
PATH SEMPLICE:
•
SENZA CICLI, O AL MASSIMO CON v[1]=v[n],
•
SENZA PASSARE 2 VOLTE SULLO STESSO
LATO/NODO
•
CICLO: PATH SEMPLICE CON v[1]=v[n] E LUNGHEZZA 1
•
LUNGHEZZA MINIMA DI UN CICLO IN UN GRAFO NON
ORIENTATO: 3
4
RAPPRESENTAZIONE DI GRAFI - 1'
• MATRICE DELLE ADIACENZE:
• BOOLEAN adjacency [# V ][# V ]
• int adjacency [# V ][# V ]
PER TENERE CONTO DEL COSTO DEI LATI
• COMPLESSITA' SPAZIALE: (# V )2
• QUALUNQUE SIA IL NUMERO DEI LATI,
• CHE POTENZIALMENTE E' <<(# V )2
• N.B.: la struttura della matrice delle adiacenze e' congruente
con il fatto che il numero massimo di lati in un grafo orientato e'
pari a (# V )2
• ANCHE LA COMPLESSITA' TEMPORALE DI QUALSIASI
ALGORITMO CHE USI QUESTA STRUTTURA DATI SARA' (#
V )2
SE DEVE INIZIALIZZARE L'ARRAY!
5
RAPPRESENTAZIONE DI GRAFI - 1"
• Se voglio scandire tutti e soli i lati uscenti dal nodo j basta che
cerchi nella riga j gli elementi con valore TRUE: l'operazone ha
costo O(# V )
• Se voglio scandire tutti e soli i lati entranti nel nodo j basta che
cerchi nella colonna j gli elementi con valore TRUE: l'operazone
ha costo O(# V )
• Matrice delle adiacenze per un grafo non orientato:
• la matrice e simmetrica:
il lato (j, k) e' presente (adjacency[j][k]=TRUE) se e
solo se e' presente anche il lato ((k, j)
(adjacency[k][j]=TRUE)
• tutti gli elementi della diagonale principale sono FALSE:
il lato (k, k) non puo' essere presente
• questo conferma che in un grafo non orientato con n nodi ci
sono al massimo n*(n-1)/2 lati: gli elemeti diagonali e quelli
della parte inferiore sono non significativi!
6
RAPPRESENTAZIONE DI GRAFI - esempio
0
1
3
2
BOOLEAN adjacency [4][4] =
{ { 0, 1, 0, 1 },
{ 0, 0, 1, 0 },
{ 0, 0, 0, 0 },
{ 0, 1, 1, 0 },
};
//
//
//
//
lati
lati
lati
lati
0
1
2
3




x
x
x
x
7
RAPPRESENTAZIONE DI GRAFI - 2'
•
INSIEME DEI NODI
•
•
CIOE' LISTA DEI NODI
INSIEME DEI LATI,
•
CIOE' LISTA DEI LATI,
•
CIOE' LISTA DELLE COPPIE (vj, vk)
•
COMPLESSITA' SPAZIALE:
•
IN UN GRAFO INDIRETTO OGNI LATO COMPARE 2 VOLTE,
SIA COME (v, w) CHE COME (w, v)
•
O(# V + # E )
NELLA MATRICE DELLE ADIACENZE I DUE LATI SONO
COLLEGATI ALGORITMICAMENTE:
E[v][ w] == E[w][v]
•
NELLA LISTA DELLE ADIACENZE LA CORRELAZIONE
DEVE ESSERE REALIZZATA CON UN RIFERIMENTO
ESPLICITO
8
RAPPRESENTAZIONE DI GRAFI - 2"
•
IN UN GRAFO E' SPESSO CONVENIENTE POTERE
CANCELLARE LATI E NODI
•
PERCIO' E' CONVENIENTE CHE NELLA
RAPPRESENTAZIONE A LISTA DI ADIACENZE CI SIA IL
DOPPIO LINK AVANTI E INDIETRO,
 COSI' DA POTERE CANCELLARE ELEMENTI RANDOM
IN TEMPO COSTANTE
(SPECIE NEL CASO DI GRAFI NON ORIENTATI DOVE
OGNI LATO HA IL DUALE, E QUESTI SONO TRA LORO
CORRELATI)
9
RAPPRESENTAZIONE DI GRAFI - esempio
typedef struct node *refNode;
typedef struct edge *refEdge;
struct node {
char
*name;
refNode lLink; // doppio link della lista
refNode rLink; // dei nodi
refEdge fromOf; // lista dei lati uscenti
refEdge toOf;
// lista dei lati entranti
};
struct edge {
refNode fromNode; // rif. al nodo coda del lato
refNode toNode;
// rif. al nodo testa del lato
refEdge lLink;
// doppio link della lista
refEdge rLink;
// dei lati
refEdge fromListLLink; //doppio link lista lati uscrefEdge fromListRLink; //enti dallo stesso nodo coda
refEdge toListLLink; // doppio link lista lati entrrefEdge toListRLink; // anti nello stesso nodo testa
10
};
RAPPRESENTAZIONE DI GRAFI - esempio
nodi
NULL
lati
"0"
"1"
NULL
"2"
"3"
11
ALBERO
•
UN ALBERO (NON ORDINATO) E':
•
UN INSIEME DI VERTICI O NODI: V
•
UNA FUNZIONE TOTALE CHILD: V  POWERSET( V )
TALE CHE:
n1n2  CHILD(n1)  CHILD(n2)=
•
! NODO n0 (DETTO RADICE) |  n  V : n0 CHILD(n)
•
( n  V | nn0) ! m  V | n  CHILD(m)
•
 n  V (  {m1, ..., mN}  n = m1  mN = m 
mi+1  CHILD(mi) 
n  CHILD(m))
•
UN NODO n PER CUI CHILD(n) =  E' DETTO FOGLIA
12
ALBERI E GRAFI
•
UN ALBERO E' UN GRAFO IN CUI ESISTE IL LATO (n, m) SE
m  CHILD(n)
•
Un albero e' un grafo
•
ORIENTATO
•
ACICLICO
•
IN CUI IN OGNI NODO DIVERSO DALLA RADICE ENTRA UNO
ED UN SOLO LATO
  n  V | n  n0 : IN_DEGREE(n)=1
•
MENTRE IN_DEGREE(RADICE)=0
(la radice e' l'elemento minimo del grafo)
•
C'E' UNO ED UN SOLO PATH TRA LA RADICE ED OGNI
ALTRO NODO
 Esercizio: come si dimostra?
•
FORESTA: UN GRAFO CHE E' UN INSIEME DI ALBERI
13
ALBERO: relazioni tra i nodi
•
SE m  CHILD(n)
ALLORA
• m E' FIGLIO DI n
• n E' PADRE DI m
•
SE C'E' UN PATH DA n A m ALLORA
• m E' UN DISCENDENTE DI n
• n E' UN ANTENATO DI m
•
OVVIAMENTE UN NODO E' SEMPRE DISCENDENTE ED
ANTENATO DI SE STESSO, PERO' E' UNA RELAZIONE NON
PROPRIA
•
UN NODO E TUTTI I SUOI DISCENDENTI SONO DETTI UN
SOTTOALBERO
14
ALBERO: profondita', altezza, livello
•
LA PROFONDITA' (DEPTH ) DI UN NODO E' LA LUNGHEZZA
DEL PATH DALLA RADICE AL NODO
•
L'ALTEZZA DI UN NODO E' LA LUNGHEZZA DEL PATH PIU'
LUNGO DAL NODO AD UNA FOGLIA SUA DISCENDENTE
•
L'ALTEZZA DI UN ALBERO E' L'ALTEZZA DELLA RADICE
•
IL LIVELLO DEL NODO n E' L'ALTEZZA DELL'ALBERO MENO LA
PROFONDITA' DI n
•
N.B.:
•
La profondita’ di un nodo e’ determinata solo dalla parte di
albero che costituisce il path dalla radice al nodo.
•
L’altezza di un nodo e’ determinata solo dalla parte dell’albero
costituita dal sottoalbero che ha il nodo come radice.
•
Il livello di un nodo dipende da tutto l’albero!
15
ALBERO: profondita', altezza, livello
0
4
2
1
3
1
2
2
3
1
4
0
4
3
2
0
0
1
0
0
0
All'interno dei nodi e' indicata la
loro altezza
0
Profondita'
Livello
16
ALBERO BINARIO
•
UN ALBERO E' ORDINATO SE I FIGLI DI OGNI NODO SONO
ORDINATI (e.g. DA SINISTRA A DESTRA)
•
UN ALBERO BINARIO E':
•
UN ALBERO ORDINATO
•
OGNI NODO HA AL PIU' 2 FIGLI
•
I FIGLI DI UN NODO SONO DISTINTI IN
•
FIGLIO SINISTRO
•
FIGLIO DESTRO
E UN NODO HA NON PIU' DI UN FIGLIO SINISTRO E
NON PIU' DI UN FIGLIO DESTRO
•
IN UN ALBERO BINARIO SI POSSONO OVVIAMENTE
DISTINGUERE SOTTOALBERI DI SINISTRA E DI DESTRA
•
se un nodo ha un unico figlio si puo' distinguere se questo e' di
sinistra o di destra
17
ALBERO BINARIO - visione ADT

albero binario (definizione ricorsiva):

un albero vuoto

una radice con al piu' due figli
 radici di sottoalberi binari
 distinguibili come di-sinistra e di-destra

un albero binario sara' denotato come la tripla ordinata
[e, ts, td]
dove

e indica l'elemento (il valore) associato al nodo radice
dell'albero

ts indica il sottoalbero di sinistra (della radice) dell'albero

td indica il sottoalbero di destra (della radice) dell'albero

ts e/o td possono ovviamente essere un albero vuoto
18
ALBERO BINARIO - visione ADT
 operazioni primitive sull'ADT albero binario:
 costruttori
 NULL o EMPTYTREE
  Tree
 denota un albero vuoto.
 constree()
 Element  Tree  Tree  Tree
 dato un elemento E e due alberi T1 e T2
(eventualmente vuoti) restituisce l'albero [E, T1, T2]
 precondizioni: nessuna
19
ALBERO BINARIO - visione ADT
 operazioni primitive sull'ADT albero binario (continua):
 predicati
 emptyt()
 Tree  BOOLEAN
 dato un albero T, restituisce TRUE o FALSE a
seconda che T sia o meno vuoto
 precondizioni: nessuna
 selettori
 root()
 Tree  Element
 dato un albero non vuoto T=[E, T1, T2] ne
restituisce l'elemento radice E
 precondizioni: !emptyt(T)
20
ALBERO BINARIO - visione ADT
 operazioni primitive sull'ADT albero binario (continua):
 selettori (continua)
 left()
 Tree  Tree
 dato un albero non vuoto T=[E, T1, T2] ne restituisce
il sottoalbero di sinistra T1 (eventualmente vuoto)
 precondizioni: !emptyt(T)
 right()
 Tree  Tree
 dato un albero non vuoto T=[E, T1, T2] ne restituisce
il sottoalbero di destra T2 (eventualmente vuoto)
 precondizioni: !emptyt(T)
21
ALBERO BINARIO - visione ADT

assiomi
1. ├ emptyt(EMPTYTREE) o emptyt(NULL)
2. ├ !emptyt(constree(e, t1, t2))
3. ├ root(constree(e, t1, t2)) == e
4. ├ left(constree(e, t1, t2)) == t1
5. ├ right(constree(e, t1, t2)) == t2

la definizione dell'ADT e' funzionale e costruttiva (vedi
assiomi 4 e 5):


un valore Tree non viene mai modificato da nessuna
operazione (infatti non ci sono trasformatori)
ovviamente avremmo potuto definire un ADT albero binario in
modo diverso
22
ALBERO BINARIO - visione ADT: implementazione
struct Node {elemento
value;
struct Node *sin;
struct Node *des;
};
typedef struct Node *Tree;
#define EMPTYTREE NULL
Boolean emptyt (Tree t) {
return (t == EMPTYTREE);
}
elemento root (Tree t) {
assert(!emptyt(t));
return (t->value);
}
23
ALBERO BINARIO - visione ADT: implementazione
Tree left (Tree t) {
assert(!emptyt(t));
return (t->sin);
}
Tree right (Tree t) {
assert(!emptyt(t));
return (t->des);
}
Tree constree (elemento el, Tree t1, Tree t2) {
Tree t = malloc(sizeof(struct Node));
t->value = el;
t->sin = t1;
t->des = t2;
return t;
24
}
ALBERO BINARIO - visione ADT: esempio d'uso
•
Scrivere una funzione che ritorna il numero di nodi contenuto
nell'albero passatole in ingresso
int findWeight(Tree t) {
return(
emptyt(t) ? 0
: findWeight(left(t)) +
findWeight(right(t)) +
1
);
}
25
ALBERO BINARIO - visione ADT: esempio d'uso
•
•
Inserisce in-ordine un nuovo elemento in un albero in cui
tutti gli elementi sono registrati in-ordine
Un elemento e' presente nell'albero al piu' una volta.
Tree insord(Tree t, elemento el) {
// P = { el  t }
if (emptyt(t))
return constree(el, EMPTYTREE, EMPTYTREE);
else if (lessThan(el, root(t)))
return constree(root(t),
insord(left(t), el),
right(t));
else // greaterThan(el, root(t))
return constree(root(t),
left(t),
insord(right(t), el));
26
}
ALBERO BINARIO - visione ADT: esercizi
•
Consideriamo (come nell'esempio della funzione insord()) un
albero binario in cui gli elementi sono registrati nei nodi in inordine
•
scrivere 3 funzioni:
elemento min(Tree t);
elemento max(Tree t);
Boolean isPresent(elemento el, Tree t);
•
la prima che ritorna l'elemento minimo di un albero non
vuoto,
•
la seconda che ritorna l'elemento massimo di un albero non
vuoto, e
•
la terza che verifica se un elemento dato e' presente o meno
nell'albero (non necessariamente non vuoto)
27
ALBERO BINARIO - visione ADT: esercizi
•
Consideriamo un albero binario in cui gli elementi sono registrati
nei nodi in in-ordine
•
scrivere 3 funzioni:
Tree deleteMin(Tree t);
Tree deleteMax(Tree t);
Tree delOrd(elemento el, Tree t);
•
•
la prima che cancella l'elemento minimo di un albero non
vuoto,
•
la seconda che cancella l'elemento massimo di un albero
non vuoto, e
•
la terza che cancella un elemento dato presente nell'albero
In ogni caso ogni funzione ritorna un albero in-ordine con gli
stessi elementi di quello in input ma privo dell'elemento cancellato
28
Rappresentazione di Alberi (n-ari)
• E' BENE CHE OGNI NODO SIA RAPPRESENTATO DA UN
DESCRITTORE DI STRUTTURA FISSA,
INDIPENDENTEMENTE DAL NUMERO DEI SUOI FIGLI.
• IN UN ALBERO N-ARIO OGNI NODO RIFERISCE:
– UN SOLO FIGLIO, il primogenito (un solo elemento di
CHILD)
– UN SOLO FRATELLO, il successivo
• per realizzare il doppio link avanti-indietro occorre:
– MANTENERE IN OGNI NODO L'INVERSO DELLA
RELAZIONE CHILD
– MANTENERE LA LISTA DEI FRATELLI COME UNA LISTA
DOPPIAMENTE LINKATA
• IN QUESTO MODO E' POSSIBILE:
– MUOVERSI LUNGO L'ALBERO IN ENTRAMBE LE
DIREZIONI (alto/basso)
– INSERIRE E CANCELLARE UN NODO (foglia) IN UN
ALBERO IN TEMPO COSTANTE
29
Rappresentazione di Alberi (n-ari): esempio
1
2
6
12
3
7
8
13
14
4
5
9
10
11
figlio (relazione logica, rappresentata in modo indiretto)
figlio primogenito
fratello
30
Rappresentazione di Alberi (n-ari): esempio
1
2
6
12
3
7
8
13
14
4
5
9
10
11
figlio-1 (parent)
figlio primogenito
fratello
31
Rappresentazione di Alberi (n-ari): esempio
typedef struct node *tree;
struct node {
char
*name;
tree
firstChild;
tree
parent;
tree
lBrother;
tree
rBrother;
};
•
la struttura dati e' molto semplificata rispetto al caso generale di
un grafo
•
esiste un punto di ingresso primario nell'albero: la radice
•
ogni nodo ha un solo lato entrante
•
la descrizione dei lati puo' essere collassata dentro quella
dei nodi:
ogni nodo coda tiene la lista dei nodi testa dei lati che
escono da lui (la relazione child)
32
Rappresentazione di Alberi Binari
•
SI PUO' MIGLIORARE ANCORA LA RAPPRESENTAZIONE
RISPETTO A QUELLA DEGLI ALBERI N-ARI, PERCHE' IN
QUESTO CASO SI PUO' DARE UN LIMITE A PRIORI AL
NUMERO DI FIGLI,
•
CIO' E' ANCHE NECESSARIO PERCHE' I FIGLI DEVONO
ESSERE DISTINTI IN SINISTRI E DESTRI
•
E SE C'E' UN SOLO FIGLIO BISOGNA DISTINGUERE SE
QUESTO E' UN FIGLIO SINISTRO O DESTRO
typedef struct binNode *binTree;
struct binNode {
char
*name;
binTree
leftChild;
binTree
rightChild;
binTree
parent;
};
33
Rappresentazione di Alberi Binari
•
MA IN REALTA', PER ALBERI COMPLETI (O QUASI) SI PUO'
FARE ANCHE DI MEGLIO, ELIMINANDO OGNI
RIFERIMENTO ESPLICITO:
•
L'ALBERO E' RAPPRESENTATO IN UN ARRAY LINEARE
node binTree[n]
•
I FIGLI DEL NODO DI INDICE i SI TROVANO NELLE
POSIZIONI: 2*i+1 E 2*i+2
•
IL FIGLIO DI SINISTRA IN POSIZIONE 2*i+1, E QUELLO DI
DESTRA IN POSIZIONE 2*i+2
•
IL PADRE DEL NODO DI INDICE i SI TROVA IN POSIZIONE:
(i-1)/2 (divisione intera!)
•
LA RADICE E' NELLA POSIZIONE 0
34
Rappresentazione di Alberi Binari
•
UN ALBERO BINARIO E' COMPLETO SE ESISTE UN
NUMERO k PER CUI
– TUTTI I NODI DI PROFONDITA' <k HANNO ENTRAMBI I
FIGLI
– I NODI DI PROFONDITA' k SONO FOGLIE
•
UN ALBERO BINARIO COMPLETO DI PROFONDITA' k HA
2k+1 - 1 NODI E, DI QUESTI, 2k SONO FOGLIE
(la dimostrazione per induzione matematica e` facile, specie
partendo dal secondo punto, ed e' lasciata per esercizio)
•
LA RAPPRESENTAZIONE IN ARRAY LINEARE E' BUONA
PURCHE' L'ALBERO SIA ALMENO QUASI PIENO:
– ESISTONO FOGLIE ANCHE DI PROFONDITA' k-1
– LE FOGLIE DI PROFONDITA' k-1 SONO I NODI PIU' A
DESTRA DI QUELLA PROFONDITA'
35
ALBERI BINARI: DIMENSIONE E PROFONDITA'
•
ALTEZZA E PROFONDITA' SONO LEGATE AL NUMERO DI
ELEMENTI DELL'ALBERO DALLA RELAZIONE "logaritmo"
•
CIO' SIGNIFICA CHE POSSIAMO RAGGIUNGERE UNA FOGLIA
IN UN TEMPO LOGARITMICO RISPETTO AL NUMERO DI NODI
DELL'ALBERO
•
E' PER QUESTO CHE GLI ALBERI SONO COSI' EFFICIENTI
PER RAPPRESENTARE INSIEMI E/O SEQUENZE DI OGGETTI
QUANDO LE OPERAZIONI CHE VOGLIAMO COMPIERE SU
TALI INSIEMI E/O SEQUENZE SONO OPERAZIONI SUL
SINGOLO ELEMENTO:
•
INSERZIONE
•
CANCELLAZIONE
•
RICERCA
•
RICERCA DEL MINIMO O DEL MASSIMO
36
VISITA DI UN ALBERO
•
LA VISITA DI UN ALBERO E' DEFINITA RICORSIVAMENTE
PER LA RADICE ED I SUOI SOTTOALBERI.
•
PUO' AVVENIRE SECONDO DIVERSE DISCIPLINE
•
PRE-ORDINE:
VISITO PRIMA LA RADICE POI, SEQUENZIALMENTE (e
ricorsivamente), CIASCUNO DEI SUOI SOTTOALBERI
•
POST-ORDINE:
VISITO PRIMA, SEQUENZIALMENTE (e ricorsivamente),
CIASCUN SOTTOALBERO DELLA RADICE, E POI LA
RADICE STESSA DELL'ALBERO
•
IN-ORDINE (SOLO PER ALBERI BINARI):
VISITO PRIMA IL SOTTOALBERO SINISTRO DELLA
RADICE, POI LA RADICE, POI IL SUO SOTTOALBERO
DESTRO
37
VISITA DI UN ALBERO
•
DURANTE LA VISITA POSSO NUMERARE I NODI
DELL'ALBERO:
1
8
2
3
6
5
7
4
pre-ordine
4
2
8
5
7
3
6
1
post-ordine
3
1
5
8
4
6
2
7
in-ordine
38
PROPRIETA' DELLE NUMERAZIONI
•
PRE-ORDINE:
•
TUTTI I DISCENDENTI HANNO NUMERO MAGGIORE
DEI LORO ANTENATI
•
SE IL NODO n HA d DISCENDENTI, QUESTI SONO
NUMERATI DA n+1 A n+d
•
SE SI CONOSCE IL NUMERO DI UN NODO ED IL
NUMERO DEI SUOI DISCENDENTI SI PUO' DECIDERE
IN TEMPO COSTANTE SE UN NODO QUALSIASI E'
DISCENDENTE DI QUEL NODO
(cioe' SE IL SUO NUMERO E' COMPRESO TRA n+1 E
n+d)
•
POST-ORDINE:
•
VALGONO PROPRIETA' DUALI
39
PROPRIETA' DELLE NUMERAZIONI
•
IN-ORDINE:
•
OGNI DISCENDENTE SINISTRO HA NUMERO MINORE
DEL NODO,
•
OGNI DISCENDENTE DESTRO HA NUMERO
MAGGIORE DEL NODO.
•
Un nodo del sottoalbero sinistro del nodo N ha numero
compreso tra N-1 e N-#(sottoalbeto sinistro).
•
Un nodo del sottoalbero destro del nodo N ha numero
compreso tra N+1 e N+#(sottoalbeto destro).
40
PROPRIETA' DELLE NUMERAZIONI
• IN-ORDINE:
E' UNA MANIERA TIPICA DI MEMORIZZARE STRINGHE
 INSERENDOLE NELL'ALBERO IN MODO CHE RISPETTINO
L'IN-ORDINE
 SE POI VISITIAMO IN IN-ORDINE L'ALBERO RITROVIAMO
LE STRINGHE IN ESSO REGISTRATE IN ORDINE
ALFABETICO
 SE VOGLIO CERCARE IL NODO i NELL'ALBERO (NON SO
SE C'E') GUARDO LA RADICE r:
1. SE r=i HO TROVATO
2. SE r>i DEVO CERCARE i NEL SOTTOALBERO
SINISTRO DI r, SE QUESTO NON E' VUOTO.
COMUNQUE, SE NON E' LI' NON E' NELL'ALBERO
3. SE r<i DEVO CERCARE i NEL SOTTOALBERO
DESTRO DI r, SE QUESTO NON E' VUOTO.
COMUNQUE, SE NON E' LI' NON E' NELL'ALBERO 41
PROCEDURE DI VISITA: pre-order
typedef struct binNode *binTree;
struct binNode {
int
givenNo;
int
size;
binTree
leftChild;
binTree
rightChild;
binTree
parent;
};
int preOrder (binTree root, int number) {
// root : radice del sottoalbero non vuoto che
// si vuole visitare
assert(root!=NULL);
// preorder numera in preordine i nodi dell'
// albero root (nel campo givenNo) a
// partire dal numero number, e ritorna la
// dimensione dell'albero
42
// continua alla prossima pagina
PROCEDURE DI VISITA: pre-order
root->givenNo = number;
int kids =
(root->leftChild != NULL) ?
preOrder(root->leftChild,
number+1)
: 0;
kids +=
(root->rightChild != NULL) ?
preOrder(root->rightChild,
number+1+kids)
: 0;
return (root->size = kids + 1);
}
43
PROCEDURE DI VISITA: post-order
int postOrder (binTree root, int number) {
assert(root!=NULL);
int kids =
(root->leftChild != NULL) ?
postOrder(root->leftChild, number)
: 0;
kids +=
(root->rightChild != NULL) ?
postOrder(root->rightChild,
number+kids)
: 0;
root->givenNo = number + kids;
return (root->size = kids + 1);
}
44
PROCEDURE DI VISITA: in-order
int inOrder (binTree root, int number) {
assert(root!=NULL);
int kids =
(root->leftChild != NULL) ?
inOrder(root->leftChild, number)
: 0;
root->givenNo = number + kids;
kids +=
(root->rightChild != NULL) ?
inOrder(root->rightChild,
number+kids+1)
: 0;
return (root->size = kids + 1);
}
45
RICORSIONE
•
QUANTO COSTA?
•
QUANTO COSTA UNA CHIAMATA DI PROCEDURA?
• DI PER SE STESSA L'ISTRUZIONE CALL HA COSTO COSTANTE
• POI DIPENDE DAI PARAMETRI CHE SONO PASSATI:
• SE UNO PASSA OGGETTI DI DIMENSIONE COSTANTE CON
LA DIMENSIONE DEL PROBLEMA (e.g. INDIRIZZI DI ARRAY)
LA CHIAMATA E' IN TEMPO COSTANTE,
• MA SE PASSA OGGETTI DI DIMENSIONE CORRELATA CON
LA DIMENSIONE DEL PROBLEMA LA CHIAMATA STESSA E'
DI COMPLESSITA' LINEARE CON LA DIMENSIONE DEL
PROBLEMA
• IL COSTO DELLA CHIAMATA E' ADDEBITATO AL CHIAMANTE
• POI C'E' IL COSTO DI ESEGUIRE LA PROCEDURA CHIAMATA
• SE QUESTA NON E' RICORSIVA LA COMPLESSITA' SI CALCOLA
FACILMENTE,
 MA SE E' RICORSIVA?
46
COMPLESSITA' DELLA VISITA DI UN ALBERO
•
VISITO UN ALBERO BINARIO DI ALTEZZA n.
IL COSTO T(n) DI QUESTA VISITA E'
 T(n) = 2 * T(n-1) + C
CIOE' 2 VOLTE IL COSTO DI VISITARE UN (SOTTO-)
ALBERO DI ALTEZZA (n-1) PIU' IL COSTO (COSTANTE)
DELLA VISITA DELLA RADICE
•
SE L'ALBERO HA ALTEZZA 0 DEVO VISITARE SOLO LA
RADICE E
 T(0) = C
•
ALLORA IL COSTO DELLA VISITA E' ESPRIMIBILE CON
UNA RELAZIONE RICORSIVA:
{
T(n) = 2*T(n-1) + C
T(0) = C
47
COMPLESSITA' DELLA VISITA DI UN ALBERO
•
COME FACCIO A RISOLVERE LA RELAZIONE RICORSIVA
DANDO LA FORMA CHIUSA DI T(n)?
•
NEL NOSTRO CASO NOI SAPPIAMO CHE
•
OGNI NODO E' VISITATO UNA SOLA VOLTA, E CHE
•
UN ALBERO DI ALTEZZA n HA 2n+1-1 NODI (in realta'
O(2n+1-1) nodi),
ERGO SARA'
 T(n) = (2n+1 - 1) * C
•
INFATTI, PER INDUZIONE MATEMATICA:
•
T(0) = C
•
T(n+1) = 2 * ((2n+1 - 1) * C) + C
= 2n+2 * C - 2 * C + C
= (2(n+1)+1 - 1) * C
48
CORRETTEZZA DELLE VISITE
•
CONSIDERIAMO AD ESEMPIO PREORDER
•
PER INDUZIONE SULL'ALTEZZA DELL'ALBERO
•
HP INDUTTIVA: la radice e` numerata correttamente secondo il "numero"
dato e la funzione ritorna la dimensione del sotto-albero
•
SE L'ALTEZZA DELL'ALBERO E' 0 ALLORA LA RADICE E' NUMERATA
CON IL VALORE number E LA FUNZIONE RITORNA 1 PERCHE' LA
RADICE E' UNA FOGLIA (ALTRIMENTI NON SAREBBE AD ALTEZZA 0)
•
SE L'ALTEZZA DELL'ALBERO E' (H+1) E SI SUPPONE CHE LA
PROCEDURA OPERI CORRETTAMENTE PER TUTTI GLI ALBERI DI
ALTEZZA H ALLORA;
•
LA RADICE E' NUMERATA CORRETTAMENTE A number
•
SE C'E' IL SOTTOALBERO SINISTRO E' NUMERATO
CORRETTAMENTE DA number+1 E kids E' LA SUA DIMENSIONE
(PER INDUZIONE MATEMATICA DATO CHE IL SOTTOALBERO E'
DI ALTEZZA H, E number E' STATO INCREMENTATO DI 1 NELLA
CHIAMATA RICORSIVA)
•
ANALOGAMENTE PER IL SOTTOALBERO DESTRO
•
E QUINDI ANCHE PER L'ALBERO DI ALTEZZA (H+1)
49
ESERCIZIO
•
Scrivere le procedure per la visita in pre- ed in post-ordine di un
albero n-ario descritto tramite la seguente struttura dati:
typedef struct node *tree;
struct node {
char
*name;
int
givenNo;
int
size;
tree
firstChild;
tree
nextBrother;
};
•
Si possono implementare 2 versioni delle procedure indicate:
•
•
•
la prima versione si basa solo sulla ricorsione, anche per la scansione
della lista dei fratelli;
la seconda si basa sulla ricorsione per la visita di ciascun (sotto-)
albero, ma sull'iterazione per la scansione della lista dei fratelli
In ogni caso, ogni funzione ritorna il numero complessivo di nodi del
50
o dei sotto-alberi che ha visitato
ESERCIZIO: pre-order - 1
int preOrder_1 (tree root, int number) {
assert(root != NULL);
root->givenNo = number;
root->size =
1 +
(root->firstChild != NULL ?
preOrder_1(root->firstChild, number+1)
: 0);
return(root->size +
(root->nextBrother != NULL ?
preOrder_1(root->nextBrother,
number + root->size)
: 0);
}
51
ESERCIZIO: pre-order - 2
int preOrder_2 (tree root, int number) {
// visita un nodo e tutto e solo il suo
// sottoalbero
assert(root != NULL);
root->givenNo = number;
root->size =
1 +
(root->firstChild != NULL ?
preOrderF(root->firstChild, number+1)
: 0);
return(root->size);
}
52
ESERCIZIO: pre-order - 2
int preOrderF(tree root, int number) {
// visita un nodo che e' figlio primogenito,
// tutto il suo sottoalbero, e tutti
// i sottoalberi suoi fratelli
int nodes = preOrder_2(root, number);
tree t = root->nextBrother;
while (t != NULL) {
nodes += preOrder_2(t, number + nodes);
t = t->nextBrother;
}
return(nodes);
}
53
ESERCIZIO: post-order - 1
int postOrder_1 (tree root, int number) {
assert(root != NULL);
root->size =
1 +
(root->firstChild != NULL ?
postOrder_1(root->firstChild, number)
: 0);
root->givenNo = number + root->size - 1;
return(root->size +
(root->nextBrother != NULL ?
postOrder_1(root->nextBrother,
number + root->size)
: 0);
}
54
ESERCIZIO : post-order - 2
int postOrder_2 (tree root, int number) {
// visita un nodo e tutto e solo il suo
// sottoalbero
assert(root != NULL);
root->size =
1 +
(root->firstChild != NULL ?
postOrderF(root->firstChild, number)
: 0);
root->givenNo = number + root->size - 1;
return(root->size);
}
55
ESERCIZIO : post-order - 2
int postOrderF(tree root, int number) {
// visita un nodo che e' figlio primogenito,
// tutto il suo sottoalbero, e tutti
// i sottoalberi suoi fratelli
int nodes = postOrder_2(root, number);
tree t = root->nextBrother;
while (t != NULL) {
nodes += postOrder_2(t, number + nodes);
t = t->nextBrother;
}
return(nodes);
}
56
VISITE ITERATIVE
•
visita in preordine dell'albero
 iterativa
•
come ricordarsi le informazioni che nel caso della ricorsione
sono memorizzate nello stack dei record di attivazione?
•
•
quale informazione occorre ricordarsi?
•
•
su uno stack!
il sotto-albero che rimane da scandire al termine della
scansione del sottoalbero che si inizia a scandire in
questo momento
ci si basa sull'utilizzo del dato astratto stack
57
Dato astratto Stack

operazioni
 StackInit
  stack
 inizializza lo stack a stack vuoto (StackEmpty()=TRUE)
 precondizioni: nessuna
 StackEmpty
 stack  BOOLEAN
 ritorna TRUE se e solo se lo stack e' vuoto
 precondizioni: nessuna
 StackPush
 stack  elemento  stack
 dato l'elemento E lo inserisce sullo stack
 precondizioni: nessuna
 StackPop
 stack  elemento
 estrae l'elemento sul top dello stack e lo ritorna al cliente
58
 precondizioni: !StackEmpty()
Dato astratto Stack

assiomi:
– ├ StackInit(); StackEmpty() == TRUE;
– ├ StackPush(e); StackEmpty() == FALSE;
– ├ StackPush(e); e == StackPop();

interfaccia programmatica (API)
–
–
–
–

void StackInit(void);
Boolean StackEmpty(void);
void StackPush(elemento e);
elemento StackPop(void);
per la nostra applicazione elemento deve coincidere con il tipo
Tree

ogni operazione ha un parametro implicito: lo stack stesso
 stackInit() e' definita come: stack, e non come: stackstack,
perche' e' di norma utilizzata per inizializzare uno stack. Prima di essere
inizializzato uno stack non e' uno stack ma solo un ammasso di byte 59
VISITE ITERATIVE: pre-ordine
void preorder (Tree t)
{
while (!(emptyt(t) && StackEmpty())) {
if (!(emptyt(t)) {
writeVal(root(t));
StackPush(right(t));
t = left(t);
} else {
t = StackPop();
}
}
}
•
•
come si dimostra la correttezza?
e se si dovesse anche numerare i nodi dell'albero e registrare in
ogni nodo la dimensione del sottoalbero di cui e' la radice?
60
VISITE ITERATIVE: esercizio
•
Scrivere le procedure iterative per la visita
•
in post-ordine
•
in in-ordine
ad un albero binario.
•
Queste procedure devono basarsi sull'utilizzo del dato astratto
stack, ma il tipo elemento dovra' essere definito
opportunamente a seconda dei casi.
•
Vedi anche le dispense di Universita' di Bologna (Cesena)
61
Ricorsione vs. Iterazione
•
Quando e' importante sfruttare la ricorsione?
•
Quando il chiamante, al momento della chiamata ricorsiva, deve
tenere memorizzate molte informazioni
• variabili locali
• stato di avanzamento della propria esecuzione (Program
Counter)
•
Confrontare ad esempio:
• scansione di una lista
• scansione di un albero binario ordinato per identificarne
l'elemento minimo
• visita di un albero binaro in pre-ordine
• visita di un albero binaro in post-ordine
•
La quantita' di informazione da tenere memorizzata e' via via
crescente (dopo i primi due casi) e quindi l'utilizzo della ricorsione
sempre piu' conveniente
62