Lucrarea nr.3

ARBORI BINARI ECHILIBRATI AVL

1. Definitie

Arborele perfect echilibrat e cel in care, pentru fiecare nod, numarul de noduri ale subarborelui stang difera de cel pentru subarborele drept cu cel mult o unitate.

Procedura de inserare care restaureaza structura de arbore, astfel incat aceasta sa fie tot timpul echilibrata, nu e viabila, activitatea de restructurare fiind foarte complexa. Se accepta unele criterii de echilibrare imperfecta care conduc la tehnici mai simple de reorganizare.

O astfel de definiție a echilibrarii este cea propusa de Adelson-Velskii și Landis in 1962, arborii ce satisfac criteriul numindu-se arbori AVL.

Un arbore este echilibrat AVL daca si numai daca, pentru fiecare nod din arbore , inaltimile celor doi subarbori ai sai difera cu cel mult 1.

Definitia e foarte simpla si conduce la o procedura viabila de reechilibrare si la o lungime medie a drumului de cautare practic egala cu cea a unui arbore perfect echilibrat.

Operatiile de cautare, insertie, stergere a unui nod cu cheia data in 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 inalt decat omologul sau perfect echilibrat, oricare ar fi numarul sau de noduri.

Daca he(n) e inaltimea unui arbore echilibrat cu n noduri, atunci:

log(n+1)<=he(n)<=1.4404•log(n+2)-0.328,

optimul fiind atins de arbori perfect echilibrati cu n=2k-1.

2. Arbori Fibonacci

Pentru a gasi inaltimea maxima h a tuturor arborilor echilibrati cu n noduri, se considera o anumita inaltime h si se incearca construirea arborelui echilibrat cu numar minim de noduri.

Se definesc astfel:

1. arborele vid e arborele Fibonacci de inaltime 0;
2. arborele cu un singur nod e arborele Fibonacci de inaltime 1;
3. daca Ah-1 si Ah-2 sunt arbori Fibonacci de inaltime h-1 si h-2, atunci Ah = este un arbore Fibonacci de inaltime h;
4. nici un alt arbore nu e arbore Fibonacci.

Numarul de noduri ale lui Ah e definit de urmatoarea relatie simpla de recurenta: N0=0, N1=1, Nh=Nh-1 + 1 + Nh-2.

3. Tehnica insertiei nodurilor in arbori echilibrati AVL

Dandu-se un arbore cu radacina R si avand subarborii stang si drept notati cu S si D, de inaltimi hs si hd, la insertia unui nod in S se disting trei cazuri:

1. hs=hd - in urma insertiei, S si D devin de inaltimi inegale, verificand insa criteriul echilibrului;

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

Cazurile posibile care pot duce la necesitatea reechilibrarii se pot sintetiza in urmatoarele, tinand cont de subarborele in care se face insertia (subarborele stang sau drept) si de locul in cadrul subarborelui.

Reechilibrarea la insertia in arbori AVL - Caz 1 stanga:

Reechilibrarea la insertia in arbori AVL - Caz 2 stanga:

Reechilibrarea la insertia in arbori AVL - Caz 1 dreapta:

Reechilibrarea la insertia in arbori AVL - Caz 2 dreapta:

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

O solutie e cea in care aceasta informatie nu e inclusa in structura arborelui, atunci insa, factorul de echilibrare al unui nod afectat de insertie, trebuind sa fie determinat de fiecare data, ducand la marirea regiei. Alta solutie e cea in care se atribuie fiecarui nod, un factor explicit de echilibrare:

	type nod = record
                  cheie : integer;
		  stang,drept : ref;
		  ech : -1..1  {diferenta dintre inaltimile subarborelui stang si drept}
	         end;

Cu solutia a doua, insertia unui nod presupune etapele:

1. parcurgerea arborelui binar pentru determinarea locului de insertie sau a existentei deja a cheii de inserat;
2. insertia noului nod si determinarea factorului de echilibrare corespunzator;
3. revenirea pe drumul de cautare si verificarea factorului de echilibru pentru fiecare nod - presupune unele verificari redundante: daca echilibrul e stabilit, nu ar mai fi necesara verificarea factorului de echilibru pentru stramosii nodului.

Operatia de reechilibrare consta dintr-o secventa de reasignari de pointeri ( pointerii sunt de fapt schimbati ciclic, rezultand fie o simpla, fie o dubla rotatie a doua sau trei noduri implicate) si reajustari ale factorilor de echilibru.

Exemplul 1: Se considera secventa de chei 4, 5, 7, 2, 1, 3, 6 care se insereaza intr-un arbore AVL initial vid. Evolutia arborelui AVL si reechilibrarile facute sunt ilustrate in figura 5:

Analiza matematica a algoritmului de insertie in arbori binari nu e inca rezolvata. Teste empirice ale inaltimilor arborilor generati la insertie, duc la valori h= log(n) + c, c=0,25, deci arborii AVL se comporta la fel de bine ca cei perfect echilibrati, fiind insa mai usor de realizat. Testele empirice sugereaza ca in medie, reechilibrarea e necesara aproximativ la fiecare doua insertii, rotatiile simple si duble fiind echiprobabile. Arborii echilibrati trebuie utilizati numai cand operatiile de cautare sunt mult mai frecvente decat cele de inserare.

4. Suprimarea nodurilor in arbori echilibrati

Cel mai simplu se pot sterge nodurile terminale si cele care au un singur fiu. Daca nodul care trebuie sa fie sters are doi fii, il inlocuim prin nodul aflat in extrema dreapta a subarborelui sau stang. Cu ajutorul unei variabile logice h se va semnala reducerea inaltimii arborelui partial. Rechilibrarea este necesara numai daca nodul s-a gasit si in urma stergerii s-a redus inaltimea subarborelui. in urma unei operatii de echilibrare se poate reduce inaltimea altui subarbore, ducand la o noua reechilibrare. Exista cazuri simetrice de reechilibrare, pe stanga si pe dreapta.

In cazul cel mai defavorabil, suprimarea unui nod se realizeaza in O(log n) operatii. Diferenta esentiala dintre insertie si suprimare in cazul arborilor echilibrati consta in faptul ca daca in urma unei insertii, reechilibrarea se realizeaza prin una sau doua rotatii, a doua sau trei noduri, suprimarea poate necesita o rotatie a fiecarui nod situat pe drumul de cautare.

In realitate, testele experimentale indica faptul ca reechilibrarea devine necesara aproximativ la fiecare a doua insertie si la fiecare a cincea suprimare.

Exemplul 2: Se considera arborele din figura 6. In urma stergerii cheii 6, apare necesitatea echilibrarii. Arborele echilibrat este prezentat in figura.