Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE:...

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


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


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

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=


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





r in T) Es. n3

n6 n7

albero n2

n3

alberi n5

n6 n7

è albero

è albero


n1

n2

n3

n4 n5

n6 n7




r in T) Es. n3

n6 n7

albero n2

n3

alberi n5

n6 n7

è albero

è albero

n2

n3

n4 n5

n6 n7

alberi è albero

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


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


Sottoalbero con radice n: albero formato dal nodo n con tutti i suoi discendenti

n1

n2

n3

n4 n5

n6 n7


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


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


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

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’’}


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)


TRIE: Serve per memorizzare stringhe di caratteri. 1. Ogni nodo ha associata una lettera2. La stringa rappresentata dal nodo è la sequenza di




-


TRIE: Serve per memorizzare stringhe di caratteri. 1. Ogni nodo ha associata una lettera2. La stringa rapperesentata dal nodo è la sequenza di




-

h -

-






-

h

e +

-

-






-

h

e

r

s +

+

-

-

-






-

h

e

r

s

i

s

+

+

-

-

-

-

+






-

h s

he

r

s

i

es

+

+

-

-

-

-

--

++


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 +

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

ALBERI Sinistra-DestraALBERI Sinistra-Destra

a

b

e

c d

f g

NODE infotype leftmostchild rightsibling

a /

b c / d /

e / / f / g / /


h s

he

r

s

i

es

+

+

-

-

-

-

--

++

- /

h - s - /

e + i - h - /

r - /

s + / /

s + / / e + / /

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=


Vogliamo provare che l’affermazione S(T) è vera per ogni albero T

Base: S(T) è vera per ogni albero con un singolo nodo

r


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

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

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


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


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

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

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


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=


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

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=

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)


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; }


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=


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


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=


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)


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=


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=

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

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


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

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

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

Alberi BinariAlberi Binari

Ogni nodo ha < 2 figli: figlio destro, figlio sinistro

a

b

e

d

f g

c


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


Struttura datiTypedef struct NODE *TREE struct NODE{ etype nodelabel; TREE leftchild, rightchild; }

Bastano due puntatori per nodo: figlio destro, figlio sinistro

Ricorsione su Alberi BinariRicorsione su Alberi Binari

FUNZIONE (T TREE) { Azione A0

FUNZIONE(T1) Azione A1; FUNZIONE(T2) Azione A2; }

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)





a

b

e

d

f g

c

Lista Inorder: (e,b,a,f,d,g,c)





void inorder(TREE T){ if (T!=NULL) { inorder(T->leftchild); printf(“%c\n”, T-

>nodelabel); inorder(T->rightchild); } }

r

c1

T1

c2

T2

T=


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

Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE:...

Documents

Transcript of Modello dati ALBERO Albero: Albero: insieme di punti chiamati NODI e linee chiamate EDGES EDGE:...