Page 46 - MATINF Nr. 1

46 C. B˘alc˘au

Obt , inem astfel urm˘atoarea variant˘a iterativ˘a a algoritmului:

CAUT-BIN(A, n, x) :
p ← 1; u ← n; // (a p , . . . , a u ) reprezint˘ a subvectorul curent
// la care s-a restrˆ ans c˘ autarea
while p ≤ u do
p + u
õ û
m ← ;
2
if x = a m then
return m; // c˘ autarea se ˆ ıncheie cu succes
else
if x < a m then
u ← m − 1;
else
p ← m + 1;

return −1; // c˘ autarea se ˆ ıncheie f˘ ar˘ a succes

Observat ,ia 4. Pentru evaluarea complexit˘at , ii algoritmilor care rezolv˘a problema considerat˘a,
vom analiza numai comparat , iile ˆın care intervin valoarea c˘autat˘a x s , i un element al vectorului
A, numite comparat ,ii de chei. Astfel consider˘am c˘a aceste comparat , ii se efectueaz˘a succesiv
(comparat , iile simultane pot fi separate).

Prezent˘am cˆateva not , iuni ajut˘atoare.

Definit , ia 9. Un arbore binar de c˘autare (BST - Binary Search Tree) este un arbore
binar cu proprietatea c˘a orice nod intern are valoarea (eticheta) mai mare decˆat orice nod din
subarborele s˘au stˆang si mai mic˘a decˆat orice nod din subarborele s˘au drept.

Observat ,ia 5. Fie A un algoritm de c˘autare, bazat pe comparat , ii de chei, ce rezolv˘a problema
considerat˘a. Presupunem c˘a algoritmul nu cont , ine instruct , iuni redundante s , i este aplicabil
pentru orice pozit , ionare posibil˘a a valorii x ˆın raport cu componentele vectorului A, deci valoarea
x este comparat˘a exact cˆate o dat˘a cu fiecare componemt˘a a i , i = 1, n.

Atunci algoritmului A i se poate asocia un arbore binar de c˘autare T (A) avˆand n noduri,
etichetate cu numerele 1, 2, . . . , n, construit recursiv astfel: dac˘a prima comparat , ie efectuat˘a de
algoritm este ˆıntre valoarea c˘autat˘a x s , i un element a i al vectorului, atunci:

• r˘ad˘acina arborelui este etichetat˘a cu indicele i;

• subarborele stˆang corespunde continu˘arii algoritmului ˆın cazul x < a i , dac˘a acest caz este
posibil dup˘a prima comparat , ie (altfel este vid, adic˘a nu exist˘a descendent stˆang);

• subarborele drept corespunde continu˘arii algoritmului ˆın cazul x > a i , dac˘a acest caz este
posibil dup˘a prima comparat , ie (altfel este vid, adic˘a nu exist˘a descendent drept).

Reciproc, oric˘arui arbore binar de c˘autare T avˆand n noduri, etichetate cu numerele
1, 2, . . . , n, ˆıi corespunde un algoritm de c˘autare A(T ) a valorii x ˆın vectorul sortat