Page 44 - MATINF Nr. 1

44 C. B˘alc˘au

Demonstrat¸ie. Consider˘am din nou c˘a nivelul pe care este reprezentat˘a r˘ad˘acina arborelui este
numerotat cu 0. Rezult˘a c˘a:

• arborele are h(T) + 1 nivele, numerotate cu 0, 1, . . . , h(T);

• pe nivelele 0, 1, . . . , h(T) − 2 avem doar noduri interne, fiecare avˆand cˆate doi descendent , i;

• pe penultimul nivel, h(T) − 1, putem avea s , i noduri externe, iar nodurile interne de pe
acest nivel au de asemenea cˆate doi descendent , i;

• pe ultimul nivel, h(T), avem doar noduri externe;

i
• pentru orice i ∈ {0, 1, . . . , h(T) − 1}, pe nivelul i avem exact 2 noduri.

Notˆand cu a num˘arul de noduri interne de pe penultimul nivel s , i cu b num˘arul de noduri externe
de pe acelas , i nivel, obt , inem c˘a
a + b = 2 h(T)−1 (2)
(num˘arul total de noduri de pe penultimul nivel, nivelul h(T) − 1), iar a ≥ 1 (pe penultimul
nivel exist˘a cel put , in un nod intern).

Pe nivelele 0, 1, . . . , h(T) − 2 nu avem noduri externe, pe penultimul nivel, h(T) − 1, avem b
noduri externe, iar pe ultimul nivel, h(T), avem 2a noduri externe (s , i anume descendent , ii celor
a noduri interne de pe penultimul nivel), deci num˘arul total de noduri externe ale arborelui este
egal cu b + 2a. Rezult˘a c˘a
b + 2a = n + 1 (3)

s , i
X
D T (v) = b(h(T) − 1) + 2a · h(T). (4)
v∈E(T)
Din relat , iile (2) s , i (3) obt , inem c˘a

a = n + 1 − 2 h(T)−1 . (5)

Dar 1 ≤ a ≤ 2 h(T)−1 (a doua inegalitate rezult˘a din (2)), deci 1 ≤ n + 1 − 2 h(T)−1 ≤ 2 h(T)−1 .
Rezult˘a c˘a 2 h(T)−1 ≤ n < n + 1 s , i 2 h(T) ≥ n + 1, deci h(T) − 1 < log (n + 1) ≤ h(T) s , i astfel
2
h(T) = dlog (n + 1)e .
2
Conform (4), (3) s , i (5) obt , inem c˘a

X
D T (v) = (n + 1 − 2a)(h(T) − 1) + 2a · h(T) = (n + 1)h(T) + 2a − n − 1
v∈E(T)
Ä h(T)−1 ä h(T)
= (n + 1)h(T) + 2 n + 1 − 2 − n − 1 = (n + 1)h(T) + n + 1 − 2 ,

de unde rezult˘a a doua egalitate din enunt , .

Propozit , ia 6. Pentru orice arbore binar strict T cu n noduri interne, n ∈ N, avem

X dlog (n+1)e
D T (v) ≥ (n + 1) dlog (n + 1)e + n + 1 − 2 2 .
2
v∈E(T)
Mai mult, egalitatea are loc dac˘a s , i numai dac˘a toate nodurile externe sunt situate pe ultimul s , i,
eventual, pe penultimul nivel.