Dati e Algoritmi (Pietracaprina)

Esercizi sugli Alberi

Dati e Algoritmi (Pietracaprina): Esercizi 1

Problema 1 Si supponga che la visita in preorder di un albero ordinato di 6 nodi incontri

i nodi nell’ordine ABCDEF. Dire quali delle seguenti sequenze può rappresentare la visita
in postorder dello stesso albero (motivando la risposta e disegnando l’albero): BAFECD,
CDBFEA, CDAEFB.

Soluzione. L’unica sequenza che può rappresentare la visita in postorder dello stesso albero
è CDBFEA, in quanto il primo nodo visitato in preorder (la radice), ovvero il nodo A, deve
essere l’ultimo visitato in postorder. L’unico albero compatibile con entrambe le visite è il
seguente: A radice; B ed E figli della radice, C e D figli di B; ed F figlio di E. □

Problema 2 (Esercizio C-8.50 del testo [GTG14]) Sia T un albero. Dati due nodi v, w ∈
T si definisce il Lowest Common Ancestor di v e w (LCA(v, w)) come l’antenato comune
più profondo. Progettare un algoritmo efficiente per calcolare LCA(v, w), analizzandone 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 nodi v,w ∈ T
output LCA(v,w)
dv ← [Link](v); dw ← [Link](w);
if (dv > dw ) then for i ← 1 to dv − dw do v ← [Link](v)
else for i ← 1 to dw − dv do w ← [Link](w);
while (v ̸= w) do {
v ← [Link](v)
w ← [Link](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 op-
erazioni. 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 . In
effetti la complessità è Θ (h), dato che esiste un’istanza che richiede tempo proporzionale ad
h (quella in cui v è la foglia a profondità massima in T , ovvero profondità h). Si osservi che
la correttezza dell’algoritmo e l’analisi non richiedono assunzioni sull’arietà di T . □
Dati e Algoritmi (Pietracaprina): Esercizi 2

Problema 3 Si supponga di calcolare l’altezza di un albero T di n nodi invocando l’algoritmo

depth(v) da ciascuna foglia v di T e restituendo come altezza la massima profondità ottenuta.
Dimostrare che tale strategia ha una complessità al caso pessimo Ω n2 . (È l’algoritmo

heightBad decritto in [GTG14]. Si veda anche l’esercizio C-8.27 del testo.)

Soluzione. L’algoritmo heightBad è il seguente

Algoritmo heightBad(T)
input Albero T
output Altezza di T calcolata come max depth di una foglia
h ← 0;
forall v ∈ [Link]() do {
if [Link](v) then h ← max{h, [Link](v)}
}
return h

Per ottenere un lower bound alla complessità è sufficiente limitarsi al costo delle invocazioni
di depth. Si ricordi che depth(v) richiede Θ (dv ) operazioni, dove dv è la profondità del nodo
v. Si ha quindi che la complessità della strategia indicata è
 
X
Ω (dv )
foglie v∈T

Gli esempi nella Fig.
1 mostrano che per ogni n esistono alberi di n nodi in cui
2
P
foglie v∈T (dv ) ∈ Ω n . (Gli esempi considerano il caso n pari, ma possono essere facil-
mente estesi al caso n dispari.) Nell’albero a sinistra ci sono n/2 foglie a profondità n/2
ciascuna, mentre in quello a destra ci sono ⌈n/4⌉ foglie a profondità ⌈n/4⌉ ciascuna. □

Problema 4 Si consideri un albero T in cui ogni nodo v contiene un valore binario, restitutito
da [Link](), e si dice alive se tale valore è 1, e dead se esso è 0. Progettare un
algoritmo ricorsivo allLiveAncestors che per ogni nodo v ∈ T memorizzi in un campo
[Link] il numero di antenati alive di v, e analizzare la complessità.

Soluzione. Detta allLiveAncestors(v) la generica invocazione su un nodo v ∈ T , per

risolvere il problema si eseguirà allLiveAncestors([Link]()). L’idea è simile a quella us-
ata nell’algoritmo allDepths visto a lezione. Si usa lo schema della visita in preorder di Tv
impostando il campo liveAncestors di v basandosi sul valore del campo corrispondente nel
padre (che sarà già stato impostato) e del bit contenuto nel nodo. Dopodiché, se v è interno,
si invoca ricorsivamente l’algoritmo sui figli. Lo pseudocodice è il seguente:
Dati e Algoritmi (Pietracaprina): Esercizi 3

Figure 1: Esempi di alberi in cui la somma delle profondità delle foglie è Ω n2 .

Algoritmo allLiveAncestors(v)
input nodo v ∈ T, tale che ∀u∈T, u antenato di v, [Link] correttamente
impostato
output T con [Link] correttamente impostato ∀u∈Tv
if [Link](v) then [Link] ← [Link]()
else [Link] ← [Link]()+[Link](v).liveAncestors
foreach (w ∈ [Link](v)) do allLiveAncestors(w)

Analizziamo la complessità di allLiveAncestors([Link]()). Si osserva che l’algoritmo es-

egue una visita in preorder di T , dove la visita di un nodo interno corrisponde alla impostazione
del campo [Link], che richiede Θ (1) operazioni. Dall’analisi della visita in pre-
order fatta a lezione si ricava immediatamente che la complessità è Θ (n), dove n è il numero
di nodi di T . □

Problema 5 Progettare un algoritmo che dato un albero T , per ciascun nodo v ∈ T memo-
rizzi la sua altezza in un campo [Link], e analizzarne la complessità in funzione del numero
di nodi n dell’albero.

Soluzione. L’algoritmo allHeights(v) riportato sotto è un semplice adattamento

dell’algoritmo height visto a lezione. Si osservi che oltre che impostare il campo height dei
Dati e Algoritmi (Pietracaprina): Esercizi 4

nodi del sottoalbero Tv restituisce anche l’altezza di v. In questo modo, dall’invocazione ricor-
siva sui figli di v si ottengono le loro altezze e si è quindi in grado di determinare l’altezza di v.

Algoritmo allHeights(v)
input nodo v ∈ T
output altezza di v e T con [Link] correttamente impostato ∀u∈Tv
h ← 0
foreach (w ∈ [Link](v)) do h ← max {h,1+allHeights(w)}
[Link] ← h
return h

Per memorizzare le altezze in tutti i nodi dell’albero sarà sufficiente invocare

allHeights([Link]()). La complessità è la stessa dell’algoritmo height, ovvero Θ (n).
Osservazione. Questo esercizio (come diversi altri nella dispensa) mostra che, a volte, cal-
colare una informazione più ricca permette di migliorare le prestazioni. □

Problema 6 Dimostrare che in un albero binario proprio con m foglie e altezza h si ha che
m ≥ h + 1.

Soluzione. Dimostriamo la relazione per induzione sull’altezza h dell’albero. La base h = 0

è vera in quanto un albero di altezza 0 ha 1 foglia, e quindi m = h + 1. 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. Siano T1 e T2 i due sottoalberi figli della radice. Si indichi con mi
il numero di foglie in Ti e con hi l’altezza di Ti (i = 1, 2). Si ricordi che, per definizione,
l’altezza di T , ovvero h + 1, è uguale a 1 + max{h1 , h2 }, e vale quindi che h1 , h2 ≤ h. Se T
ha m foglie si ha che

m = m1 + m2
≥ h1 + 1 + h2 + 1 (per hp. induttiva)
≥ max{h1 , h2 } + 2
= (h + 1) + 1.

Problema 7 Dimostrare che per ogni n > 0 dispari esiste un albero binario proprio T con n
√
nodi e altezza Θ ( n).
√
Soluzione. Se n = 1 la dimostrazione è banale. Supponiamo n ≥ 3. Sia h = ⌊ n⌋. L’albero
cercato si ottiene combinando un albero molto sbilanciato T ′ di altezza h e con 2h + 1 nodi, al
Dati e Algoritmi (Pietracaprina): Esercizi 5

quale viene attaccato, come figlio della radice, un albero molto bilanciato T ′′ con n − 2h nodi
e altezza O (log n). Si noti che l’ipotesi n ≥ 3, assicura che n − 2h ≥ 0. Più specificatamente,
si consideri come T ′ un albero costituito da una dorsale di h + 1 nodi u0 , u1 , . . . , uh , con u0
radice e ui figlio sinistro di ui−1 , e dai figli destri di u0 , u1 , . . . , uh−1 . Invece, si consideri come
T ′′ , la cui radice viene fatta coincidere con il figlio destro di u0 , un albero tale che ogni suo
livello i, tranne l’ultimo, ha il massimo numero (2i ) di nodi. Esempi di T ′ e T ′′ sono stati
disegnati nei lucidi sugli Alberi Binari presentati a lezione, come casi di massimo e minimo
sbilanciamento. □

Problema 8 Dimostrare che in un albero non vuoto T con n nodi di cui m foglie, dove ogni
nodo interno ha almeno 2 figli, si ha che m ≥ n − m + 1.

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). 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 k ≥ 2 il numero di figli della radice. Per 1 ≤ i ≤ k sia ni il numero di nodi
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 di T . Si ha allora che
k
X
n = 1+ ni
i=1
k
X
m = mi .
i=1

Poichè i sottoalberi figli della radice hanno altezza al più h, possiamo applicare l’ipotesi
induttiva e dedurre che
k
X k
X k
X k
X
m= mi ≥ (ni − mi + 1) = ni − mi + k = n − m + (k − 1) ≥ n − m + 1,
i=1 i=1 i=1 i=1

in quanto k ≥ 2. □

Problema 9 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:
Dati e Algoritmi (Pietracaprina): Esercizi 6

(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

L’albero T2 è il seguente:

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
d
X
m = mi
i=1
d
X
n = 1+ ni ,
i=1
Dati e Algoritmi (Pietracaprina): Esercizi 7

e quindi
d
X
m= ((d − 1)ni + 1) = (d − 1)n + 1.
i=1

Problema 10 Progettare e analizzare un algoritmo che dato un Parse Tree T restituisce il

valore della espressione E associata a T , assumendo che i valori di costanti e variabili siano
noti.

Soluzione. L’algoritmo si basa sullo schema di visita in postorder. Lo pseudocodice è il

seguente:

Algoritmo evaluateExpression(v)
input nodo v ∈ T, dove T e’ il Parse Tree per E
output Valore della espressione associata al sottoalbero Tv
if ([Link](v)) then return [Link]()
else {
x ← evaluateExpression([Link](v));
y ← evaluateExpression([Link](v));
op ← [Link]();
return x op y
}

Come anticipato, la struttura dell’algoritmo è quella della visita in postorder, e la visita di

un nodo v consiste nella lettura di op e nel calcolo del valore x op y, che assumiamo richieda
Θ (1) operazioni. Quindi la complessità di evaluateExpression([Link]()) è Θ (n), dove n
è il numero di nodi di T , cioè il numero di costanti, variabili e operatori in E. □

Problema 11 Progettare e analizzare un algoritmo che data una lista che rappresenta una
espressione E in notazione postfissa, restituisce il valore di E, assumendo che i valori di
costanti e variabili siano noti.

Soluzione. Considerata la definizione di notazione postfissa, per i calcolo del valore dell’espressione
E è sufficiente una scansione della lista che rappresenta l’espressione, appunto in notazione
postfissa, e l’uso di una pila di appoggio. Lo pseudocodice è il seguente.
Dati e Algoritmi (Pietracaprina): Esercizi 8

Algoritmo evaluatePostfix(E)
input Positional List E che rappresenta un’espressione in notazione postfissa
output Valore della espressione rappresentata da E
S ← Stack vuota; /* contenitore per operatori/costanti/variabili */
p ← [Link]();
while (p <> null) do {
if ([Link]() = costante/variabile) then [Link]([Link]());
else {
op = [Link](); /* operatore rappresentato da p */
x ← [Link]();
y ← [Link]();
[Link](x op y);
}
p ← [Link](p);
}
return [Link]()

Assumendo che op sia una operazione elementare, ogni iterazione del while richiede Θ (1)
operazioni, e la complessità di evaluatePostfix(E) è Θ (n), dove n = |E|, cioè il numero di
costanti, variabili e operatoriche compaiono nell’espressione. □

Problema 12 (Esercizio C-8.41 del testo [GTG14]) Progettare tre algoritmi iterativi
preorderNext(v), inorderNext(v) e postorderNext(v) che dato un albero binario pro-
prio T e un nodo v ∈ T restituiscano il nodo visitato dopo v nella visita di T rispettivamente
in preorder, inorder e postorder, o null, se v è l’ultimo nodo visitato, analizzandone la com-
plessità.

Soluzione. Progettiamo prima l’algoritmo preorderNext(v). 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:
Dati e Algoritmi (Pietracaprina): Esercizi 9

Algoritmo preorderNext(v)
input nodo v ∈ T
output successore di v nella visita in preoder, se esiste, altrimenti null
if ([Link](v)) then return [Link](v)
while () do {
if (v=[Link]([Link](v))) then return [Link](v)
else v ← [Link](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 .
Consideriamo adesso inorderNext(v). Si osservi che se v è un nodo interno, il suo
successore nella visita inorder sarà la foglia più a sinistra nel sottoalbero destro di v. Se
invece v è una foglia, il suo successore nella visita inorder sarà il primo antenato incontrato
risalendo verso la radice, tale che v è nel suo sottoalbero sinistro. Se tale antenato non esiste,
allora v è la foglia più a destra dell’albero ed è quindi l’ultimo nodo visitato. In questo caso,
l’algoritmo restituisce null. Lo pseudocodice dell’algoritmo è il seguente:

Algoritmo inorderNext(v)
input nodo v ∈ T
output successore di v nella visita inorder, se esiste, altrimenti null
if ([Link](v)) then {
v ← [Link](v)
while () do v ← [Link](v)
return v
}
while () do {
if (v=[Link]([Link](v))) then return [Link](v)
else v ← [Link](v)
}
return null

Si noti che il numero di iterazioni di ciascuno dei due cicli while è limitato dall’altezza h
di T , e che in ciascuna iterazione si esegue un numero costante di operazioni. Per il resto
l’algoritmo esegue un numero costante di operazioni. Concludiamo quindi che la complessità
è O (h). Il progetto e l’analisi di postorderNext(v) sono lasciati come esercizio. □
Dati e Algoritmi (Pietracaprina): Esercizi 10

Problema 13 Si vuole progettare un algoritmo ricorsivo heightSum per calcolare la somma

delle altezze di tutti i nodi di un albero binario proprio T . Detta heightSum(v) la generica
invocazione su un nodo v ∈ T , per risolvere il problema si eseguirà heightSum([Link]()).

a. Descrivere tramite pseudocodice heightSum(v), specificandone con attenzione l’input e

l’output.

b. Analizzare la complessità di heightSum([Link]()) in funzione del numero n di nodi in

T.

Soluzione.

a. L’algoritmo heightSum(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 output più ricco
(somma delle altezze e altezza) si ottiene una strategia algoritmica più efficiente. Lo
pseudocodice è il seguente:

Algoritmo heightSum(v)
input nodo v ∈ T
output somma delle altezze dei nodi di Tv , altezza di v
if ([Link](v)) then return (0,0)
(sL,hL) ← heightSum([Link](v))
(sR,hR) ← heightSum([Link](v))
h ← max{hL,hR}+1
s ← sL+sR+h
return (s,h)

b. Se invocato con v = [Link](), 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 Θ (n).

Problema 14 Si vuole progettare un algoritmo ricorsivo deepLeaf per trovare la foglia più
profonda in un albero binario proprio T .

a. Descrivere tramite pseudocodice la generica invocazione di deepLeaf, specificandone con

attenzione l’input e l’output.

b. Analizzare la complessità di deepLeaf.

Soluzione.
Dati e Algoritmi (Pietracaprina): Esercizi 11

a. Detta deepLeaf(v) la generica invocazione su un nodo v ∈ T , per risolvere il prob-

lema si eseguirà deepLeaf([Link]()). Si tenga presente che per ogni sottoalbero Tv la
profondità (in Tv ) della sua foglia più profonda è pari all’altezza di Tv , e la foglia più
profonda in Tv sarà la foglia più profonda nel sottoalbero sx o dx di altezza massima. È
quindi opportuno seguire lo schema della visita in postorder chiedendo che deepLeaf(v)
restituisca oltre alla foglia w più profonda in Tv anche l’altezza di Tv (ovvero la pro-
fondità di w in Tv ). Ancora una volta, calcolando un’informazione più ricca (foglia più
profonda e altezza) si ottiene una strategia algoritmica più efficiente. Lo pseudocodice
è il seguente:

Algoritmo deepLeaf(v)
input nodo v ∈ T
output Foglia w ∈ Tv piu’ profonda e altezza h di Tv
if ([Link](v)) then return (v,0)
(wL,hL) ← deepLeaf([Link](v))
(wR,hR) ← deepLeaf([Link](v))
if (hL > hR) then {w ← wL; h ← hL+1}
else {w ← wR; h ← hR+1}
return (w,h)

b. Se invocato con v=[Link](), l’algoritmo esegue una visita in postorder di T , dove la

visita di un nodo interno corrisponde alla determinazione di w e h, basandosi sulle coppie
(wL,hL) e (wR,hR) ottenute dai figli, e quindi richiede tempo Θ (1). La complessità
risulta essere Θ (n), dove n è il numero di nodi di T .

Problema 15 Sia T un albero binario proprio dove ogni nodo v ∈ T contiene un valore
binario. Un nodo v ∈ T si dice 3-balanced, se |n0 (v) − n1 (v)| ≤ 3, dove n0 (v) e n1 (v)
denotano il numero di 0 (n0 (v)) e 1 (n1 (v)) nel sottoalbero Tv . Si progetti in pseudocodice un
algoritmo ricorsivo All3Balanced per determinare se tutti i nodi di T sono 3-balanced, con
complessità lineare nel numero di nodi di T .

Soluzione. Sia All3Balanced(v) l’invocazione generica dell’algoritmo su un nodo v ∈ T .

Per determinare se tutti i nodi di T sono 3-balanced, sin invocherà All3Balanced(v) con v =
[Link](). Lo pseudocodice è il seguente
Dati e Algoritmi (Pietracaprina): Esercizi 12

Algoritmo All3Balanced(v)
input nodo v ∈ T
output n0 (v), n1 (v), booleano bv che vale ‘‘true’’ se tutti i nodi di Tv
sono 3-balanced, e ‘‘false’’ altrimenti
if ([Link]() = 0) then {n0 (v) ← 1; n1 (v) ← 0}
else {n0 (v) ← 0; n1 (v) ← 1};
if (T .isExternal(v)) then return (n0 (v), n1 (v), true);
(n0,L , n1,L , bL ) ← All3Balanced(T .left());
(n0,R , n1,R , bR ) ← All3Balanced(T .right());
n0 (v) ← n0 (v) + n0,L + n0,R ;
n1 (v) ← n1 (v) + n1,L + n1,R ;
if (|n0 (v) − n1 (v)| ≤ 3) then return (n0 (v), n1 (v), (bL AND bR ))
else return (n0 (v), n1 (v), false)

Se invocato con v = [Link](), l’algoritmo esegue una visita in postorder di T , dove la

visita di un nodo interno corrisponde al calcolo delle quantità n0 (v), n1 (v) e del valore del
boolea no da restituire, e quindi richiede tempo O (1). La complessità risulta essere Θ (n). □

Problema 16 Un albero di sensori è un albero binario proprio T i cui nodi rappresentano

sensori. Ciascun sensore v ∈ T ha un flag [Link] che vale 1 se il sensore è acceso, e 0 se
è spento. Si vuole progettare un algoritmo ricorsivo maxOnHeight che, dato un albero di
sensori T , restituisca la massima altezza di un sensore acceso. Se tutti i sensori sono spenti,
l’algoritmo restituisce -1.

a. Descrivere tramite pseudocodice la generica invocazione di maxOnHeight, specificandone

con attenzione l’input e l’output.

b. Analizzare la complessità di maxOnHeight.

Soluzione.

a. Detta maxOnHeight(v) la generica invocazione su un nodo v ∈ T , per risolvere il prob-

lema si eseguirà maxOnHeight([Link]()). Basiamo l’algoritmo sullo schema di visita
in postorder.
Dati e Algoritmi (Pietracaprina): Esercizi 13

Algoritmo maxOnHeight(v)
input nodo v ∈ T
output max altezza di un sensore acceso in Tv (-1 se tutti i sensori in
Tv sono spenti) e altezza di Tv
if ([Link](v)) then
if ([Link]=1) then return (0,0) else return (-1,0);
(hL,mL) ← maxOnHeight([Link](v));
(hR,mR) ← maxOnHeight([Link](v));
h ← max{hL,hR};
m ← max{mL,mR};
if ([Link]=1) then return (h,h) else return (m,h)

b. Se invocato con v = [Link](), l’algoritmo esegue una visita in postorder di T , dove la

visita di un nodo richiede tempo O (1). La complessità risulta essere O (n), dove n è il
numero di nodi di T .

Problema 17 Sia T un albero binario proprio dove ogni nodo v ∈ T memorizza un valore
[Link] che può essere 1 o -1. Un nodo v ∈ T si dice strong se la somma dei valori memorizzati
nei nodi del sottoalbero Tv è > 0. Progettare un algoritmo countStrong per contare il numero
di nodi strong in un tale albero T , e analizzarne la complessità.

Soluzione. Scriviamo un algoritmo ricorsivo countStrong che dato T e un nodo v ∈ T resti-

tuisce il numero di nodi strong in Tv , la somma dei valori Tv . Il numero di nodi strong di T si
otterrà invocando l’algoritmo con v = [Link](). Ancora una volta, calcolando un’informazione
più ricca (numero di nodi strong e somma dei valori) si ottiene una strategia algoritmica più
efficiente. Lo pseudocodice dell’algoritmo è il seguente:

Algoritmo countStrong(v)
input nodo v ∈ T
output count = numero di nodi strong in Tv , sum = somma dei valori Tv
if ([Link](v)) then
if ([Link]=1) then return (1,1) else return (0,-1)
(cL,sL) ← countStrong([Link](v))
(cR,sR) ← countStrong([Link](v))
sum ← sL+sR+[Link]
if (sum>0) then (count ← cL+cR+1) else (count ← cL+cR)
return (count,sum)
Dati e Algoritmi (Pietracaprina): Esercizi 14

Se invocato con v = [Link](), l’algoritmo esegue una visita in postorder di T , dove la visita
di un nodo interno corrisponde al calcolo delle quantità sum e count, basandosi su quelle
ottenute dai figli e sul valore del nodo, e quindi richiede tempo O (1). La complessità risulta
quindi la stessa della visita in postorder, ovvero Θ (n), dove n è il numero di nodi di T . □

Problema 18 (Adattamento dall’esercizio C-8.52 del testo [GTG14]) Sia T un albero binario
proprio con n nodi. Il diametro di T è definito come la massima distanza tra due nodi, dove
la distanza tra due nodi u e v è la somma delle loro profondità nel sottoalbero con radice
LCA(u, v). Progettare e analizzare un algoritmo ricorsivo efficiente per calcolare il diametro
di un albero. (Suggerimento: è facile vedere che, se n > 1, il diametro di T si ottiene
come massimo tra tre quantità: il diametro del sottoalbero sinistro, il diametro del sottoalbero
destro, e la somma d1 + d2 + 2, dove d1 è la massima profondità di una foglia nel sottoalbero
sinistro, e d2 è la massima profondità di una foglia nel sottoalbero destro.)

Soluzione. Scriviamo un algoritmo ricorsivo diametro che dato T e un nodo v ∈ T restituisce

il diametro di Tv e la massima profondità di una foglia di Tv . Il diametro di T si otterrà invo-
cando l’algoritmo con v = [Link](). Ancora una volta, calcolando un’informazione più ricca
(diametro e max profondità di una foglia) si ottiene una strategia algoritmica più efficiente.
Lo pseudocodice dell’algoritmo è il seguente:

Algoritmo diametro(v)
input nodo v ∈ T
output diametro di Tv e max profondita’ di una foglia di Tv
if ([Link](v)) then return (0,0)
else {
(diam1,dmax1) ← diametro([Link](v))
(diam2,dmax2) ← diametro([Link](v))
diam ← max{diam1,diam2,dmax1+dmax2+2}
dmax ← max{dmax1,dmax2}+1
return (diam,dmax)
}

Se invocato con v = [Link](), l’algoritmo esegue una visita in postorder di T , dove la visita
di un nodo interno corrisponde al delle quantità diam e dimax, basandosi su quelle ottenute
dai figli e sul valore del nodo, e quindi richiede tempo O (1). La complessità risulta quindi la
stessa della visita in postorder, ovvero Θ (n), dove n è il numero di nodi di T . □