Structuri de Date

L A B O R A T O R 13a

Arbori AVL

Un arbore AVL este un arbore binar de cautare echilibrat in inaltime. Pentru fiecare nod dintr-un arbore AVL inaltimea subarborelui stanga diferade inaltimea subarborelui dreapta cu cel mult 1. In fiecare nod p se memoreaza inaltimea sa, adica numarul de noduri de pe cea mai lunga ramura care pleaca din nodul p. Dupa adaugarea unui nou nod se verifica diferenta dintre inaltimile celor doi subarbori la fiecare nod afectat de adaugare; daca aceasta diferenta este mai mare ca 1 (in valoare absoluta) atunci se face o rotatie simpla sau dubla pentru corectarea acestei diferente.

Sa se scrie:

1- Definitia unui tip "tnod" pentru un nod de arbore binar AVL care contine:o valoare intreaga (val), inaltime nod (h), adrese noduri fii (st,dr). O functie "make" pentru crearea unui nod frunza cu valoarea "val" si inaltimea 1.

2- O functie recursiva pentru adaugarea unui nod nou la un arbore binar de cautare, cu modificarea inaltimilor nodurilor afectate de adaugare: void add (tnod* & r, int x); // adauga x la arborele cu radacina r

3- O functie de afisare prefixata cu indentare, care marcheaza absenta unui fiu printr-un minus ('-'), dar nu si absenta ambilor fii (nodurile frunza nu sunt urmate de '-'). Se va afisa valoarea si inaltimea fiecarui nod (intre paranteze).Exemplu de afisare dupa adaugarea valorilor 5,8,3,6,7

5(4) 3(1) 8(3) 6(2) - 7(1) -

Sa se verifice impreuna cu functia de adaugare "add" prin creare si afisare arbore.

4- Functiile de rotatie a radacinii unui arbore la stanga (rotL) si la dreapta (rotR), prin inlocuire cu fiul dreapta si respectiv cu fiul stanga. Primainstructiune afiseaza litera 'L' sau 'R' si valoarea din nodul rotit (radacina).Sa se verifice rotind la stanga radacina arborelui (1(-,2(-,3)) si la dreaptaradacina arborelui (3(2(1,-),-))

5- Functiile de rotatie nod radacina, care modifica si inaltimile nodurilor rotite: rotL, rotR (rotatii simple la stanga si la dreapta) Indicatie: in functia "rotL" se vor adauga urmatoarele linii:

r->h = 1+max( ht(r->st),ht(r->dr)); // inaltime r dupa rotatie f->h = 1+max( ht(f->dr),r->h); // inaltime f dupa rotatie

Functia urmatoare are ca rezultat inaltimea unui nod (memorata in nod): int ht (tnod* r) { return r==NULL? 0 : r->h; }

6- Functii de rotatie dubla, pentru 3 noduri in zig-zag : rotRL (tnod* p) // rotatie dreapta fiu dreapta p + rotatie stanga p rotLR (tnod* p) // rotatie stanga fiu stanga p + rotatie dreapta p

Sa se verifice functia rotRL pe radacina arborelui (1(-,3(2,-)) si functia rotLRpe radacina arborelui (3(1(-,2),-))

7- O functie "main" care adauga si afiseaza succesiv arborele AVL rezultatdupa adaugare, folosind functia de adaugare cu corectie "addFix". Pentru verificare se va folosi secventa urmatoare care produce rotatii simplesi duble: 5,4,1,7,8,6,2. La fiecare pas se afiseaza valoarea adaugata, directia de rotatie, valoarea nodului rotit (de ex: L5,R7,L4 ,..) si tot arborele.

Functia urmatoare face adaugarea si corectia necesara pentru arbori AVL:

void addFix ( tnod* & r, int x ) { // adauga x la arbore cu radacina r if( r == NULL ) { // daca arbore vid r = make(x); // creare nod frunza cu inaltimea 1 return; } if (x==r->val) // daca x exista deja in arbore return; // atunci nu se mai adauga if( x < r->val ) { // daca x mai mic addFix ( r->st,x ); // atunci se adauga la stanga if( ht(r->st) - ht(r->dr) > 1 )// daca r dezechilibrat stanga if( x < r->st->val ) // daca x e in fiul stanga rotR( r ); // rotatie simpla la dreapta else // daca x e in fiul dreapta rotLR( r ); // rotatie dubla stanga-dreapta } else { //daca x mai mare addFix ( r->dr,x ); // atunci se adauga la dreapta if( ht(r->dr) - ht(r->st) > 1 ) // daca r dezechilibrat dreapta if( x > r->dr->val ) // daca x e in fiul dreapta rotL( r ); // rotatie simpla la stanga else // daca x e in fiul stanga rotRL( r ); // rotatie dubla dreapta-stanga } r->h = max(ht(r->st), ht(r->dr)) + 1; // recalculare inaltime nod r}

8- Sa se rescrie functiile rotL, rotR, rotLR, rotRL si addFix fara a folosiargumente referinta (functii cu rezultat tnod*) si sa se verifice cu functia"main" de la programul anterior (modificata corespunzator).