Arbori AVL

Definire:

Arborii binari de căutare echilibraţi AVL sunt arborii binari de căutare care au următoarele proprietăţi:

- pentru fiecare nod din arbore, înălţimea subarborelui stâng diferă de înălţimea subarborelui drept prin maxim un nod;

- fiecare subarbore este un arbore binar de căutare AVL.

Numele AVL este dat de numele inventatorilor lui: Adelson, Veliskii şi Landis.

Inserarea unui nod într-un arbore AVL se face în două etape. În prima etapă se realizează inserarea nodului ca la o inserare obişnuită într-un arbore binar de căutare, iar apoi, dacă este cazul se echilibrează arborele.

Echilibrarea dacă este cazul se face printr-o rotaţie. Sunt patru cazuri distincte de rotaţie. Rotaţiile pot fi simple sau duble.

Cele patru rotaţii sunt:

- Rotaţie stânga

- Rotaţie dreapta

- Rotaţie stânga-dreapta

- Rotaţie dreapta-stânga

Operatiile de cautare, insertie, stergere a unui nod cu cheia data în arbori echilibrati, se fac cu un efort de calcul de O(log n) unitati de timp, consecinta directa a teoremei demonstrate de Adelson, Velskii si Landis ce garanteaza ca un arbore echilibrat nu va fi niciodata cu mai mult de 45% mai înalt decât omologul sau perfect echilibrat, oricare ar fi numarul sau de noduri.

Operaţii pe arbori AVL:

- Tehnica inserţiei nodurilor în arbori echilibraţi AVL.

Dându-se un arbore cu radacina R si având subarborii stâng si drept notati cu S si D, de înăltimi hs si hd, la insertia unui nod în S se disting trei cazuri:

1. hs=hd, în urma insertiei, S si D devin de înaltimi inegale, verificând însa criteriul echilibrului;

2. hs<hd, în urma insertiei S si D devin de înaltimi egale, deci echilibrul se îmbunatateste;

3. hs>hd, criteriul echilibrului nu se mai verifica, arborele trebuie reechilibrat.

Cazurile posibile care pot duce la necesitatea reechilibrării se pot sintetiza în următoarele, ţinând cont de subarborele în care se face inserţia (subarborele stâng sau drept) si de locul in cadrul subarborelui.

Reechilibrarea la inserţia în arbori AVL - Caz 1 stânga:

Reechilibrarea la inserţia în arbori AVL - Caz 2 stânga-dreapta:

Reechilibrarea la inserţia în arbori AVL - Caz 1 dreapta:

Reechilibrarea la inserţia în arbori AVL - Caz 2 dreapta- stânga:

Un algoritm pentru insertie si reechilibrare depinde de maniera în care e memorata informatia referitoare la situatia echilibrului arborelui.

- Căutarea într-un arbore AVL.

Cãutarea într-un arbore AVL se face la fel ca într-un arbore binar de cãutare obisnuit, in plus adaugandu-se factorul de echilibru. Structura unui nod împreunã cu functia de inserare în nod este prezentatã mai jos:

/* avl-tree.h */

typedef unsigned char Balance;

typedef enum { Left, Right, Equal } Tree_balance;

typedef struct tag_AVL_Tree

{

Tree_balance balance;

int key;

struct tag_AVL_Tree *l, *r;

} AVL_Tree;

AVL_Tree *avl_tree_insert (AVL_Tree *t, int k);

/* avl-tree.c */

static int equilibration_required;

static AVL_Tree *equilibrate_left (AVL_Tree *a);

static AVL_Tree *equilibrate_right (AVL_Tree *a);

/*