Esercizi svolti sugli alberi

Dati e Algoritmi I (Pietracaprina)
Esercizi sugli Alberi
Dati e Algoritmi I (Pietracaprina): Esercizi
1
Problema 1 Dimostrare che un albero non vuoto con n nodi interni, dove ogni nodo interno
ha almeno 2 figli, ha almeno n + 1 foglie
Soluzione. La dimostrazione procede per induzione sull’altezza h dell’albero. Come base
osserviamo che la proprietà è vera per un albero di altezza h = 0, che quindi ha un solo nodo
(foglia) e n = 0. Supponiamo che la proprietà sia vera per alberi di altezza al più h, con
h ≥ 0 fissato, e consideriamo un albero T di altezza h + 1 ≥ 1. Chiaramente la radice di T
deve essere un nodo interno. Sia d ≥ 2 il numero di figli della radice. Per 1 ≤ i ≤ d sia ni
il numero di nodi interni ed mi il numero di foglie nel sottoalbero radicato nelll’i-esimo figlio
della radice. Sia inoltre m il numero di foglie ed n il numero di nodi interni di T . Si ha allora
che
n = 1+
d
X
ni
i=1
m =
d
X
mi .
i=1
Poichè i sottoalberi figli della radice hanno altezza al più h, possiamo applicare l’ipotesi
induttiva e dedurre che
m=
d
X
mi ≥
i=1
d
X
d
X
i=1
i=1
(ni + 1) = d +
ni = (d − 1) + 1 +
d
X
ni = n + d − 1 ≥ n + 1,
i=1
2
in quanto d ≥ 2.
Problema 2 Si definisca albero d-ario proprio un albero ordinato in cui ogni nodo interno
ha esattamente d figli.
a. Disegnare due alberi ternari (d = 3) propri T1 e T2 con 8 nodi interni ciascuno, tali che
T1 ha altezza massima e T2 ha altezza minima. Quante foglie hanno T1 e T2 ?
b. Sia T un albero d-ario proprio di altezza h con n nodi interni ed m foglie. Usando gli
esempi precedenti e il buon senso trovare l’unica tra le seguenti relazioni che può valere
per T arbitrario e d ≥ 2:
(i) m = (d − 1)h + 1; (ii) m = (d − 1)n + 1; (iii) m = 5d + 2
c. Dimostrare la relazione trovata al punto precedente per induzione su h.
Soluzione.
a. L’albero T1 è il seguente (le foglie sono rappresentate da quadrati e i nodi interni da
cerchi).
i
i
i
i
i
i
i
i
Dati e Algoritmi I (Pietracaprina): Esercizi
2
L’albero T2 è il seguente:
i
i
i
i
i
i
i
i
Entrambi gli alberi hanno 17 foglie.
b. La (i) non è soddisfatta dall’albero T1 . La (iii), pur essendo soddisfatta sia da T1 che
da T2 , non ha senso in quanto non dipende da n. L’unica che può valere è la (ii).
c. Dimostriamo che m = (d−1)n+1 per induzione sull’altezza h dell’albero. La base h = 0
è vera in quanto un albero di altezza 0 ha 1 foglia e 0 nodi interni. Fissiamo h ≥ 0,
supponiamo che la relazione sia vera per alberi di altezza sino ad h, e consideriamo
un albero T di altezza h + 1 > 0. Sia Ti l’i-esimo sottoalbero figlio della radice di T ,
1 ≤ i ≤ d, e si indichi con ni il numero di nodi interni di Ti e con mi il numero di foglie
di Ti . Poichè ogni Ti ha altezza al più h, per ipotesi induttiva vale che mi = (d−1)ni +1.
Inoltre
m =
d
X
mi
i=1
n = 1+
d
X
ni ,
i=1
e quindi
m=
d
X
((d − 1)ni + 1) = (d − 1)n + 1.
i=1
2
Problema 3 Si ricordi che una espressione aritmetica E fully parenthesized in notazione infissa che usa solo operatori binari è definita come segue:
E = a
E = (E1 op E2 ),
dove a è una costante o variabile, E1 e E2 sono espressioni fully parenthesized in notazione
infissa, e op è un operatore binario. Sia T il parse tree associato a E, i cui nodi interni contengono gli operatori e le foglie le costanti o variabili di E. Sviluppare un algoritmo ricorsivo
infix che ricavi l’espressione E a partire dal parse tree T , e analizzarne la complessità in
tempo.
Dati e Algoritmi I (Pietracaprina): Esercizi
3
Soluzione. L’algoritmo è il seguente (si usa + per indicare la concatenazione di stringhe):
Algoritmo infix(T,v)
input Parse tree T , nodo v ∈ T
output espressione Ev rappresentata da Tv
if (T.isExternal(v)) then return v.element()
else return ’(’+infix(T,T.left(v))+v.element()+infix(T,T.right(v))+’)’
Per generare l’espressione completa associata a T , basterà invocare l’algoritmo con v=T.root().
La struttura dell’algoritmo è simile a quella di una visita, e quindi la sua complessità è lineare
nel numero di nodi del (sotto)albero sul quale è invocato.
2
Problema 4 (Esercizio C-7.3 del Goodrich-Tamassia, 5th Edition, 2010.) Progettare degli
algoritmi per le seguenti operazioni per un albero binario T (si assuma che l’albero binario
sia proprio):
• preorderNext(v): restituisce il nodo visitato dopo v nella visita in preorder di T
• inorderNext(v): restituisce il nodo visitato dopo v nella visita inorder di T
• postorderNext(v): restituisce il nodo visitato dopo v nella visita in postorder di T
Analizzare la complessità degli algoritmi.
Soluzione. Sviluppiamo l’algoritmo preorderNext(v) lasciando gli altri come esercizio per
il lettore. Assumiamo che se v è l’ultimo nodo visitato nella vista in preorder di T l’algoritmo
restituisca null. Si osservi che se v è un nodo interno, allora il suo successore nella visita
in preorder è il suo figlio sinisitro. Altrimenti, dobbiamo risalire da v sino a trovare il primo
antenato u (cioè l’antenato più profondo) tale che v sta nel sottoalbero sinistro di u. In questo
caso, il successore di v nella visita in preorder è il figlio destro di u. Se tale antenato u non
esiste, significa che v è la foglia che si incontra scendendo sempre a destra a partire dalla
radice di T , ed è quindi l’ultimo nodo visitato dalla vista in preorder di T . In questo caso
l’algoritmo restituisce null. Lo pseudocodice dell’algoritmo è il seguente:
Algoritmo preorderNext(v)
input Albero T, nodo v ∈ T
output successore di v in preoder, se esiste, altrimenti null
if (T.isInternal(v)) then return T.left(v)
while (!T.isRoot(v)) do {
if (v=T.left(T.parent(v))) then return T.right(T.parent(v))
else v ← T.parent(v)
}
return null
Si noti che il numero di iterazioni del while è limitato superiormente dalla profondità di v, e
che in ciascuna iterazione si esegue un numero costante di operazioni. Per il resto l’algoritmo
esegue un numero costante di operazioni. Dato che la profondità di un nodo è minore o uguale
all’altezza dell’albero, concludiamo che la complessità è O (h) con h altezza di T .
2
Dati e Algoritmi I (Pietracaprina): Esercizi
4
Problema 5 Sia T un albero binario proprio. Dato un nodo v ∈ T , si definisca imbalance(v)
la differenza in valore assoluto tra il numero di foglie nei sottoalberi sinistro e destro di
v. Se v è una foglia si assume imbalance(v) = 0. Si definisca anche imbalance(T ) =
maxv∈T imbalance(v).
a. Dimostrare un limite superiore all’imbalance di un albero binario proprio con n nodi, e
descrivere un albero il cui imbalance raggiunge tale limite.
b. Disegnare un albero binario proprio T in cui imbalance(T ) = imbalance(v) e v non è la
radice dell’albero.
c. Sviluppare un algoritmo efficiente per determinare imbalance(T ), e analizzarne la complessità in tempo.
Soluzione.
a. Se l’albero è proprio e ha n nodi, avrà m = (n + 1)/2 foglie. Sia v un nodo interno.
Allora, poichè l’albero è proprio, vi sarà almeno una foglia nel sottoalbero sinistro e
almeno una foglia nel sottoalbero destro di v. Quindi
imbalance(v) ≤ m − 2 = (n − 3)/2.
Un albero con n nodi il cui imbalance raggiunge tale limite è quello in cui la radice ha
come figlio sinistro una foglia, e come figlio destro un albero binario proprio con n − 2
nodi.
b. L’imbalance del seguente l’albero è 2 ed è ottenuto nel nodo evidenziato da un pallino
più grande.
t
y
t
t
t
t
t
t
t
t
t
t
t
c. Utilizziamo il seguente algoritmo ricorsivo che quando invocato su un nodo v ∈ T
calcola l’imbalance del sottoalbero Tv e il numero di foglie in Tv . Il valore imbalance(T )
si ottiene invocando l’algoritmo sulla radice. Si noti che calcolando un’informazione
più ricca (imbalance e numero di foglie invece che solo numero di foglie) si ottiene una
strategia algoritmica più efficiente.
Dati e Algoritmi I (Pietracaprina): Esercizi
5
Algoritmo maxImbalance(T,v)
input Albero T, nodo v ∈ T
output imbalance(Tv ) e numero di foglie in Tv
if (T.isExternal(v)) then return (0,1)
(bL, mL) ←− maxImbalance(T,T.left(v))
(bR, mR) ←− maxImbalance(T,T.right(v))
b ←− max {bL, bR, |mL - mR|}
m ←− mL+mR
return (b,m)
La struttura dell’algoritmo è la stessa di quella della visita in postorder, e quindi la sua
complessità è lineare nel numero di nodi del (sotto)albero sul quale è invocato.
2
Problema 6 Sia T un albero binario proprio. Si definisca la heightsum di T come la somma
delle altezze di tutti i suoi nodi. (Si ricordi che l’altezza di una foglia è 0, e quella di un nodo
interno è 1+la massima altezza dei suoi figli.)
a. Si sviluppi un algoritmo ricorsivo heightSum(T,v) che calcola la heightsum del sottoalbero Tv , per un nodo arbitrario v.
b. Analizzare la complessità in tempo di heightSum(T,T.root()).
Soluzione.
a. L’algoritmo heightSum(T,v) invocato su un nodo v ∈ T restituisce la somma delle
altezze dei nodi di Tv e l’altezza di v. Anche in questo caso, calcolando un’informazione
più ricca (somma delle altezze e altezza) si ottiene una strategia algoritmica più efficiente. Lo pseudocodice è il seguente:
Algoritmo heightSum(T,v)
input Albero T, nodo v ∈ T
output somma delle altezze dei nodi di Tv , altezza di v
if (T.isExternal(v)) then return (0,0)
(sL,hL) ← heightSum(T,T.left(v))
(sR,hR) ← heightSum(T,T.right(v))
h ← max{hL,hR}+1
s ← sL+sR+h
return (s,h)
b. Se invocato con v = T.root(), l’algoritmo esegue una visita in postorder di T , dove la
visita di un nodo interno corrisponde al calcolo delle quantità s e h, basandosi su quelle
ottenute dai figli, e quindi richiede tempo O (1). La complessità risulta essere O (n),
dove n è il numero di nodi di T .
Dati e Algoritmi I (Pietracaprina): Esercizi
6
2
Problema 7 (Esercizio C-7.21 del Goodrich-Tamassia, 5th Edition, 2010.) Sia T un albero
con n nodi. Si definisca il Lowest Common Ancestor (LCA) di due nodi v e w il nodo
più profondo di T che ha v e w come discendenti. Sviluppare un algoritmo che dati v e w
determini il loro LCA, e analizzarne la complessità.
Soluzione. L’idea dell’algoritmo è di risalire dal più profondo dei due nodi passati in input
sino all’antenato che sta alla stessa profondità dell’altro, e da qui risalire da entrambi sino a
trovare il primo antenato comune. (Si osservi che un antenato in comune esiste sicuramente
ed è la radice.) Per determinare la profondità di un nodo si utilizza l’algoritmo depth visto
a lezione. Lo pseudocodice dell’algoritmo richiesto è il seguente:
Algoritmo LCA(v,w)
input Albero T, nodi v,w ∈ T
output LCA(v,w)
dv ← depth(v); dw ← depth(w)
if (dv > dw ) then for i ← 1 to dv − dw do v ← T.parent(v)
else for i ← 1 to dw − dv do w ← T.parent(w)
while (v 6= w) do {
v ← T.parent(v)
w ← T.parent(w)
}
return v
Le invocazioni di depth hanno complessità proporzionale alle profondità di v e w. I cicli
for e il ciclo while eseguono, ciascuno, un numero di iterazioni limitato superiormente dalla
massima profondità dei due nodi, e in ciascuna iterazione eseguono un numero costante di operazioni. Dato che la profondità di un nodo di un albero è limitata superiormente dall’altezza
dell’albero, concludiamo che la complessità dell’algoritmo è O (h), con h altezza di T . Si
osservi che non si fanno assunzioni sull’arietà di T .
2
Problema 8 (Esercizio C-7.22 del Goodrich-Tamassia, 5th Edition, 2010.) Sia T un albero
binario con n nodi. Per ogni nodo v ∈ T sia dv la sua profondità. Si definisca la distanza
tra due nodi v e w in T come dv + dw − 2du , dove u è LCA(v, w) (vedi problema precedente).
Il diametro di T è definito come la massima distanza tra due nodi. Sviluppare un algoritmo
efficiente che dato T ne calcoli il diametro, e analizzarne la complessità.
Soluzione. L’algoritmo si basa sulla distinzione tra i seguenti tre casi:
Caso 1: Se T contiene un solo nodo foglia, il suo diametro è 0.
Caso 2: Se T è costituito dalla radice r con un solo sottoalbero (sinistro), che indichiamo
con T1 , allora i due nodi a distanza massima sono entrambi in T1 oppure uno è la radice
r e l’altro è la foglia v di massima profondità in T1 . In questo caso il diametro di T è il
massimo tra il diametro di T1 e la distanza tra r e v, dove tale distanza è pari all’altezza
di T , ovvero all’altezza di T1 più 1.
Dati e Algoritmi I (Pietracaprina): Esercizi
7
Caso 3: Se T è costituito dalla radice r con due sottoalberi, che indichiamo con T1 e T2 ,
allora i due nodi a distanza massima sono entrambi in T1 oppure entrambi in T2 oppure
uno è la foglia v di massima profondità in T1 e l’altro è la foglia w di massima profondità
in T2 . In questo caso il diametro di T è il massimo tra il diametro di T1 , il diametro di
T2 , e la distanza tra v e w, dove tale distanza è pari all’altezza di T1 più l’altezza di T2
più 2.
Scriviamo allora un algoritmo diametro che dato T e un nodo v ∈ T restituisce il diametro
di Tv e l’altezza di Tv . Ancora una volta, calcolando un’informazione più ricca (diametro e
altezza) si ottiene una strategia algoritmica più efficiente. Lo pseudocodice dell’algoritmo è
il seguente:
Algoritmo diametro(T,v)
input Albero T, nodo v ∈ T
output diametro di Tv e altezza di Tv
if (T.isExternal(v)) then return (0,0)
else if (!T.hasRight(v)) then {
(d,h) ← diametro(T,T.left(v))
return (max{d,h+1}, h+1)
}
else {
(d1,h1) ← diametro(T,T.left(v))
(d2,h2) ← diametro(T,T.right(v))
return (max{d1,d2,h1+h2+2}, max{h1,h2}+1)
}
La struttura dell’algoritmo è la stessa di quella della visita in postorder, e quindi la sua
complessità è lineare nel numero di nodi del (sotto)albero sul quale è invocato.
2