Arbori echilibrati AVL. Tehnici de insertie si suprimare

1. Scopul lucrarii il constituie prezentarea structurii de arbore echilibrat AVL si a operatiilor principale ce se pot efectua pe aceasta structura.

2. Aspecte teoretice.

2.1. Prezentare

In cazul arborilor binari ordonati, media numarului de noduri parcurse in scopul gasirii unui anumit nod (performanta cautarii) depinde de inaltimea arborelui respectiv. Aceasta medie este minima atunci cand arborele este perfect echilibrat, deci are inaltimea minima.

Activitatea de restructurare a arborelui la fiecare insertie si suprimare astfel incat el sa fie intotdeauna echilibrat este complexa. Daca termenul de "echilibrat" este definit intr-o maniera mai putin stricta, tehnica de reorganizare se simplifica. O astfel de definitie a echilibrarii a fost propusa de Andelson-Velskii si Landis in 1962: un arbore este echilibrat daca si numai daca inaltimile celor doi subarbori ai sai difera cu cel mult 1. Arborii care satisfac acest criteriu numesc arbori AVL (Andelson-Velskii si Landis).

In cele ce urmeaza, acesti arbori vor fi numiti si arbori echilibrati. Aceasta definitie, pe langa ca este simpla, conduce la o procedura viabila de reechilibrare si la o lungime medie a drumului de cautare practic identica cu cea a unui arbore perfect echilibrat.

2.2. Cautarea in arborii AVL

Intrucat arborii AVL sunt arbori binari ordonati, cautarea unui nod cu o cheie data se realizeaza in modul prezentat la arborii binari ordonati.

2.3. Insertia in arborii AVL

Insertia unui nod in arborii AVL presupune insertia normala a nodului intr-un arbore binar ordonat, urmata de o eventuala echilibrare. 

De exemplu, pentru arborele din figura 5.1, consideram insertia unuia dintre nodurile legate prin arce reprezentate cu linie intrerupta. Astfel, nodurile 9 si 11 pot fi inserate fara echilibrare, arborele cu radacina 10 devenind nesimetric (cu subarbori de inaltimi inegale, dar echilibrat AVL), iar arborele cu radacina 8 imbunatatindu-si echilibrul. Insertia nodurilor 1, 3, 5, si 7 necesita insa reechilibrare (arborele cu radacina 8 va fi dezechilibrat).

Echilibrul unui arbore il vom memora in nodul sau radacina. Astfel, fiecare nod va avea un factor explicit de echilibru, egal cu diferenta dintre inaltimea subarborelui sau drept si inaltimea subarborelui sau stang. Astfel, valorile admise intr-un arbore AVL pentru acest factor sunt: -1 (subarborele stang este mai inalt cu 1 decat cel drept), 0 (cei doi subarbori sunt egali ca inaltime), sau 1 (subarborele drept este mai inalt cu 1). Asadar, structura unui nod trebuie sa cuprinda si un camp pentru memorarea factorului sau de echilibru:

struct _nodAVL;

Pornind de la aceasta structura de nod, insertia unui nod se realizeaza in trei etape:

1. se parcurge arborele binar, pentru a verifica daca cheia exista deja;

2. se insereaza noul nod si se semnaleaza ca s-ar putea sa fie nevoie de reechilibrare;

3. se revine pe drumul de cautare si, pentru fiecare nod, daca inaltimea subarborelui sau in care a avut loc insertia (h₁) a crescut, in functie de situatia echilibrului existenta anterior insertiei, se va hotari daca este necesara sau nu reechilibrarea (h₂ este inaltimea celuilalt subarbore):

a.     daca initial h₁ < h₂ => in urma insertiei cei doi subarbori devin de inaltimi egale, echilibrul fiind imbunatatit in urma insertiei.

b.     daca initial h₁ = h₂ => in urma insertiei subarborele in care a avut loc insertia devine mai inalt, respectand insa criteriul echilibrului.

c.      daca initial h₁ > h₂ => in urma insertiei criteriul echilibrului este incalcat si arborele trebuie reechilibrat.

Daca analizam atent situatiile posibile ce rezulta in urma insertiei, observam ca exista numai doua configuratii in care sunt necesare efectiv reechilibrari. Operatia de reechilibrare consta dintr-o serie de reasignari de legaturi in arbore, rezultand o simpla rotatie sau o dubla rotatie a doua sau trei noduri implicate. Pe langa aceasta, factorii de echilibru respectivi sunt reajustati. Cele 4 cazuri distincte care pot aparea sunt:

- rotatia simpla stanga (figura 5.2);

- rotatia simpla dreapta (figura 5.3), simetrica rotatiei simple stanga;

- rotatia dubla stanga (figura 5.4);

- rotatia dubla dreapta (figura 5.5), simetrica rotatiei duble stanga.

