Algoritmi e Calcolo Parallelo 2012/2013 - Alberi

Prof. Pier Luca Lanzi

AlberiAlgoritmi e Calcolo Parallelo


Riferimenti

• Bertossi Alan A., Montresor Alberto. “Algoritmi e strutture di dati” (seconda edizione), CittàStudi 2010

• Stanley B. Lippman, Barbara E. Moo, Josee Lajoie“C++ Primer”, 5th Edition Addison-Wesley

2


Alberi Radicati

• Albero (definizione informale): insieme dinamico i cui elementi hanno relazioni di tipo gerarchico

• Albero (definizione ricorsiva) Insieme vuotoUna radice T e 0 o più sottoalberi, con la radice

di ogni sottoalbero collegata a T da un arco (orientato)

3


Alberi Radicati

• Albero radicatoUn insieme vuoto di nodi Un nodo radice R collegato a 0 o più alberi

(sottoalberi)

4


Alberi Radicati 5


6Alberi Radicati Binari


Alberi Radicati Binari

• Un albero binario è un albero ordinato in cui ogni nodo ha al più due figli e si fa distinzione tra il figlio sinistro ed il figlio destro di un nodo

• Nota: due alberi T e U aventi gli stessi nodi, gli stessi figli per ogni nodo e la stessa radice, sono distinti qualora un nodo u sia designato come figlio sinistro di un nodo v in T e come figlio destro del medesimo nodo in U

7


Alberi? 8

DAG Radice

Foresta


Alberi Radicati

• Profondità di un nodo: la lunghezza del percorso dalla radice al nodo (numero archi attraversati)

• Livello: l'insieme dei nodi alla stessa profondità

• Altezza dell'albero: massima profondità+1

• Grado di un nodo:numero dei figli

9


10Alberi Binari: Pieni e Completi

• Alberi binari pieni: Ogni nodo è una foglia oppure è un nodo interno con esattamente due figli non vuoti

• Alberi binari completi: se l’altezza dell’albero è d, allora tutte le foglie eccetto possibilmente il libello d sono completamente piene. L’ultimo livello ha tutti i nodi sul lato sinistro


Rappresentazione degli Alberi Binari

11


Realizzazione con Vettore dei Figli 12

/ /

/

/ / / /

//

/ /

/ ///////// / /

// / /

// / /

// / /

/ / /


Realizzazione con Puntatori Padre, Primo-figlio, Fratello

13


Altre Rappresentazioni:Con puntatore al parente

14


Altre Rappresentazioni: Array

Left Key Right

Par

0 1 A 3 -1

1 -1 B 2 0

2 -1 D -1 1

3 4 C 6 0

4 5 E -1 3

5 -1 G -1 4

6 7 F 8 3

7 -1 H -1 6

8 -1 I -1 6

15


Realizzazione con Vettore dei Padri

• L'albero è rappresentato da un vettore i cui elementi contengono l'indice del padre

16

a

b e

c d f g

T0 a

1 b

1 e

2 c

2 d

3 f

3 g


Possible Interfaccia 17


Algoritmi di Visita degli Alberi

• Visita (o attraversamento) di un albero:Algoritmo per “visitare” tutti i nodi di un albero

• In profondità (depth-first search, a scandaglio): DFSVengono visitati i rami, uno dopo l’altroTre varianti: pre-ordine, post-ordine, in-ordine

• In ampiezza (breadth-first search, a ventaglio): BFSA livelli, partendo dalla radice

18


Visita in Profondità: Implementazioni

VisitaPreOrdine(T) VisitaRadice(T); VisitaPreOrdine(T->left()); VisitaPreOrdine(T->right());}

VisitaPostOrdine(T) VisitaPostOrdine(T->left()); VisitaPostOrdine(T->right()); VisitaRadice(T);}

VisitaInOrdine(T) VisitaInOrdine(T->left()); VisitaRadice(T); VisitaInOrdine(T->right());}

19


Visita in Ampiezza

VisitaAmpiezza(T) q = new Queue() q.insert(T) while not q.empty() do p := q.dequeue() visita p q.enqueue(p.left()) q.enqueue(p.right())

20


Esercizi

• Stampare il risultato dellaVisita in pre-ordineVisita in-ordineVisita in post-ordineVisita in ampiezza

• Scrivere un algoritmo perCalcolare l’altezza di un albero binario TCalcolare il numero di nodi di un albero binario TStampare tutti i nodi di profondità h di un albero

binario T

21


Alberi Binari: Specifica 22


Alberi Binari: Realizzazione 23


Esercizi

• Dato un albero radicato T, calcolare la sua altezza

• Dato un albero radicato T, calcolare il numero totale di nodi

• Dato un albero radicato T, stampare tutti i nodi a profondità h

24

Algoritmi e Calcolo Parallelo 2012/2013 - Alberi

Education

Transcript of Algoritmi e Calcolo Parallelo 2012/2013 - Alberi