Arbori

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 stâng si subarborele drept.

Un arbore binar poate fi descris cu ajutorul urmatoarei structuri de date dinamice:

			typedef int TCheie; 

			class TNodAB {  
			   public:  
				  TCheie cheie;  
				  TNodAB *stg,*dr;  
				  TNodAB(TCheie k) {  
					   cheie=k;  
					   stg=dr=NULL;  
				   }  
			};
		

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, notând cu R radacina si cu A si cu B subarborele sau stâng, respectiv drept, cele 3 posibilitati de traversare sunt:

  • preordine - lista R, A, B
  • inordine - lista A, R, B
  • postordine- lista A, B, R.

Cele trei metode de traversare se concretizeaza în trei functii recursive în care Prelucrare este operatia ce trebuie facuta asupra fiecarui nod.

Arbori binari ordonati. Arbori binari de înaltime minima

Arborele binar ordonat e arborele binar cu proprietatea ca parcurgând nodurile în inordine, secventa cheilor este monoton crescatoare.

Are proprietatea ca daca un nod oarecare al arborelui are cheia c, toate nodurile din subarborele stâng al nodului au cheile mai mici decât 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 stâng sau drept de la nodul curent, functie de relatia dintre cheia cautata si cea a nodului curent.

Cum înaltimea minima a unui arbore binar ordonat cu n noduri este hmin=[log2 (n+1)], rezulta ca o cautare într-un arbore binar ordonat necesita aproximativ log2n comparatii de chei, fata de n/2 comparatii într-o lista liniara.

Tehnica de creare a arborilor binari ordonati

Procesul de creare consta în insertia câte unui nod într-un arbore binar ordonat, care initial este vid, astfel încât dupa insertie el sa ramâna ordonat.

Pentru aceasta se traverseaza arborele începând cu radacina si se selecteaza fiul stâng sau drept, dupa cum cheia de inserat e mai mica sau mai mare decât a nodului parcurs. Se repeta pâna când se ajunge la un pointer nil 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.

Arbori binari de cautare echilibrati (AVL)

Una dintre principalele aplicatii ale arborilor binari, o reprezinta AVL-urile. AVL-urile sunt arbori de cautare echilibrati care au complexitate O(log N) pe operatiile de inserare, stergere si cautare. Pentru mai multe detalii, puteti consulta bibliografia. In continuare, prezentam o implementare scurta si eficienta a operatiilor unui AVL:

	#define max(a, b) ((a) > (b) ? (a) : (b))
#define geth(n) (n->h = 1 + max(n->l->h, n->r->h))

struct node
{
      int key, h;
      struct node *l, *r;
} *R, *NIL;
typedef struct node node;

void init(void)
{
      R = NIL = (node *) malloc(sizeof(node));
      NIL->key = NIL->h = 0,
              NIL->l = NIL->r = NULL;
}

node* rotleft(node *n)
{
      node *t = n->l;

      n->l = t->r, t->r = n,
              geth(n), geth(t);
      return t;
}

node* rotright(node *n)
{
      node *t = n->r;
 
      n->r = t->l, t->l = n,
              geth(n), geth(t);
      return t;
}

node* balance(node *n)
{
      geth(n);
      if (n->l->h > n->r->h + 1)
      {
              if (n->l->r->h > n->l->l->h)
                      n->l = rotright(n->l);
              n = rotleft(n);
      }
      else
              if (n->r->h > n->l->h + 1)
              {
                      if (n->r->l->h > n->r->r->h)
                              n->r = rotleft(n->r);
                      n = rotright(n);
              }
      return n;
}

node* insert(node *n, int key)
{
      if (n == NIL)
      {
              n = (node *) malloc(sizeof(node));
              n->key = key, n->h = 1, n->l = n->r = NIL;
              return n;
      }
      if (key < n->key)
              n->l = insert(n->l, key);
      else
              n->r = insert(n->r, key);
      return balance(n);
}

node* erase(node *n, int key)
{
      node *t;
      if (n == NIL) return n;
      if (n->key == key)
      {
              if (n->l == NIL || n->r == NIL)
              {
                      t = n->l == NIL ? n->r : n->l;
                      free(n); return t;
              }
              else
              {
                      for (t = n->r; t->l != NIL; t = t->l);
                      n->key = t->key,
                              n->r = erase(n->r, t->key);
                      return balance(n);
              }
      }
      if (key < n->key)
              n->l = erase(n->l, key);
      else
              n->r = erase(n->r, key);
      return balance(n);
}

int search(node *n, int key)
{
      if (n == NIL) return 0;
      if (n->key == key) return 1;
      if (key < n->key)
              return search(n->l, key);
      else
              return search(n->r, key);
}

	
D
E
S
I
G
N
E
R

Florian Marcu

Personal information:
Education:
Work experience:
- Summer 2011 : Software Engineer Intern at Adobe Systems Inc. Bucharest
Projects:
Skills:
Awards: