Page 48 - MATINF Nr. 1

48 C. B˘alc˘au

Arborele T se numes , te arbore binar extins de c˘autare.

Exemplul 3. Arborele binar extins 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

0 1 2 3 4 5 6 8

7 8

Observat ,ia 7. Pentru orice algoritm de c˘autare A a valorii xˆın vectorul sortat A = (a 1 , a 2 , . . . , a n ),
arborele binar extins de c˘autare asociat T = T (A) este un arbore binar strict ce are n noduri
interne, etichetate cu numerele 1, 2, . . . , n reprezentate ˆın cercuri s , i n + 1 noduri externe,
etichetate cu numerele 0, 1, 2, . . . , n reprezentate ˆın p˘atrate, avˆand semnificat , ia urm˘atoare:

• pentru orice i ∈ {1, 2, . . . , n}, nodul intern etichetat cu i reprezint˘a comparat , ia valorii
c˘autate, x, cu elementul a i din vectorul sortat;

• pentru orice i ∈ {0, 1, 2, . . . , n}, nodul extern etichetat cu i reprezint˘a ˆıncheierea f˘ar˘a
succes a c˘aut˘arii, corespunz˘atoare situat , iei:

x < a 1 , dac˘a i = 0,
a i < x < a i+1 , dac˘a 1 ≤ i ≤ n − 1,
x > a n , dac˘a i = n.

De asemenea, avem:

• la o c˘autare cu succes, x = a i , num˘arul de comparat , ii de chei este egal cu num˘arul de
noduri (interne) situate pe lant , ul elementar dintre nodul r˘ad˘acin˘a s , i nodul intern i, adic˘a
este mai mare cu 1 decˆat lungimea acestui lant , ;

• la o c˘autare f˘ar˘a succes num˘arul de comparat , ii de chei este egal cu num˘arul de noduri
interne situate pe lant , ul elementar dintre nodul r˘ad˘acin˘a s , i nodul extern corespunz˘ator
ˆıncheierii f˘ar˘a succes a c˘aut˘arii, adic˘a cu lungimea acestui lant , .

Teorema 2 (complexitatea algoritmilor de c˘autare). Pentru orice algoritm de c˘autare A,
bazat pe comparat ,ii de chei, a valorii x ˆın vectorul sortat A = (a 1 , a 2 , . . . , a n ) avem:

1) num˘arul de comparat ,ii de chei efectuate ˆın cazul cel mai defavorabil este mai mare sau
egal cu dlog (n + 1)e ;
2
2) num˘arul mediu de comparat ,ii de chei efectuate este mai mare sau egal cu

2n + 2 n + 2 − 2 · 2 dlog (n+1)e
2
· dlog (n + 1)e + .
2n + 1 2 2n + 1