Se numeste arbore de cautare un arbore binar cu
urmatoarele proprietati:
- toate nodurile din subarborele stang sunt "mai
mici" radacina (deci preced radacina);
- toate nodurile din subarborele drept sunt "mai
mari" decat radacina (succed radacinii);
- orice subarbore al arborelui de cautare este el
insusi un arbore de cautare.
Ultima proprietate ne indica faptul ca arborele de cautare este o structura
recursiva.
Un exemplu de arbore de cautare este dat in figura 1. In acest caz, informatiile din noduri sunt numere intregi, iar criteriul de ordonare este cel al ordinii naturale a numerelor.
- Figura 1 -
Exemplul 1: daca in arborele din figura 1 se cauta
valoarea 48, se procedeaza astfel:
- se porneste de la radacina arborelui;
- se constata ca 48<50, deci se continua cautarea
in subarborele stang;
- se constata ca 48>27, deci se continua cautarea
in subarborele drept;
- se constata ca 48>38, deci se continua cautarea
in subarborele drept;
- se constata ca 48=48, deci cautarea s-a incheiat
cu succes.
Exemplul 2: daca in arborele din figura 1 se cauta valoarea
57, se procedeaza astfel:
- se porneste de la radacina arborelui;
- se constata ca 57>50, deci se continua cautarea
in subarborele drept;
- se constata ca 57<65, deci se continua cautarea
in subarborele stang;
- se constata ca 57<61, dar cautarea se incheie
cu esec, deoarece nu exista subarbore stang.
Exemplu: In arborele de cautare din figura 1,
elementul minim se gaseste parcurgand calea 50, 27, 15, iar elementul maxim
se gaseste parcurgand calea 50, 65, 72.
Exemplu: Consideram ca dorim sa punem in arborele de cautare
din figura 1 un nod care contine valoarea 57. Operatia decurge astfel:
- etapa 1 - se cauta nodul cu valoarea 57, parcurgand
calea 50, 65, 61; intrucat 57<61, noul nod ar trebui sa fie cautat in
subarborele stang al nodului 61, dar acest nod nu are fiu stanga;
- etapa 2 - se creeaza un nod care contine valoarea
57 si se pune ca fiu stanga al nodului 61. Se obtine astfel arborele din
figura 2.
- Figura 2 -
Clasa ArboreCautareIn fisierul ArboreCautare.java este definita clasa ArboreCautare.
Testarea existentei obiectului de informatie val atasat unui
nod oarecare al arborelui se face prin metoda
Convertirea arborelui intr-un sir, in formatul cu paranteze, se face
prim metoda
Testarea acestor metode se face in programul din fisierul TestArbCautare.java. |
- Figura 3 -
Se constata, deci, ca folosirea arborilor de cautare de tipul celor discutati aici este convenabila numai daca punerea nodurilor in arbore se face intr-o ordine aleatoare a valorilor. Aceasta deficienta poate fi evitata prin utilizarea arborilor de cautare echilibrati, care este discutata in sectiunea urmatoare.