APLICATII - Lucrarea nr.3: ARBORI BINARI ECHILIBRATI AVL

5.Exercitii

5.1.Sa se construiasca arborele AVL rezultat prin inserarea, in ordine, a cheilor din secventa: 3,6,9,5,10,4,1,0,2. Se vor reprezenta toate etapele de constructie a arborelui si se vor discuta operatiile de echilibrare.

5.2.Sa se gaseasca arborele AVL rezultat prin suprimarea nodurilor 6,4,0 din arborele AVL construit in exercitiul anterior.

6.Probleme de implementare

6.1. Sa se implementeze clasa TArboreAVL. Se va tine cont de faptul ca arborii AVL sunt un caz particular de arbori binari ordonati, iar operatiile de parcurgere si de cautare se fac in mod identic atat pentru arborii binari ordonati cat si pentru AVL. Arborii AVL introduc modificari in ceea ce priveste operatiile de inserare si de stergere. O rezolvare a acestei probleme este data in listing-ul din Anexa 4.

6.2. Sa se redacteze un program interactiv care implementeaza urmatoarele functii pentru prelucrarea unui arbore AVL, avand chei numerice:

• C - initializeaza arborele AVL ( il face vid, cu recuperarea zonei de memorie corespunzatoare.)
• I - insereaza un nod cu o cheie precizata, semnaland reechilibrarea;
• S - suprima un nod cu o cheie precizata, semnaland reechilibrarea;
• V - vizualizeaza arborele pe niveluri;
• P - pentru o secventa aleatoare de chei care vor fi inserate in arborele AVL, determina raportul intre numarul de reechilibrari si numarul total de insertii. Analog pentru suprimare.
• X - terminare.

6.3. Pornind de la o secventa oarecare de chei numerice, sa se construiasca ABO si AB AVL corespunzatori. Se cere: - sa se masoare timpii de construire ai celor doi arbori; - sa se tipareasca, pe niveluri, arborii; - sa se masoare timpii de cautare in cei doi arbori, ai unei secvente de chei - sa se masoare timpii de suprimare din cei doi arbori, ai unei secvente de chei.

7.Aplicatii

7.1. Pentru un N citit de la tastatura, sa se genereze toate permutarile numerelor de la 1 la N, fiecare secventa constituind cheile ce se insereaza in cate un arbore AVL. Sa se vizualizeze arborii, pentru fiecare discutandu-se inaltimea si numarul de reechilibrari necesare generarii

7.2. Pentru o inaltime H care se citeste de la tastatura, sa se construiasca arborele AVL cu numar minim de noduri (arbore Fibonacci).
a. Sa se precizeze care este numarul de noduri, N din acest arbore.
b. Se va construi si arborele binar perfect echilibrat cu N noduri, precum si arborele AVL corespunzator unei secvente aleatoare de N chei. Sa se discute performantele operatiilor de cautare in cei 3 arbori.

7.3.Sa se implementeze operatorii: EsteAVL(arbore_binar) care testeaza daca un arbore binar este arbore AVL, si EsteEch(arbore_binar) care testeaza daca un arbore binar este un arbore perfect echilibrat.
Indicatii
Definitia arborilor AVL precizeaza ca pentru oricare nod din arbore, inaltimile celor doi subarbori ai sai difera cu cel mult 1. Deci un arbore este arbore AVL daca subarborii sai sunt arbori AVL si daca inaltimile lor difera cu cel mult 1 nivel. 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. Deci un arbore este perfect echilibrat daca cei doi subarbori ai sai sunt arbori perfect echilibrati si daca dimensiunile lor(numarul de noduri) difera cu cel mult 1 nod.