Page 49 - MATINF Nr. 1

Optimalitatea algoritmului de c˘autare binar˘a 49

Demonstrat¸ie. 1) Analiz˘am cazul cel mai defavorabil. Conform Observat , iei 7, num˘arul de
comparat , ii de chei efectuate ˆın cazul cel mai defavorabil este egal cu ˆın˘alt , imea h a arborelui
binar extins de c˘autare asociat T = T (A). Arborele T este un arbore binar strict, cu n noduri
interne (s , i n + 1 noduri externe), deci conform Propozit , iei 4 rezult˘a c˘a h ≥ dlog (n + 1)e .
2
2) Analiz˘am acum cazul mediu (cazul timpului mediu de execut , ie). Conform Observat , iei 7,
num˘arul mediu de comparat , ii de chei are valoarea

(1 + D(k)) + D(k) n + D(k) + D(k)
P P P P
k∈I k∈E k∈I k∈E
N med (n) = = ,
2n + 1 2n + 1
unde I este mult , imea nodurilor interne, E este mult , imea nodurilor externe, iar, pentru fiecare
nod k, D(k) reprezint˘a distant , a de la r˘ad˘acina arborelui T = T (A) la nodul k. Conform
Propozit , iilor 3 s , i 6 rezult˘a c˘a

2 P D(k) − n Ä dlog (n+1)e ä
2
k∈E 2 (n + 1) dlog (n + 1)e + n + 1 − 2 2 − n
N med (n) = ≥ ,
2n + 1 2n + 1
adic˘a inegalitatea din enunt , .

Propozit , ia 7. Pentru algoritmul de c˘autare binar˘a ˆıntr-un vector sortat cu n componente, o
c˘autare cu succes necesit˘a cel mult h comparat ,ii de chei, iar o c˘autare f˘ar˘a succes necesit˘a h − 1
sau h comparat ,ii de chei, unde h = dlog (n + 1)e = blog nc + 1.
2
2
Demonstrat¸ie. Fie T (n) arbore binar de c˘autare asociat algoritmului de c˘autare binar˘a ˆın-
tr-un vector sortat cu n componente. Conform descrierii algoritmului de c˘autare binar˘a
s , i a construirii arborelui binar de c˘autare asociat, rezult˘a c˘a subarborele stˆang al lui T (n)
ö ù
corespunde c˘aut˘arii binare ˆın subvectorul (a 1 , . . . , a m−1 ), unde m = n+1 , deci este chiar
2
Äö ùä
T n−1 , iar subarborele drept corespunde c˘aut˘arii binare ˆın subvectorul (a m+1 , . . . , a n ) de
2
ö ù † £ Ć £ä
lungime n − m = n − n+1 = n−1 , deci are aceeas , i structur˘a cu T n−1 (doi arbori
2 2 2
binari au aceeas , i structur˘a dac˘a sunt identici, cu except , ia etichetelor, adic˘a prin suprapunerea
r˘ad˘acinilor ei se suprapun perfect). Aplicˆand metoda induct , iei matematice, rezult˘a c˘a arborele
binar T (n + 1) are aceeas , i structur˘a cu arborele binar T (n) plus un nod extern, situat pe
ultimul nivel (la pasul inductiv se analizeaz˘a separat cazurile n par, respectiv impar s , i se aplic˘a
† n−1 £ ö n−1 ù
ipoteza de induct , ie pentru cei doi subarbori). Cum = pentru n impar, respectiv
2 2
† £ ö ù
n−1 = n−1 +1 pentru n par, rezult˘a c˘a subarborele drept al lui T (n), avˆand aceeas , i structur˘a
2
Ć 2 £ä Äö ùä
cu T n−1 , are aceeas , i structur˘a cu subarborele stˆang T n−1 plus un eventual nod extern
2 2
(cˆand n este par). Aplicˆand din nou metoda induct , iei matematice, rezult˘a c˘a ˆın arborele binar
T (n) toate nodurile care nu au doi descendent , i (fii) sunt situate pe ultimul s , i, eventual, pe
penultimul nivel (la pasul inductiv se foloses , te relat , ia de structur˘a ment , ionat˘a dintre cei doi
subarbori s , i se aplic˘a ipoteza de induct , ie pentru subarborele drept).
Rezult˘a c˘a arborele binar extins de c˘autare asociat T (n) are nodurile externe situate pe
cel mult dou˘a nivele. Notˆand cu h ˆın˘alt , imea arborelui extins (adic˘a lungimea maxim˘a de la
r˘ad˘acin˘a la un nod extern) s , i considerˆand c˘a r˘ad˘acina arborelui este reprezentat˘a pe nivelul 0,
rezult˘a c˘a: arborele extins are h + 1 nivele, n noduri interne s , i n + 1 noduri externe; pe nivelele
0, 1, . . . , h − 2 avem doar noduri interne, fiecare avˆand cˆate doi descendent , i; pe penultimul nivel,
h − 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, avem doar noduri externe.