Arbori de căutare

Fie un arbore binar, în care informațiile din noduri sunt comparabile, adică pot fi ordonate după un anumit criteriu. Vom spune că nodul A precede nodul B dacă, după criteriul adoptat, informația din A o precede pe cea din B.

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 -


Căutarea unui nod în arborele de căutare

Pentru a căuta o anumită valoare V în arbore ne folosim de proprietățile acestuia:
    - dacă valoarea căutată V coincide cu cea din rădacină, înseamnă că V există în arbore;
    - altfel, dacă valoarea căutată V este mai mică decât cea din rădacină, căutăm în subarborele din stânga;
    - altfel, cautăm în subarborele din dreapta.
Căutarea se încheie cu succes în momentul în care s-a găsit valoarea căutată, sau se încheie cu eșec în momentul în care se constată ca nodul curent nu mai are subarbore în partea în care ar trebui continuată căutarea.

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.
 

Căutarea valorii minime sau maxime

Nodul arborelui de căutare, care conține elementul (obiectul de informație) de valoare minimă, se găsește pornind de la rădacină și urmând numai calea spre fiul stânga, pâna când se ajunge la un nod care nu mai are fiu stânga. În mod similar, pentru nodul de valoare maximă, se pornește de la rădăcină urmând consecvent calea spre fiul dreapta, pâna se ajunge la un nod care nu mai are fiu dreapta.

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.
 

Punerea unui nod în arborele de căutare

Punerea unui nou nod în arborele de căutare se face astfel:
    - se caută locul în care ar trebui să se găsească nodul respectiv, la fel ca în cazul când se caută o valoare existentă;
    - dacă există deja un nod care conține valoarea respectivă, operația se incheie fară a adăuga un nou nod;
    - dacă nu se găsește în arbore un astfel de nod, se adaugă noul nod ca fiu (stânga sau dreapta, după caz) al nodului la care s-a încheiat operația de căutare.

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 ArboreCautare

In fișierul ArboreCautare.java este definită 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 existenței obiectului de informație val atașat unui nod oarecare al arborelui se face prin metoda 
       public boolean exista(Object val)
care, la rândul ei, invocă metoda privată recursivă care caută val în subarborele cu rădăcina nod
   private static boolean exista(Object val, Nod nod)
Pentru a obține o referință la nodul care conține informația val, se folosește metoda publică
   public Nod cauta(Object val)
care invocă metoda privată recursivă care caută val în subarborele cu rădăcina nod
   private static Nod cauta(Object val, Nod nod)
Pentru a pune în arborele binar un nou nod, care conține obiectul de informație val, se folosește metoda publică
   public boolean pune(Object val)
care invocă metoda privată recursivă care pune un nou nod în subarborele cu rădăcina nod
   private boolean pune(Object val, Nod nod)
Pentru a determina valoarea minimă conținută în arborele de căutare se folosește metoda publică
   public Object minim()
care invocă metoda privată recursivă care caută minimul în subarborele cu rădăcina nod
   private Nod minim(Nod nod)
Pentru a determina valoarea maximă conținută în arborele de căutare se folosește metoda publică
   public Object maxim()
care invocă metoda privată recursivă care caută maximul în subarborele cu rădăcina nod
   private Nod maxim(Nod nod)

Convertirea arborelui într-un șir, în formatul cu paranteze, se face prim metoda 
   public String toString()
prin care este redefinită metoda toString() din clasa Object,  care invocă metoda privată recursivă
   private StringBuffer toStringBuffer(StringBuffer sb, Nod nod)

Testarea acestor metode se face în programul din fișierul TestArbCautare.java.

Eliminarea unui nod din arborele de căutare

Eliminarea unui nod frunză al arborelui de căutare este foarte simplă: se caută nodul respectiv și se elimină legatura către acesta din nodul-tată. Dacă însă se dorește eliminarea unui nod care este rădacină a arborelui sau a unui subarbore, se procedează astfel: se elimină numai informația din nodul care trebuie eliminat și se înlocuiește cu cea din fiul minim al subarborelui din dreapta sau cu cea din fiul maxim al subarborelui din stânga. Dacă acest nod, din care s-a extras informația, este o frunză, nodul se elimină. Dacă însă este tot un nod intermediar (rădăcină a unui subarbore), se repetă operația de propagare descrisă mai sus, continuându-se astfel până se ajunge la o frunză.

Complexitatea operațiilor cu arbori de căutare

Se observă că, atât la căutarea unui nod existent, cât și la punerea unui nod nou, numărul maxim de pași de căutare este egal cu înalțimea arborelui. În cazul cel mai favorabil, când arborele este (aproape) complet, sau când numărul de noduri lipsă este relativ mic, complexitatea este O(log n). Totusi, în cazul cel mai defavorabil, când toate nodurile arborelui au numai fiu stâng sau numai fiu drept, complexitatea este O(n), deoarece arborele a degenerat practic, în acest caz, într-o listă înlănțuită. O astfel de situație poate să apară, dacă punerea nodurilor în arborele de căutare se face în ordinea strict crescătoare (descrescătoare) a valorilor lor. De exemplu, dacă nodurile în arbore se pun în ordinea 3, 7, 15, 23, se obține arborele din figura 3, care a degenerat, practic, într-o listă înlănțuită, întrucât fiecare nou nod a fost atașat ca fiu dreapta al nodului precedent.


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



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați