Page 45 - MATINF Nr. 1

Optimalitatea algoritmului de c˘autare binar˘a 45

Demonstrat¸ie. Fie M = {T | T = arbore binar strict, card(I(T)) = n} s , i S(T) = P D T (v),
v∈E(T)
∗
∗
∀ T ∈ M. Fie T ∈ M, T = (V, F), astfel ˆıncˆat
∗
S(T ) = min{S(T) | T ∈ M}.
Consider˘am din nou c˘a nivelul pe care este reprezentat˘a r˘ad˘acina arborelui este numerotat cu 0.
∗
∗
Demonstr˘am c˘a arborele T nu are noduri externe pe nivelele 0,1, . . ., h(T ) − 2 prin reducere la
∗
∗
absurd. S˘a presupunem c˘a arborele T ar avea un nod extern x pe un nivel i, cu i ≤ h(T ) − 2.
∗
∗
Fie y un nod intern al lui T situat pe penultimul nivel, nivelul h(T ) − 1, s , i fie y 1 s , i y 2 cei doi
∗
descendent , i ai lui y, deci y 1 s , i y 2 sunt noduri externe situate pe ultimul nivel, nivelul h(T ).
∗ ∗
Evident, D T ∗(x) = i, D T ∗(y) = h(T ) − 1, D T ∗(y 1 ) = D T ∗(y 2 ) = h(T ).
0
∗
Fie T arborele obt , inut din T prin mutarea nodurilor y 1 s , i y 2 de la descendent , i ai nodului y
la descendent , i ai nodului x, adic˘a
0
T = (V, F \ {[y, y 1 ], [y, y 2 ]} ∪ {[x, y 1 ], [x, y 2 ]}).
0
∗
Evident, T 0 r˘amˆane un arbore binar strict, T 0 ∈ M, E(T ) = E(T ) \ {x} ∪ {y},
∗
0
0
∗(v), ∀ v ∈ E(T ) \ {y 1 , y 2 }. Avem S(T ) − S(T ) =
D T 0(y 1 ) = D T 0(y 2 ) = i + 1, D T 0(v) = D T
P 0(v) − P
D T D T ∗(v) = D T 0(y) + D T 0(y 1 ) + D T 0(y 2 ) − D T ∗(x) − D T ∗(y 1 ) − D T ∗(y 2 ) =
∗
0
v∈E(T ) v∈E(T )
∗
∗
∗
0
∗
h(T ) − 1 + 2(i + 1) − i − 2h(T ) = i + 1 − h(T ) < 0, deci S(T ) < S(T ), ceea ce contrazice
∗
alegerea lui T . Demonstrat , ia prin reducere la absurd este ˆıncheiat˘a.
∗
∗
Deoarece arborele T nu are noduri externe pe nivelele 0,1, . . ., h(T ) − 2, rezult˘a c˘a
toate nodurile sale externe sunt situate pe ultimul s , i, eventual, pe penultimul nivel. Aplicˆand
Propozit , ia 5 rezult˘a c˘a
∗
min{S(T) | T ∈ M} = s(T ) = (n + 1) dlog (n + 1)e + n + 1 − 2 dlog (n+1)e ,
2
2
de unde rezult˘a inegalitatea din enunt , . Mai mult, dac˘a toate nodurile externe sunt situate pe
ultimul s , i, eventual, pe penultimul nivel atunci, conform Propozit , iei 5, inegalitatea din enunt ,
devine egalitate, iar ˆın caz contrar, conform demonstrat , iei prin reducere la absurd de mai sus,
inegalitatea este strict˘a.
C˘autarea binar˘a
Consider˘am problema c˘aut˘arii unei valori date x printre elementele unui vector sortat cresc˘ator
∗
dat A = (a 1 , a 2 , . . . , a n ), a 1 ≤ a 2 ≤ . . . ≤ a n , n ∈ N .
Algoritmul de c˘autare binar˘a rezolv˘a aceast˘a problem˘a prin urm˘atoarea strategie de tip
Divide et Impera:

ö n+1 ù
• Se compar˘a x cu elementul median a m , unde m = ;
2
• Avem trei variante posibile:
– Dac˘a x = a m , atunci c˘autarea se ˆıncheie cu succes;

– Dac˘a x < a m , atunci algoritmul continu˘a cu c˘autarea lui xˆın subvectorul (a 1 , . . . , a m−1 );
– Dac˘a x > a m , atunci algoritmul continu˘a cu c˘autarea lui xˆın subvectorul (a m+1 , . . . , a n ).