Page 47 - MATINF Nr. 1

Optimalitatea algoritmului de c˘autare binar˘a 47

A = (a 1 , a 2 , . . . , a n ), descris recursiv astfel:

A(T ) :
î ó
if T este vid then
return −1; // c˘ autare f˘ ar˘ a succes
else
i ← eticheta r˘ad˘acinii lui T ;
if x = a i then
return i; // c˘ autare cu succes
else
if x < a i then
T s ← subarborele stˆang al lui T ;
return A(T s );
else
T d ← subarborele drept al lui T ;
return A(T d );

Corespondent , ele A → T (A) s , i T → A(T ) de mai sus sunt bine definite s , i inverse una
celeilalte, deci sunt biject , ii ˆıntre mult , imea algoritmilor de c˘autare (bazat , i pe comparat , ii de
chei) a unei valori x ˆıntr-un vector sortat cu n componente (a 1 , a 2 , . . . , a n ) s , i mult , imea arborilor
binari de c˘autare avˆand n noduri etichetate cu numerele 1, 2, . . . , n.

Definit , ia 10. Arbore binar de c˘autare T (A) construit ˆın observat ,ia anterioar˘a se numes , te s , i
arborele de decizie al algoritmului de c˘autare A.

Exemplul 2. Arborele binar de c˘autare asociat algoritmului c˘aut˘arii binare pentru n = 8 este
reprezentat ˆın figura urm˘atoare.

4

2 6

1 3 5 7
8

Observat ,ia 6. Arborele de c˘autare asociat algoritmului de c˘autare binar˘a este un arbore binar,
nu neap˘arat strict.

Definit , ia 11. Fie T un arbore binar de c˘autare avˆand n noduri, etichetate cu numerele
1, 2, . . . , n. Extindem arborele binar T la un arbore binar strict T astfel: pentru orice
k ∈ {1, 2, . . . , n}, nodul lui T avˆand eticheta k este reprezentat ˆıntr-un cerc s , i devine nod
intern ˆın T prin aplicarea urm˘atoarelor dou˘a reguli:

• dac˘a nodul nu are descendent stˆang, atunci i se adaug˘a un descendent stˆang etichetat cu
k − 1 s , i reprezentat ˆıntr-un p˘atrat;

• dac˘a nodul nu are descendent drept, atunci i se adaug˘a un descendent drept etichetat cu k
s , i reprezentat ˆıntr-un p˘atrat.