Arbori de cautare

Fie un arbore binar, in care informatiile din noduri sunt comparabile, adica pot fi ordonate dupa un anumit criteriu. Vom spune ca nodul A precede nodul B daca, dupa criteriul adoptat, informatia din A o precede pe cea din B.

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 -


Cautarea unui nod in arborele de cautare

Pentru a cauta o anumita valoare V in arbore ne folosim de proprietatile acestuia:
    - daca valoarea cautata V coincide cu cea din radacina, inseamna ca V exista in arbore;
    - altfel, daca valoarea cautata V este mai mica decat cea din radacina, cautam in subarborele din stanga;
    - altfel, cautam in subarborele din dreapta.
Cautarea se incheie cu succes in momentul in care s-a gasit valoarea cautata, sau se incheie cu esec in momentul in care se constata ca nodul curent nu mai are subarbore in partea in care ar trebui continuata cautarea.

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.
 

Cautarea valorii minime sau maxime

Nodul arborelui de cautare, care contine elementul (obiectul de informatie) de valoare minima, se gaseste pornind de la radacina si urmand numai calea spre fiul stanga, pana cand se ajunge la un nod care nu mai are fiu stanga. In mod corespunzator, pentru nodul de valoare maxima, se porneste de la radacina urmand consecvent calea spre fiul dreapta, pana se ajunge la un nod care nu mai are fiu dreapta.

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.
 

Punerea unui nod in arborele de cautare

Punerea unui nou nod in arborele de cautare se face astfel:
    - se cauta locul in care ar trebui sa se gaseasca nodul respectiv, la fel ca in cazul cand se cauta o valoare existenta;
    - daca exista deja un nod care contine valoarea respectiva, operatia se incheie fara a adauga un nou nod;
    - daca nu se gaseste in arbore un astfel de nod, se adauga noul nod ca fiu (stanga sau dreapta, dupa caz) al nodului la care s-a incheiat operatia de cautare.

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 ArboreCautare

In fisierul ArboreCautare.java este definita clasa ArboreCautare.
 
public class ArboreCautare {
  Nod radacina;
  
  /* Constructori si metode */
  public ArboreCautare() {
    radacina=null;
  }

  /* Se testeaza existenta in arbore a valorii val */
  private static boolean exista(Object val, Nod nod) {
    if(nod==null) return false;
    int rez=((Comparable)val).compareTo(nod.info);
    if(rez==0) return true;
    if(rez<0) return exista(val, nod.fiuStanga);
    return exista(val, nod.fiuDreapta);
  }

  public boolean exista(Object val) {
    return exista(val, radacina);
  }

  /* Se intoarce nodul in care se gaseste valoarea val */
  private Nod cauta(Object val, Nod nod) {
    if(nod==null) return null;
    int rez=((Comparable)val).compareTo(nod.info);
    if(rez==0) return nod;
    if(rez<0) return cauta(val, nod.fiuStanga);
    return cauta(val, nod.fiuDreapta);
  }

  public Nod cauta(Object val) {
    return cauta(val, radacina);
  }

  /* Se pune un nou nod care contine valoarea val */
  private boolean pune(Object val, Nod nod) {
    int i=((Comparable)val).compareTo(nod.info);
    if(i==0) return false; // val deja exista, nu se mai pune
    if(i<0) {
      if(nod.fiuStanga==null) {
        nod.fiuStanga=new Nod(val);
        return true;
      }
      else return pune(val, nod.fiuStanga);
    }
    else if(nod.fiuDreapta==null) {
           nod.fiuDreapta=new Nod(val);
           return true;
         }
    return pune(val, nod.fiuDreapta);
  }

  public boolean pune(Object val) {
    if(radacina==null) {
      radacina=new Nod(val);
      return true;
    }
    return pune(val, radacina);
  }

  private Nod minim(Nod nod) {
    if(nod.fiuStanga==null) return nod;
    return minim(nod.fiuStanga);
  }

  public Object minim() {
    if(radacina==null) return null;
    return minim(radacina).info;
  }

  private Nod maxim(Nod nod) {
    if(nod.fiuDreapta==null) return nod;
    return maxim(nod.fiuDreapta);
  }

  public Object maxim() {
    if(radacina==null) return null;
    return maxim(radacina).info;
  }
 