In figurile prezentate, nodul X este cel care a fost inserat si care a produs dezechilibrarea. Identificatorii nodurilor nu reflecta aici ordonarea in arbore, ci sunt doar pentru identificare. Tot din figurile respective rezulta modul in care variaza factorul de echilibru dupa operatia de echilibrare (numai pentru nodurile la care variaza). Cu * este marcat nodul la care se simte nevoia reechilibrarii pe drumul de revenire. h din figuri poate fi si 0, deci subarborii reprezentati ca avand inaltimea h pot fi si vizi.

Referat: Contabilitatea tertilor Referat: Structurarea elementelor de activ si pasiv dupa criterii financiare

La rotatia dubla, in cazul in care h = 0, X va deveni radacina subarborelui (avand ca fii  pe a si pe b), iar a si b nu vor avea fii; altfel spus, X este in locul lui e din figuri. Daca h0, pentru actualizarea corecta a factorilor de echilibru, este important in care dintre subarborii lui e a fost inserat X; daca a fost inserat in stangul, in figura este marcat cu X_S (prima valoare pentru factorul de echilibru - acolo unde sunt doua - se refera la acest caz), in caz contrar este marcat cu X_D (a doua valoare pentru factorul de echilibru, acolo unde sunt doua). Fie P partea in care este dezechilibrat a (partea cu subarborele mai mare), iar PO, partea opusa.

Daca pentru e, h_P > h_PO, vom avea: b va fi echilibrat, iar pentru a, h_P < h_PO.

Daca pentru e, h_P < h_PO, vom avea: a va fi echilibrat, iar pentru b, h_P > h_PO.

Partea in care se face rotatia este cea in care se afla subarborele mai inalt. In cazul insertiei, acesta este cel in care a avut loc insertia.

Daca nodurile a si b din figuri au, dupa insertie, subarborii mai mari in aceeasi parte, rotatia va fi simpla, iar daca ii au in parti diferite, va fi dubla.

Se observa ca o reechilibrare readuce subarborele echilibrat la inaltimea anterioara insertiei, deci, dupa o insertie, pe drumul de revenire va fi necesara cel mult o reechilibrare.

2.4. Suprimarea din arborii AVL

Procedura de suprimare echilibrata reprezinta o combinatie intre tehnicile de suprimare a nodurilor din arborii binari ordonati si cele de echilibrare: intai nodul dorit este suprimat (prin metoda cunoscuta), apoi se verifica daca este necesara reechilibrarea si, in caz afirmativ, structura de arbore se reechilibreaza.

In cazul suprimarii, partea in care se face rotatia este cea opusa celei in care se afla subarborele in care a avut loc suprimarea.

La revenirea pe drumul de cautare, daca inaltimea subarborelui in care a avut loc suprimarea (h₂) a scazut, in functie de situatia echilibrului existenta anterior suprimarii, se va hotari daca este necesara sau nu reechilibrarea (h₁ este inaltimea celuilalt subarbore):

a.     daca initial h₁ < h₂ => in urma suprimarii, cei doi subarbori devin de inaltimi egale, echilibrul fiind imbunatatit in urma suprimarii.

b.     daca initial h₁ = h₂ => in urma suprimarii, subarborele in care a avut loc suprimarea devine mai putin inalt, respectand insa criteriul echilibrului.   

c.      daca initial h₁ > h₂ => in urma suprimarii, criteriul echilibrului este incalcat si arborele trebuie reechilibrat.

Ca si in cazul insertiei, daca nodurile a si b din figuri au, dupa suprimare, subarborii mai mari in aceeasi parte, rotatia va fi simpla, iar daca ii au in parti diferite, va fi dubla. La suprimare putem intalni si o alta situatie (care nu poate aparea in cazul insertiei): atunci cand subarborele mai inalt este echilibrat, adica nodul b din figuri are subarborii de inaltimi egale. In acest caz, reechilibrarea presupune o rotatie simpla. Diferenta care apare fata de rotatia simpla prezentata inainte este la ajustarea factorilor de echilibru ai nodurilor a si b. Mai jos se prezinta rotatia stanga in acest caz.

Se observa ca dupa aceasta rotatie nodul radacina al arborelui obtinut nu este perfect echilibrat.

La suprimare nu intotdeauna este suficienta o singura reechilibrare pe drumul de cautare, la intoarcere.

3. Problema rezolvata

Pentru pentru ca regasirea ulterioara a unor informatii intr-un volum mare de date sa fie rapida, se cere sa se implementeze un arbore AVL in care sa se poata insera noduri (pentru memorarea datelor) si din care sa se poata suprima noduri.

Rezolvare

Pentru simplificare, datele de introdus sunt intregi. Variabila h va fi setata atunci cand are loc o insertie sau o suprimare efectiva, deci atunci cand inaltimea subarborelui in care se opereaza se poate sa se fi modificat. Ea este verificata la revenirea pe drumul de cautare a locului de insertie (respectiv a nodului de sters in cazul suprimarii) pentru a stabili daca sunt necesare reechilibrari.

In cazul insertiei, la prima reechilibrare, ea va fi resetata.

La suprimare, va fi resetata cand apare cazul-exceptie prezentat la suprimare sau cand inaltimile subarborilor nodului de verificat (la revenire) erau egale inainte de suprimare, altfel, reechilibrarile pot avea loc in lant pana la nodul radacina.

