Page 43 - MATINF Nr. 1
P. 43
Optimalitatea algoritmului de c˘autare binar˘a 43
penultimul nivel, deci x are ca descendent , i dou˘a noduri externe y s , i z, situate pe ultimul nivel.
Fie
0
T = T \ {y, z} = (V \ {y, z}, F \ {[x, y], [x, z]})
0
arborele obt , inut din T prin eliminarea nodurilor externe y s , i z. Evident, T este arbore binar
0
0
0
strict s , i I(T ) = I(T) \ {x}, E(T ) = E(T) \ {y, z} ∪ {x}, deci card(I(T )) = card(I(T)) − 1 =
0
0
n − 1, card(E(T )) = card(E(T)) − 1. Conform ipotezei de induct , ie, aplicat˘a pentru T , avem
0
0
0
card(E(T )) = card(I(T )) + 1 = n, deci card(E(T)) = card(E(T )) + 1 = n + 1, adic˘a arborele
T are n + 1 noduri externe. Demonstrat , ia prin induct , ie este ˆıncheiat˘a.
Propozit , ia 3. Pentru orice arbore binar strict T cu n noduri interne, n ∈ N, avem
X X
D T (v) = D T (v) + 2n.
v∈E(T) v∈I(T)
Demonstrat¸ie. Demonstr˘am egalitatea din enunt , prin induct , ie dup˘a n.
Pentru n = 0 este evident c˘a arborele T este format doar din nodul r˘ad˘acin˘a r, E(T) = {r},
I(T) = Ø, P D T (v) = D T (r) = 0, P D T (v) + 2n = 0 + 2 · 0 = 0, deci egalitatea din
v∈E(T) v∈I(T)
enunt , este verificat˘a.
Presupunem egalitatea adev˘arat˘a pentru n − 1 s , i o demonstr˘am pentru n, n ≥ 1. Fie
T = (V, F) un arbore binar strict cu n noduri interne. Fie x un nod intern al lui T situat pe
penultimul nivel, deci x are ca descendent , i dou˘a noduri externe y s , i z, situate pe ultimul nivel.
0
Evident, D T (y) = D T (z) = 1+D T (x). Fie T = T \{y, z} = (V \{y, z}, F \{[x, y], [x, z]}) arborele
0
obt , inut din T prin eliminarea nodurilor externe y s , i z. Evident, T r˘amˆane tot arbore binar
0 0 0 0
strict s , i I(T ) = I(T) \ {x}, E(T ) = E(T) \ {y, z} ∪ {x}, D T 0(v) = D T (v), ∀ v ∈ I(T ) ∪ E(T ).
0
Utilizˆand s , i ipoteza de induct , ie, aplicat˘a pentru T , avem P D T (v) = P D T 0(v)−D T 0(x)+
0
v∈E(T) v∈E(T )
D T (y)+D T (z) = P D T 0(v)+2(n−1)−D T (x)+2(1+D T (x)) = P D T (v)+D T (x)+2n =
0
v∈I(T ) v∈I(T)\{x}
D T (v) + 2n. Demonstrat , ia prin induct , ie este ˆıncheiat˘a.
P
v∈I(T)
Propozit , ia 4. Pentru orice arbore binar strict T cu n noduri interne, n ∈ N, avem
h(T) ≥ dlog (n + 1)e .
2
Demonstrat¸ie. Consider˘am c˘a nivelul pe care este reprezentat˘a r˘ad˘acina arborelui este numerotat
cu 0. T este un arbore binar strict, cu 2n + 1 noduri (n interne s , i n + 1 externe), iar pe fiecare
i
2
nivel i ∈ {0, 1, . . . , h(T)} el are cel mult 2 noduri (induct , ie!), deci 2n+1 ≤ 1+2+2 +. . .+2 h(T) .
Obt , inem, succesiv: 2n + 1 ≤ 2 h(T)+1 − 1, 2 h(T) ≥ n + 1, h(T) ≥ log (n + 1). Cum h(T) ∈ N,
2
deducem c˘a h(T) ≥ dlog (n + 1)e .
2
∗
Observat ,ia 3. Pentru orice n ∈ N avem dlog (n + 1)e = 1 + blog nc .
2 2
ˆ ∗
Intr-adev˘ar, fie dlog (n + 1)e = k, k ∈ N . Avem, succesiv: k − 1 < log (n + 1) ≤ k,
2 2
k
k
2 k−1 < n+1 ≤ 2 , 2 k−1 ≤ n < 2 , k −1 ≤ log n < k. Deci blog nc = k −1 = dlog (n + 1)e−1.
2
2
2
Propozit , ia 5. Fie T un arbore binar strict cu n noduri interne, n ∈ N. Dac˘a toate nodurile
externe sunt situate pe ultimul s , i, eventual, pe penultimul nivel, atunci avem
h(T) = dlog (n + 1)e ,
2
X dlog (n+1)e
D T (v) = (n + 1) dlog (n + 1)e + n + 1 − 2 2 .
2
v∈E(T)