  /* Metoda auxiliara recursiva care converteste un subarbore intr-un
     sir, in care arborele este pus in formatul cu paranteze
  */
  private StringBuffer toStringBuffer(StringBuffer sb, Nod nod) {
    sb.append("("+nod.info);
    if(nod.fiuStanga!=null) toStringBuffer(sb, nod.fiuStanga);
    else if(nod.fiuDreapta!=null) sb.append("(()");
    if(nod.fiuDreapta!=null) toStringBuffer(sb, nod.fiuDreapta);
    else if(nod.fiuStanga!=null) sb.append("()");
    sb.append(")");
    return sb;
  }

  /* Redefinirea metodei toString din clasa Object. Foloseste metoda
     auxiliara toStringBuffer() aplicata radacinii arborelui
  */
  public String toString() {
    StringBuffer sb=new StringBuffer();
    if(radacina==null) return "( )";
    return toStringBuffer(sb, radacina).toString();
  }

    
    
  /* CLASE INTERIOARE */
  /* Nod al arborelui de cautare */
  class Nod {
    Object info;
    Nod fiuStanga, fiuDreapta;

    Nod(Object obj) {
      info=obj;
      fiuStanga=fiuDreapta=null;
    }

    public String toString() {
      return "["+info+"]";
    }
  }
}

Testarea existentei obiectului de informatie val atasat unui nod oarecare al arborelui se face prin metoda 
       public boolean exista(Object val)
care, la randul ei, invoca metoda privata recursiva care cauta val in subarborele cu radacina nod
   private static boolean exista(Object val, Nod nod)
Pentru a obtine o referinta la nodul care contine informatia val, se foloseste metoda publica
   public Nod cauta(Object val)
care invoca metoda privata recursiva care cauta val in subarborele cu radacina nod
   private static Nod cauta(Object val, Nod nod)
Pentru a pune in arborele binar un nou nod, care contine obiectul de informatie val, se foloseste metoda publica
   public boolean pune(Object val)
care invoca metoda privata recursiva care pune un nou nod in subarborele cu radacina nod
   private boolean pune(Object val, Nod nod)
Pentru a determina valoarea minima continuta in arborele de cautare se foloseste metoda publica
   public Object minim()
care invoca metoda privata recursiva care cauta minimul in subarborele cu radacina nod
   private Nod minim(Nod nod)
Pentru a determina valoarea maxima continuta in arborele de cautare se foloseste metoda publica
   public Object maxim()
care invoca metoda privata recursiva care cauta maximul in subarborele cu radacina nod
   private Nod maxim(Nod nod)

Convertirea arborelui intr-un sir, in formatul cu paranteze, se face prim metoda 
   public String toString()
prin care este redefinita metoda toString() din clasa Object si care invoca metoda privata recursiva
   private StringBuffer toStringBuffer(StringBuffer sb, Nod nod)

Testarea acestor metode se face in programul din fisierul TestArbCautare.java.

Eliminarea unui nod din arborele de cautare

Eliminarea unui nod frunza a arborelui de cautare este foarte simpla: se cauta nodul respectiv si se elimina legatura catre acesta din nodul-tata. Daca insa se doreste eliminarea unui nod care este radacina a arborelui sau a unui subarbore se procedeaza astfel: se elimina numai informatia din nod si se inlocuieste cu cea din fiul minim al subarborelui din dreapta sau cu cea din fiul maxim al subarborelui din stanga. Daca acest nod, din care s-a extras informatia, este o frunza, nodul se elimina. Daca insa este tot un nod intermediar (radacina a unui subarbore), se repeta operatia descrisa mai sus, continuandu-se astfel pana se ajunge la o frunza.

Complexitatea operatiilor cu arbori de cautare

Se observa ca, atat la cautarea unui nod existent, cat si la punerea unui nod nou numarul maxim de pasi de cautare este egal cu inaltimea arborelui. In cazul cel mai favorabil, cand arborele este (aproape) complet, sau cand numarul de noduri lipsa este relativ mic, complexitatea este O(log n). Totusi, in cazul cel mai defavorabil, cand toate nodurile arborelui au numai fiu stang sau numai fiu drept, complexitatea este O(n), deoarece arborele a degenerat practic, in acest caz, intr-o lista inlantuita. O astfel de situatie poate sa apara daca punerea nodurilor in arbore se face in ordinea strict crescatoare (descrescatoare) a valorii lor. De exemplu, daca nodurile in arbore se pun in ordinea 3, 7, 15, 23, se obtine arborele din figura 3, care a degenerat, practic, intr-o lista inlantuita, intrucat fiecare nou nod a fost atasat ca fiu dreapta al nodului precedent.


- 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.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunarea de Jos" din Galati