Se numește arbore de căutare un arbore binar cu
următoarele proprietăți:
- toate nodurile din subarborele stâng sunt "mai mici" decât
rădăcina (deci preced rădăcina);
- toate nodurile din subarborele drept sunt "mai mari" decât
rădăcina (succed rădăcinii);
- orice subarbore al arborelui de căutare este el însuși un arbore
de căutare.
Ultima proprietate ne indică faptul că arborele de căutare este o structură
recursivă.
Un exemplu de arbore de căutare este dat în figura 1. În acest caz, informațiile din noduri sunt numere întregi, iar criteriul de ordonare este cel al ordinii naturale a numerelor.
- Figura 1 -
Exemplul 1: dacă în arborele din figura 1 se
caută valoarea 48, se procedează astfel:
- se pornește de la rădăcina arborelui;
- se constată că 48<50, deci se continuă căutarea în subarborele
stâng;
- se constată că 48>27, deci se continuă căutarea în subarborele
drept;
- se constată că 48>38, deci se continuă căutarea în subarborele
drept;
- se constată că 48=48, deci căutarea s-a încheiat cu succes.
Exemplul 2: dacă în arborele din figura 1 se caută
valoarea 57, se procedează astfel:
- se pornește de la rădăcina arborelui;
- se constată că 57>50, deci se continuă căutarea în subarborele
drept;
- se constată că 57<65, deci se continuă căutarea în subarborele
stâng;
- se constată că 57<61, dar căutarea se încheie cu eșec,
deoarece nu există subarbore stâng.
Exemplu: În arborele de căutare din figura 1,
elementul minim se găsește parcurgând calea 50, 27, 15, iar elementul
maxim se găsește parcurgând calea 50, 65, 72.
Exemplu: Considerăm ca dorim să punem în arborele de
căutare din figura 1 un nod care conține valoarea 57. Operația
decurge astfel:
- etapa 1 - se caută nodul cu valoarea 57, parcurgând calea 50, 65,
61; întrucât 57<61, noul nod ar trebui să fie căutat în subarborele
stâng al nodului 61, dar acest nod nu are fiu stânga;
- etapa 2 - se creează un nod care conține valoarea 57 și se pune
ca fiu stânga al nodului 61. Se obține astfel arborele din figura 2.
- Figura 2 -
Clasa ArboreCautareIn fișierul ArboreCautare.java este definită clasa ArboreCautare.
Testarea existenței obiectului de informație val
atașat unui nod oarecare al arborelui se face prin metoda Convertirea arborelui într-un șir, în formatul cu paranteze,
se face prim metoda Testarea acestor metode se face în programul din fișierul TestArbCautare.java. |
- Figura 3 -
Se constată, deci, că folosirea arborilor de căutare de tipul celor prezentați aici este convenabilă numai dacă punerea nodurilor în arbore se face într-o ordine aleatoare a valorilor. Această deficiență poate fi evitată prin utilizarea arborilor de căutare echilibrați, care este discutată în secțiunea următoare.