![Page 1: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/1.jpg)
Modello dati ALBEROModello dati ALBERO
Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES
EDGE: EDGE: linea che unisce due nodi distintilinea che unisce due nodi distinti
Radice (root): Radice (root): in una albero esiste un nodo in una albero esiste un nodo distinto chiamato radice (disegnato in cima)distinto chiamato radice (disegnato in cima)
Es. Albero con sette nodi nEs. Albero con sette nodi n11, n, n22, n, n33, n, n44, n, n55, n, n66, n, n77
la radice è nla radice è n11
n1
n2
n3
n4 n5
n6 n7
![Page 2: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/2.jpg)
Modello dati ALBEROModello dati ALBERO
n1
n2
n3
n4 n5
n6 n7
Padre/figlio: ogni nodo c (tranne la radice) è connesso mediante una linea ad un nodo p, chiamato il padre di c; c è detto figlio di p.
Es. n1 padre di n2, n4, n5 / n2, n4, n5 figli di n1 n2 “ n3 / n3 figlio di n2
n5 n6, n7 / n6, n7 figli di n5
![Page 3: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/3.jpg)
Modello dati ALBEROModello dati ALBERO
n1
n2
n3
n4 n5
n6 n7
Padre/figlio: ogni nodo c (tranne la radice) è connesso mediante una linea ad un nodo p, chiamato il padre di c; c è detto figlio di p.
Es. n1 padre di n2, n4, n5 / n2, n4, n5 figli di n1 n2 “ n3 / n3 figlio di n2
n5 n6, n7 / n6, n7 figli di n5
Albero è connesso: per ogni nodo n (tranne la radice) se ci spostiamo da n al padre di n,
poi dal padre di n al padre del padre di n, …,arriviamo alla radice.
Es. n3 padre di n3=n2 padre di n2=n1=radice
![Page 4: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/4.jpg)
Definizione ricorsiva di ALBERODefinizione ricorsiva di ALBERO
c1
Base: un singolo nodo n è un albero (con radice n)Passo:Siano T1,…,Tk, (per qualche k>0) alberi con
radici c1,c2,…,ck,rispettivamente, tali che ogni nodo compaia in uno solo degli alberi. Sia r un nuovo nodo (non in T1,…,Tk). Costruiamo un nuovo albero T come segue
1. La radice di T è r2. Aggiungi un edge da r ad ognuna dei nodi c1,
…,ck (che diventano figli di r in T) r
T1
…
ck
Tk
c1
T1
… ck
Tk
T=
![Page 5: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/5.jpg)
Definizione ricorsiva di ALBERODefinizione ricorsiva di ALBERO
Base: un singolo nodo n è un albero (con radice n)Passo:Siano T1,…,Tk, (per qualche k>0) alberi con radici
c1,c2,…,ck,rispettivamente, tali che ogni nodo compaia in un solo albero. Sia r un nuovo nodo. Costruiamo il nuovo albero T
1. La radice di T è r2. Aggiungi un edge da r ad ognuna dei nodi c1,…,ck (figli di
r in T) Es. n3 albero n2
n3
è albero
![Page 6: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/6.jpg)
Definizione ricorsiva di ALBERODefinizione ricorsiva di ALBERO
Base: un singolo nodo n è un albero (con radice n)Passo:Siano T1,…,Tk, (per qualche k>0) alberi con radici
c1,c2,…,ck,rispettivamente, tali che ogni nodo compaia in un solo albero. Sia r un nuovo nodo. Costruiamo il nuovo albero T
1. La radice di T è r2. Aggiungi un edge da r ad ognuna dei nodi c1,…,ck (figli di
r in T) Es. n3
n6 n7
albero n2
n3
alberi n5
n6 n7
è albero
è albero
![Page 7: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/7.jpg)
Definizione ricorsiva di ALBERODefinizione ricorsiva di ALBERO
n1
n2
n3
n4 n5
n6 n7
Base: un singolo nodo n è un albero (con radice n)Passo:Siano T1,…,Tk, (per qualche k>0) alberi con radici
c1,c2,…,ck,rispettivamente, tali che ogni nodo compaia in un solo albero. Sia r un nuovo nodo. Costruiamo il nuovo albero T
1. La radice di T è r2. Aggiungi un edge da r ad ognuna dei nodi c1,…,ck (figli di
r in T) Es. n3
n6 n7
albero n2
n3
alberi n5
n6 n7
è albero
è albero
n2
n3
n4 n5
n6 n7
alberi è albero
![Page 8: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/8.jpg)
Definizioni su ALBERI èDefinizioni su ALBERI è
Dato T con radice rm1,…mk: è un cammino (di lunghezza k-1) in T se m1 è padre di m2, m2 è padre di m3,…, mk-1 padre di
mk.
un solo nodo è un cammino di lunghezza 0 (k=1).
n1
n2
n3
n4 n5
n6 n7
![Page 9: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/9.jpg)
Definizioni su ALBERI èDefinizioni su ALBERI è
Dato T con radice rm1,…mk: è un cammino (di lunghezza k-1) in T se m1 è padre di m2, m2 è padre di m3,…, mk-1 padre di
mk.
un solo nodo è un cammino di lunghezza 0 (k=1).
Predecessore: m è predecessore di m’ se esiste un cammino da m a m’ in T
Discendente: m’ è discendente di m se m è predecessore di m’.
Fratelli: m e m’ so dicono fratelli se hanno lo stesso padre.
n1
n2
n3
n4 n5
n6 n7
![Page 10: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/10.jpg)
Definizioni su ALBERI èDefinizioni su ALBERI è
Sottoalbero con radice n: albero formato dal nodo n con tutti i suoi discendenti
n1
n2
n3
n4 n5
n6 n7
![Page 11: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/11.jpg)
Definizioni su ALBERI èDefinizioni su ALBERI è
Sottoalbero con radice n: albero formato dal nodo n con tutti i suoi discendenti
Foglia: nodo che non ha figliNodo interno: nodo che ha almeno un figlio
n1
n2
n3
n4 n5
n6 n7
![Page 12: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/12.jpg)
Definizioni su ALBERI èDefinizioni su ALBERI è
Altezza di un albero T: lunghezza del più lungo cammino dalla radice di T ad una foglia di T.
Livello del nodo n: lunghezza del cammino dalla radice ad n.
Fratelli: m e m’ so dicono fratelli se hanno lo stesso
padre.
n1
n2
n3
n4 n5
n6 n7
![Page 13: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/13.jpg)
Definizioni su ALBERI èDefinizioni su ALBERI è
Alberi ordinati: possiamo assegnare un ordine da sinistra a destra ai figli di un nodo, inoltre
se m ed n sono fratelli ed m è a destra di n allora ogni discendente di m è a destra di ogni
discendente di n Quindi per ogni coppia di nodi vale la relazione
“essere a destra”.
n1
n2
n3
n4 n5
n6 n7
![Page 14: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/14.jpg)
Struttura dati per ALBERIStruttura dati per ALBERI
Dipende dalle operazioni che si devono effettuare
Generalmente nodi = struct elemento puntatori
Array di puntatori
info p0 … pb-1
Array di puntatori ai figli del nodo
b= branching factor = max numero figli per nodo
Se nodo ha < b figli allora alcuni puntatori sono NULL
Typedef struct NODE *pNODE struct NODE{ int info “array di b puntatori pNODE’’}
![Page 15: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/15.jpg)
Struttura dati per ALBERIStruttura dati per ALBERI
TRIE: Serve per memorizzare stringhe di caratteri. 1. Ogni nodo ha associata una lettera2. La stringa rappresentata dal nodo è la sequenza di
lettere sul cammino dalla radice al nodo3. Un simbolo (+/-) dice se la stringa rappresentata dal
nodo fa parte di quelle da memorizzare.
Es. Vogliamo memorizzare {he, hers, his, she} (array di 26 elementi)
![Page 16: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/16.jpg)
Struttura dati per ALBERIStruttura dati per ALBERI
TRIE: Serve per memorizzare stringhe di caratteri. 1. Ogni nodo ha associata una lettera2. La stringa rappresentata dal nodo è la sequenza di
lettere sul cammino dalla radice al nodo3. Un simbolo (+/-) dice se la stringa rappresentata dal
nodo fa parte di quelle da memorizzare.
Es. Vogliamo memorizzare {he, hers, his, she} (array di 26 elementi)
-
![Page 17: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/17.jpg)
Struttura dati per ALBERIStruttura dati per ALBERI
TRIE: Serve per memorizzare stringhe di caratteri. 1. Ogni nodo ha associata una lettera2. La stringa rapperesentata dal nodo è la sequenza di
lettere sul cammino dalla radice al nodo3. Un simbolo (+/-) dice se la stringa rappresentata dal
nodo fa parte di quelle da memorizzare.
Es. Vogliamo memorizzare {he, hers, his, she} (array di 26 elementi)
-
h -
-
![Page 18: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/18.jpg)
Struttura dati per ALBERIStruttura dati per ALBERI
TRIE: Serve per memorizzare stringhe di caratteri. 1. Ogni nodo ha associata una lettera2. La stringa rapperesentata dal nodo è la sequenza di
lettere sul cammino dalla radice al nodo3. Un simbolo (+/-) dice se la stringa rappresentata dal
nodo fa parte di quelle da memorizzare.
Es. Vogliamo memorizzare {he, hers, his, she} (array di 26 elementi)
-
h
e +
-
-
![Page 19: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/19.jpg)
Struttura dati per ALBERIStruttura dati per ALBERI
TRIE: Serve per memorizzare stringhe di caratteri. 1. Ogni nodo ha associata una lettera2. La stringa rapperesentata dal nodo è la sequenza di
lettere sul cammino dalla radice al nodo3. Un simbolo (+/-) dice se la stringa rappresentata dal
nodo fa parte di quelle da memorizzare.
Es. Vogliamo memorizzare {he, hers, his, she} (array di 26 elementi)
-
h
e
r
s +
+
-
-
-
![Page 20: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/20.jpg)
Struttura dati per ALBERIStruttura dati per ALBERI
TRIE: Serve per memorizzare stringhe di caratteri. 1. Ogni nodo ha associata una lettera2. La stringa rapperesentata dal nodo è la sequenza di
lettere sul cammino dalla radice al nodo3. Un simbolo (+/-) dice se la stringa rappresentata dal
nodo fa parte di quelle da memorizzare.
Es. Vogliamo memorizzare {he, hers, his, she} (array di 26 elementi)
-
h
e
r
s
i
s
+
+
-
-
-
-
+
![Page 21: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/21.jpg)
Struttura dati per ALBERIStruttura dati per ALBERI
TRIE: Serve per memorizzare stringhe di caratteri. 1. Ogni nodo ha associata una lettera2. La stringa rapperesentata dal nodo è la sequenza di
lettere sul cammino dalla radice al nodo3. Un simbolo (+/-) dice se la stringa rappresentata dal
nodo fa parte di quelle da memorizzare.
Es. Vogliamo memorizzare {he, hers, his, she} (array di 26 elementi)
-
h s
he
r
s
i
es
+
+
-
-
-
-
--
++
![Page 22: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/22.jpg)
Struttura dati per ALBERIStruttura dati per ALBERI
h s
he
r
s
i
es
+
+
-
-
-
-
--
++
-a b … h … s … z
h - s -
e +
e i h
i - h -
r s e
r -s
s +
s + e +
![Page 23: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/23.jpg)
ALBERI Sinistra-DestraALBERI Sinistra-DestraPer evitare spreco di memoria: lista a puntatori per rappresentare i figli di un nodo
Typedef struct NODE *pNODE struct NODE{ infotype info; pNODE leftchild, rightsibling}
NODE infotype leftmostchild rightsibling
![Page 24: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/24.jpg)
ALBERI Sinistra-DestraALBERI Sinistra-Destra
a
b
e
c d
f g
NODE infotype leftmostchild rightsibling
a /
b c / d /
e / / f / g / /
![Page 25: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/25.jpg)
Struttura dati per ALBERIStruttura dati per ALBERI
h s
he
r
s
i
es
+
+
-
-
-
-
--
++
- /
h - s - /
e + i - h - /
r - /
s + / /
s + / / e + / /
![Page 26: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/26.jpg)
Induzione StrutturaleInduzione Strutturale
c1
Possiamo specializzare induzione per alberi in base alla definizione ricorsiva:Base un singolo nodo n è un albero (con radice n)Passo Siano T1,…,Tk, (per qualche k>0) alberi con
radici c1,c2,…,ck, tali che ogni nodo compaia in un solo albero. Sia r un nuovo nodo. Costruiamo un nuovo albero T:
1. La radice di T è r2. Aggiungi un edge da r ad ognuna dei nodi c1,
…,ck (che diventano figli di r in T) r
T1
…
ck
Tk
c1
T1
… ck
Tk
T=
![Page 27: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/27.jpg)
Induzione StrutturaleInduzione Strutturale
Vogliamo provare che l’affermazione S(T) è vera per ogni albero T
Base: S(T) è vera per ogni albero con un singolo nodo
r
![Page 28: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/28.jpg)
Induzione StrutturaleInduzione Strutturale
Vogliamo provare che l’affermazione S(T) è vera per ogni albero T
Base: S(T) è vera per ogni albero con un singolo nodo
Passo: Sia T con sottoalberi T1…,Tk. Mostriamo che se
S(T1),…,S(Tk) sono tutte vere allora anche S(T) è vera c1
r
T1
…
ck
Tk
c1
T1
… ck
Tk
T=
Ipotesi Induttiva su ogni sottoalbero
![Page 29: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/29.jpg)
Induzione StrutturaleInduzione StrutturaleEs. Definiamo V(T)= numero di nodi di T deg(x)= numero di figli di x Vogliamo provare l’affermazione S(T):
Tin nodo
deg(x)1)(x
TV
![Page 30: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/30.jpg)
Induzione StrutturaleInduzione StrutturaleEs. Definiamo V(T)=numero di nodi di T e grado del nodo x =deg(x)= numero di figli di x Vogliamo provare l’affermazione S(T):
BASE: Se T ha 1 nodo x, allora x non ha figli e deg(x)=0
V(T)=1=1+deg(x)
Tin nodo
deg(x)1)(x
TV
![Page 31: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/31.jpg)
Induzione StrutturaleInduzione Strutturale
S(T):
PASSO: Indichiamo con k il numero di figli della radice e con sottoalberi T1,…,Tk. Siano S(T1),
…,S(Tk) vere, cioè
r
c1
T1
… ck
Tk
T=
Tin nodo
deg(x)1)(x
TV
kiTVx
i ,...,1 ,deg(x)1)(iTin nodo
![Page 32: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/32.jpg)
Induzione StrutturaleInduzione Strutturale
S(T):
PASSO: Indichiamo con k il numero di figli della radice e con sottoalberi T1,…,Tk. Siano S(T1),…,S(Tk) vere, cioè
Proviamo S(T)
r
c1
T1
… ck
Tk
T=
Tin nodo
deg(x)1)(x
TV
kiTVx
i ,...,1 ,deg(x)1)(iTin nodo
Tx
rx
Txx
k
i
x
k
ii
k
i
x
xrk
TVTV
in nodo
in nodo Tin 1
Tin nodo 11
)deg(1
)deg()deg(1)deg(x)(1
)deg(x)1(1)(1)(
i
i
![Page 33: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/33.jpg)
Induzione StrutturaleInduzione Strutturale Induzione strutturale induzione completa specializzata per alberi
S(T): proprieta P è vera S(n): proprietà P è vera per
per T ogni albero con n nodi
Base. Albero con 1 nodo affermazione vera n=1
Passo. I.I. per ogni sottoalbero I.I. per ogni m<n
proviamo per T proviamo per n
![Page 34: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/34.jpg)
Induzione StrutturaleInduzione StrutturaleEs. Consideriamo alberi con rappresentazione sinistra-destra Vogliamo provare l’affermazione S(T): il numero di puntatori NULL in T è V(T)
+1
BASE: Se T ha 1 nodo x, allora x non ha figli ne fratelli
V(T)=1, #NULL=2=V(T)+1
![Page 35: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/35.jpg)
Induzione StrutturaleInduzione Strutturale
S(T): #NULL in T è V(T)+1
PASSO: Indichiamo con k il numero di figli della radice e con sottoalberi T1,…,Tk. Siano S(T1),…,S(Tk) vere, cioè
#NULL in Ti è V(Ti)+1, per ogni i=1,…,k.
r
c1
T1
… ck
Tk
T=
![Page 36: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/36.jpg)
Induzione StrutturaleInduzione Strutturale
S(T): #NULL in T è V(T)+1
PASSO: Indichiamo con k il numero di figli della radice e con sottoalberi T1,…,Tk. Siano S(T1),…,S(Tk) vere, cioè #NULL in Ti è V(Ti)+1, per ogni i=1,…,k.
r
c1
T1
… ck
Tk
T=
#NULL in T ==1 +( #NULL in T1 -1)+…+( #NULL in Tk-1-1)+( #NULL in Tk)=1+(V(T1)+1-1)) +…+ (V(Tk-1)+1-1)+V(Tk)+1
=1 + V(T1)+…+V(Tk-1)+V(Tk)+1=V(T) +1
I puntatori NULL in T sono: rightsibling di r, e quelli di ogni sottoalbero, tranne il rightsibling di c1,…,ck-
1
![Page 37: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/37.jpg)
Ricorsione su alberiRicorsione su alberi
Schema generale funzione
P(T)
P(T){ Azione A0
P(T1); Azione A1; P(T2); … Azione Ak-1; P(Tk); Azione Ak }
r
c1
T1
… ck
Tk
T=
![Page 38: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/38.jpg)
Visite di alberiVisite di alberi
Visita Preorder: si devono listare i nodi
dell’albero in modo tale che 1. ogni nodo precede nella lista tutti i suoi
discendenti2. la lista rispetta le relazione sinistra-destra
a
b
e
c d
f g
(a,b,e,c,d,f,e)
![Page 39: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/39.jpg)
Visite di alberiVisite di alberi
Visita Preorder: si devono listare i nodi dell’albero in modo tale che
1. ogni nodo precede nella lista tutti i suoi discendenti
2. la lista rispetta le relazione sinistra-destra
void preorder (pNode n){ pNODE c; /* figlio di n*/ printf(“%c\n”, n-
>nodelabel); c=n->leftmostchild; while (c != NULL) { preorder(c); c=c->rightsibling; } }
r
c1
T1
… ck
Tk
T=
typedef struct NODE *pNODE
struct NODE { char nodelabel; pNODE leftmostchild,
rigthsibling; }
![Page 40: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/40.jpg)
Visite di alberiVisite di alberi
void preorder (pNode n){ pNODE c; /* figlio di n*/ printf(“%c\n”, n->nodelabel); c=n->leftmostchild; while (c != NULL) { preorder(c); c=c->rightsibling;} }
CORRETTEZZA S(T): preorder(T) stampa la lista preorder di T
BASE. Se T ha un solo nodo, lo stampa e si ferma
PASSO. I.I.: preorder(Ti) da Li= lista preorder di Ti,
per ogni i=1,…,k.Quindi preorder(T) da L=(r, L1,…,Lk)=lista preorder di T
r
c1
T1
… ck
Tk
T=
![Page 41: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/41.jpg)
Visite di alberiVisite di alberi
R.T.: O(n), dove n è il numero di nodi di T
T(1)=O(1)
T(n)= O(1) + O(n1)+…+O(nk) = O(n)
dove n=1+n1+…+nk
Visite di alberiVisite di alberi
void preorder (pNode n){ pNODE c; /* figlio di n*/ printf(“%c\n”, n->nodelabel); c=n->leftmostchild; while (c != NULL) { preorder(c); c=c->rightsibling;} }
r
c1
T1
… ck
Tk
T=
![Page 42: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/42.jpg)
Visite di alberiVisite di alberi
Visita Postorder: si devono listare i nodi
dell’albero in modo tale che 1. ogni nodo segue nella lista tutti i suoi
discendenti2. la lista rispetta le relazione sinistra-destra
a
b
e
c d
f g
(e,b,c,f,g,d,a)
![Page 43: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/43.jpg)
Visite di alberiVisite di alberi
Visita Postorder: si devono listare
i nodi dell’albero in modo tale che
1. ogni nodo segue nella lista tutti i suoi discendenti
2. la lista rispetta le relazione sinistra-destra
void postorder (pNode n){ pNODE c; /* figlio di n*/ c=n->leftmostchild; while (c != NULL) {postorder(c); c=c>rightsibling; } printf(“%c\n”, n->nodelabel); }
r
c1
T1
… ck
Tk
T=
![Page 44: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/44.jpg)
Visite di alberiVisite di alberi
void postorder (pNode n){ pNODE c; /* figlio di n*/ c=n->leftmostchild; while (c != NULL) {postorder(c); c=c>rightsibling; } printf(“%c\n”, n->nodelabel); }
CORRETTEZZA S(T): postorder(T) stampa la lista postorder di T
BASE. Se T ha un solo nodo, lo stampa e si ferma
PASSO. I.I.: postorder(Ti) da Mi= lista postorder del sottoalbero, per ogni i=1,…,k.
postorder(T) da M=(M1,…,Mk,r)=lista postorder di T
R.T. O(n), dove n è il numero di nodi di T
r
c1
T1
… ck
Tk
T=
![Page 45: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/45.jpg)
Computo dell’ Altezza di un alberoComputo dell’ Altezza di un albero
Altezza di un nodo n= max distanza di n da una foglia sua discendente
Altezza albero= altezza radice
Altezza di una foglia = 0
Altezza di un nodo interno n = 1 + (altezza sottoalbero radicato in
n) = 1 + max altezza figli di n
a
b
e
c d
f g
Altezza di a = 1 + max { altezza di b, altezza di c, altezza di d } = 1 + max { 1,0,1} = 1 + 1 = 2
![Page 46: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/46.jpg)
Computo altezza Computo altezza
Vogliamo una funzione che per ogni nodo calcola l’altezza del nodo e la scrive nel campo heigth.
typedef struct NODE *pNODE
struct NODE { char nodelabel; int height; pNODE leftmostchild,
rigthsibling; }
Altezza di un nodo interno n = 1 + max altezza figli di n
IDEA: per ogni nodo calcola (ricorsivamente) l’altezza di ogni suo sottoalbero e calcola il max
![Page 47: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/47.jpg)
Visite di alberiVisite di alberi
r
c1
T1
… ck
Tk
T=
void computeHt (pNode n){ pNODE c; n->height=0; c=n->leftmostchild; while (c != NULL) {computeHt(c); if (c->height >= n->height) n->height= 1+c-
>height; c=c>rightsibling; }}
IDEA: per ogni nodo calcola (ricorsivamente) l’altezza di ogni suo sottoalbero e calcola il max
![Page 48: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/48.jpg)
Computo altezzaComputo altezzavoid computeHt (pNode n){ pNODE c; n->height=0; c=n->leftmostchild; while (c != NULL) {computeHt(c); if (c->height >= n->height) n->height= 1+c-
>height; c=c>rightsibling; }}CORRETTEZZA S(T): computeHt(n) calcola correttamente altezza
nodo n
BASE. Se T ha un solo nodo, pone height=0 e si ferma
![Page 49: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/49.jpg)
Computo altezzaComputo altezzavoid computeHt (pNode n){ pNODE c; n->height=0; c=n->leftmostchild; while (c != NULL) {computeHt(c); if (c->height >= n->height) n->height= 1+c-
>height; c=c>rightsibling; }}CORRETTEZZA S(T): computeHt(n) calcola correttamente altezza
nodo n
BASE. Se T ha un solo nodo, pone height=0 e si ferma
PASSO. I.I.: computeHt(ni) calcola correttamente l’altezza
del figlio ni di n, per ogni i=1,…,k.
n->heigth= max{1+ n1->height, …, 1+ nk->height} = max{1+ altezza T1,, …, 1+ altezza Tk} (per
I.I) = 1 + max altezza sottoalberi
![Page 50: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/50.jpg)
Alberi BinariAlberi Binari
Ogni nodo ha < 2 figli: figlio destro, figlio sinistro
a
b
e
d
f g
c
![Page 51: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/51.jpg)
Alberi BinariAlberi Binari
Definizione ricorsivaBASE. Albero vuoto è albero binario
PASSO. Dati 2 alberi binari T1,T2 ed un nuovo nodo r
T=r
è un albero binario
con sottoalbero di sinistra T1
sottoalbero di destra T2
T1 T2
![Page 52: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/52.jpg)
Alberi BinariAlberi Binari
Struttura datiTypedef struct NODE *TREE struct NODE{ etype nodelabel; TREE leftchild, rightchild; }
Bastano due puntatori per nodo: figlio destro, figlio sinistro
![Page 53: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/53.jpg)
Ricorsione su Alberi BinariRicorsione su Alberi Binari
FUNZIONE (T TREE) { Azione A0
FUNZIONE(T1) Azione A1; FUNZIONE(T2) Azione A2; }
![Page 54: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/54.jpg)
Visita InorderVisita Inorder
Visita Inorder: si devono visitare i nodi dell’albero in modo tale che
1. ogni nodo segue nella lista tutti i nodi del sottoalbero di sinistra
2. precede nella lista tutti i nodi del sottoalbero di destra
r
c1
T1
c2
T2
T=
Lista Inorder di T = (lista inorder T1, r, lista inorder
T2)
![Page 55: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/55.jpg)
Visita InorderVisita Inorder
Visita Inorder: si devono visitare i nodi dell’albero in modo tale che
1. ogni nodo segue nella lista tutti i nodi del sottoalbero di sinistra
2. precede nella lista tutti i nodi del sottoalbero di destra
a
b
e
d
f g
c
Lista Inorder: (e,b,a,f,d,g,c)
![Page 56: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/56.jpg)
Visita InorderVisita Inorder
Visita Inorder: si devono visitare i nodi dell’albero in modo tale che
1. ogni nodo segue nella lista tutti i nodi del sottoalbero di sinistra
2. precede nella lista tutti i nodi del sottoalbero di destra
void inorder(TREE T){ if (T!=NULL) { inorder(T->leftchild); printf(“%c\n”, T-
>nodelabel); inorder(T->rightchild); } }
r
c1
T1
c2
T2
T=
![Page 57: Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE: linea che unisce due nodi distinti Radice (root): in una](https://reader035.vdocumenti.com/reader035/viewer/2022062512/5542eb58497959361e8c2346/html5/thumbnails/57.jpg)
Visita InorderVisita Inorder
void inorder(TREE T){ if (T!=NULL) { inorder(T->leftchild); printf(“%c\n”, T-
>nodelabel); inorder(T->rightchild); } }
a
b
e
d
f g
c
Inorder: e,b,a,f,d,g,c