Arbori Binari

Definitie


     Un arbore binar este o multime de n >= 0 noduri, care daca nu este vida, contine un nod numit radacina, restul nodurilor formand doi arbori disjuncti numiti subarborele stang si subarborele drept.
     Aceasta structura de date e importanta pentru ca e usor de reprezentat si prelucrat, orice arbore putand fi transformat în arbore binar.




Tehnica transformarii unui arbore generalizat in arbore binar


     Un arbore generalizat poate fi transformat intr-un arbore binar, astfel incat secventele de noduri pentru parcurgerea in preordine sa fie identice in cazul ambilor arbori.
     Un arbore generalizat A cu radacina A1 si subarborii A1,1, A1,2, ...,A1,k se transforma in arbore binar avand radacina A1, A1,1 fiul sau stang, iar A1,i devin fii drepti ai lui A1,i-1 pentru 2<=i<=k.
     Secventele de noduri in parcurgerea in preordine a arborelui generalizat si a celui binar obtinut prin transformare, sunt identice.




Implementarea arborilor binari


     Un arbore binar poate fi creat cu ajutorul urmatoarei structuri:
 struct nod
  {
      int info;
      nod*st;
      nod*dr;
  };




Operatorii arborelui binar


 INITIALIZEAZA(A) - face vid arborele A;
 INSEREAZA(X,A) - insereaza cheia X în arborele A;
 CAUTA(X,A) - cauta cheia X, returnând true la gasire;
 SUPRIMA(X,A) - suprima cheia X, daca exista;
 TRAVERSEAZA(A) - parcurge toate cheile arborelui A




Traversarea arborilor binari


     Pentru un arbore binar, notand cu Rad radacina si cu St si cu Dr subarborele sau stang, respectiv drept, cele 3 posibilitati de traversare sunt:
 -preordine - lista Rad, St, Dr
 -inordine - lista St, Rad, Dr
 -postordine- lista St, Dr, Rad


Cele trei metode de traversare se concretizeaza in trei functii recursive.




Arbori binari ordonati. Arbori binari de înaltime minima


     Arborele binar ordonat e arborele binar cu proprietatea ca parcurgand nodurile in inordine, secventa cheilor este monoton crescatoare.
     Are proprietatea ca daca un nod oarecare al arborelui are cheia C, toate nodurile din subarborele stang al nodului au cheile mai mici decat valoarea C, respectiv toate cheile din subarborele drept au cheile mai mari sau egale cu C. De aici rezulta procedeul de cautare foarte simplu, prin trecerea la fiul stang sau drept de la nodul curent, in functie de relatia dintre cheia cautata si cea a nodului curent. 
     Cum inaltimea minima a unui arbore binar ordonat cu n noduri este hmin=[log2 (n+1)], rezulta ca o cautare intr-un arbore binar ordonat necesita aproximativ log2n comparatii de chei, fata de n/2 comparatii intr-o lista liniara.




Tehnica de creare a arborilor binari ordonati


     Procesul de creare consta in insertia cate unui nod intr-un arbore binar ordonat, care initial este vid, astfel incat dupa insertie el sa ramana ordonat. 
     Pentru aceasta se traverseaza arborele incepand cu radacina si se selecteaza fiul stang sau drept, dupa cum cheia de inserat e mai mica sau mai mare decat a nodului parcurs. Se repeta pana cand se ajunge la un pointer NULL care se inlocuieste cu pointerul spre noul nod creat.  Pentru ca sortarea sa fie stabila, se trece la fiul drept chiar daca valoarea cheii e egala.