Pentru reechilibrari avem doua functii, cate una pentru fiecare din cele doua tipuri de rotatii (simpla si dubla). Partea in care se face o rotatie este data ca parametru acestor functii, intrucat rotatia dreapta este perfect simetrica celei stangi (oricare se poate obtine din cealalta interschimband referintele spre stanga cu referintele spre dreapta). Variabilele st si dr sunt setate in functie de partea dorita. Pentru a realiza simetria, fiii unui nod au fost declarati sub forma unui tablou de doua elemente, primul referindu-se la fiul stang, al doilea - la cel drept; astfel, daca st = 0 (se refera la primul fiu, cel stang) si dr = 1 (se refera la fiul al doilea, cel drept), rotatia va fi stanga, iar invers (st = 1, dr = 0), va fi dreapta.

In tabloul cu doua elemente, echMareP, prima pozitie este pentru partea stanga, iar a doua - pentru cea dreapta. Tabloul memoreaza pentru fiecare parte echilibrul unui arbore mai inalt in partea respectiva (echMareP[0] = -1, echMareP[1] = 1). Negand elementele acestui tablou, obtinem echilibrul unui arbore mai inalt in partea opusa.

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

enum ;

typedef struct _nodAVLnodAVL;

nodAVL *rad;

int h;/*va indica:

- la insertie: daca inaltimea subarborelui in care s-a inserat a crescut

- la suprimare: daca inaltimea subarborelui din care s-a suprimat a scazut */

int echMareP[2] = , echilibrat = 0;

//echilibrele posibile pt. un nod AVL

//rotatia simpla in partea specificata

void RotSimpla(int parte, nodAVL **p)

else //rotatie simpla dreapta

//initial, **p este nodul a din figuri

p1 = (*p)->f[st];//initial, *p1 este nodul b din figuri

//cazul exceptie la supr. => a nu va fi perfect ech. (hP > hPO)

if(h == 2) (*p)->ech = echMareP[parte];

else //altfel, a va fi perfect echilibrat (ech = 0)

(*p)->ech = echilibrat;

//reasignarea pointerilor

(*p)->f[st] = p1->f[dr];//e va fi fiu al lui a

p1->f[dr] = *p;//a va fi fiu al lui b

*p = p1;//b va fi radacina subarborelui

//rotatia dubla in partea specificata

void RotDubla(int parte, nodAVL **p)

else //rotatie dubla dreapta

//initial, **p este nodul a din figuri

p1 = (*p)->f[st];//*p1 este initial nodul b

p2 = p1->f[dr];//*p2 este initial nodul e

//ajustarea factorilor de echilibru

if(p2->ech==echMareP[parte])else

if(p2->ech==echMareP[1-parte]) else

//reasignarea pointerilor

(*p)->f[st] = p2->f[dr];//un fiu al lui e va fi al lui a

p1->f[dr] = p2->f[st];//celalalt fiu al lui e va fi al lui b

p2->f[st] = p1;//b va fi fiu al lui e

p2->f[dr] = *p;//a va fi fiu al lui e

*p = p2;//e va fi radacina subarborelui

//la revenirea dintr-o parte, la stergere

void RevSterg(int parte, nodAVL **p)

elseelse//pt b, hP <= hPO

if((*p)->f[1-parte]->ech== echilibrat)

else

}

void AdaugNod(nodAVL **p, int x);

void InsNod(int parte, nodAVL **p, int x)

else//pt a, aveam hP >= hPO

if((*p)->ech == echilibrat)

// pt a, aveam hP = hPO

(*p)->ech = echMareP[parte];

//si vom avea hP > hPO

else

void AdaugNod(nodAVL **p, int x)

void StergNod1(nodAVL **p, nodAVL *nS)

else

void StergNod(nodAVL **p, int x)else

else

if(x > (*p)->cheie)

else

else

if((*p)->f[1]==NULL)

else

}

}

//afisarea subarborelui cu radacina p

void Afis(nodAVL *p, int niv)

//stergerea subarborelui cu radacina p

void StergAVL(nodAVL *p)

int main(void)

printf('Arborele AVL este:n');

Afis(rad, 0);

doelse if(optiune=='2')

}

}while(optiune!='0');

StergAVL(rad);

return 0;

4. Probleme propuse

4.1. Sa se construiasca un arbore binar ordonat si unul AVL, pornind de la aceeasi secventa de chei (generate aleator sau citite dintr-un fisier). Sa se compare inaltimile celor doi arbori si sa se afiseze diferenta raportata la numarul de chei, precum si raportul celor doua inaltimi.

4.2. Sa se modifice problema rezolvata astfel incat sa se semnaleze atunci cand are loc o reechilibrare, fie la insertie, fie la suprimare. Sa se afiseze in final un raport intre numarul de insertii si numarul de reechilibrari la insertie si un raport intre numarul de suprimari si numarul de reechilibrari la suprimare.

4.3. Sa se scrie un program care verifica daca un arbore binar ordonat este AVL.