1 © Alberto Montresor Algoritmi e Strutture Dati Capitolo 5

Algoritmi e Strutture Dati
Capitolo 5 - Alberi
Alberto Montresor
Università di Trento
This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License. To view a
copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/2.5/ or send a letter to Creative
Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.
© Alberto Montresor
1
Alberi radicati
Albero: definizione informale
✦
E' un insieme dinamico i cui elementi hanno relazioni di tipo gerarchico
✦
Albero: definizione ricorsiva
✦
Insieme vuoto di nodi, oppure
✦
Una radice T e 0 o più sottoalberi, con la radice di ogni sottoalbero collegata a T da
un arco (orientato)
✦
T
es.: radice T con n sottoalberi
T1
© Alberto Montresor
T2
Tn
2
Alberi ordinati
T
Radice (root)
Figlio (child) di T
Nodi interni =
Nodi - Foglie
Padre (parent)
dei nodi j e k
Figlio di T
Radice del proprio
sottoalbero
Sottoalbero
a
j
k
...
Foglie (leaf)
© Alberto Montresor
Nodi fratelli
(figli di a)
3
Alberi: definizioni
In un albero
✦
Profondità di un nodo: la
lunghezza del percorso dalla
radice al nodo
(i.e., numero archi attraversati)
p=0
✦
p=1
Livello: l'insieme dei nodi alla
stessa profondità
p=2
Altezza dell'albero:
massimo livello delle sue foglie
p=3
✦
✦
Livello 3
Altezza albero: 3
© Alberto Montresor
4
Alberi?
DAG
Radice
Foresta
© Alberto Montresor
5
Alberi: una possibile specifica
© Alberto Montresor
6
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): DFS
✦
Vengono visitati i rami, uno dopo l’altro
✦
Tre varianti
✦
In ampiezza (breadth-first search, a ventaglio): BFS
✦
A livelli, partendo dalla radice
✦
© Alberto Montresor
7
Visita alberi: in profondità in ordine anticipato (previsita)
T
a
b
c
Sequenza: a
© Alberto Montresor
b
c
e
d
f
d
e
g
f
g
8
Visita alberi: in profondità in ordine posticipato (postvisita)
T
a
b
c
Sequenza: c
© Alberto Montresor
d
b
e
d
f
f
g
g
e
a
9
Visita alberi: in profondità in ordine simmetrico (invisita)
T
a
b
c
Sequenza (i=1): c
© Alberto Montresor
b
e
d
d
g
f
a
f
e
g
10
Visita alberi: in ampiezza
T
a
b
c
Sequenza: a
© Alberto Montresor
b
e
d
e
g
f
c
d
f
g
11
Realizzazione con vettore dei figli
/
/
/ / /
/ / /
/ / / /
/ / / /
/ / / /
/ / / /
/ /
/ / / /
/ / / /
/ / //
/ / / /
Padre
Rischio di sprecare memoria se
molti nodi hanno grado minore
del grado massimo k.
© Alberto Montresor
Nodo
Array
di Figli
12
Realizzazione con puntatori padre/primo-figlio/fratello
/
/
/
/
/
/
/
/
/
/
/
/
/
/
/
/
Padre
Nodo
Primo
Figlio
Fratello
Soluzione: usare una lista
di figli (fratelli).
© Alberto Montresor
13
Realizzazione con puntatori padre/primo-figlio/fratello
© Alberto Montresor
14
Realizzazione con puntatori padre/primo-figlio/fratello
© Alberto Montresor
15
Realizzazione con vettore dei padri
L'albero è rappresentato da un vettore i cui elementi contengono
l'indice del padre
✦
Esempio:
✦
0 a
T
1 b
a
1 e
b
2 c
2 d
c
e
d
f
g
3 f
3 g
© Alberto Montresor
16
Realizzazione con vettore dei padri
© Alberto Montresor
17
Alberi binari
Definizione
✦
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
✦
© Alberto Montresor
18
Alberi binari
Figlio sinistro
Radice del
sottoalbero sinistro
Figlio destro
Radice del
sottoalbero destro
Radice
j.parent()
Padre del
nodo j (e k)
Sottoalbero
sinistro
Sottoalbero
destro
a
j
k
a.left()
© Alberto Montresor
a.right()
19
Alberi binari: specifica
© Alberto Montresor
20
Alberi binari: realizzazione
/
/
Padre
Figlio
Figlio
Sinistro Destro
© Alberto Montresor
/
/
/
/
/
/
/
/
Nodo
21
Alberi binari: realizzazione
Per motivi di spazio, le operazioni parent(), left(), right(), read() e write() non sono mostrate; semplicemente, restituiscono il valore della variabile corrispondente.
© Alberto Montresor
22
Alberi binari: visite in profondità
© Alberto Montresor
23
Limite inferiore complessità ordinamento
Albero delle scelte in algoritmi di ordinamento
✦
Sequenze di confronti (a due alternative) rappresentabile come albero binario
✦
Nodi interni → confronti,
✦
foglie → soluzioni del problema
Percorso radice-foglia: insieme di confronti per individuare una soluzione
✦
Limite inferiore ordinamento
✦
Sia n la dimensione del vettore
✦
Numero di possibili soluzioni: n!
✦
Altezza minima albero:
log2 n!
✦
Da cui deriva che qualunque
algoritmo di ordinamento
richiede Ω(n log n) confronti
✦
© Alberto Montresor
24
Semplici esercizi basati su visite
Es. 5.1 - 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
✦
www.xkcd.com
© Alberto Montresor
25