Structuri de Date și Algoritmi - Managementul unui Magazin de Haine

1. Descrierea temei :

Să se realizeze managementul unui magazin de haine cu o structura de tip arbore AVL. In structura informatiei apar urmatoarele campuri:

- Id- cheia dupa care se creeaza structura

- Model haine

- Pret

- Culoare

- Marime

- Data vanzarii

Pentru aceasta structura se implementeaza urmatoarele operatii:

I. Operatii de baza

1. creare structura arbore din fisier

2. inserare inregistrare

3. modificare informatie(orice camp in afara de cheie)

4. cautare inregistrare in functie de cheie

5. stergere inregistrare in functie de cheie

6. afisare

a) pe nivele - se afiseaza numai cheile

b) completa - se afiseaza toate datele din structura sub forma tabelara

II. Operatii specifice

1.creare arbori folosind alte campuri din structura informatiei

2. adaugare date din alt fisier

3. prezentarea de situatii ale stocului in functie de diverse criterii

4. crearea de scenarii pentru testarea functiilor de inserare si stergere

5.salvarea datelor in fisier

Datele din structura de tip arbore AVL referitoare la model sunt trecute intr-o structura arborescenta de tip B. Pentru arborele B se implementeaza urmatoarele operatii:

1. inserare inregistrare

2. cautare inregistrare

3. afisare structura arborescenta pe nivele

4. salvare date in fisier

5. incarcare date din fisier

Consideratii teoretice

Arbori AVL

O solutie interesanta privind mentinerea unui arbore de cautare avantajos a fost descoperita de catre matematicienii G.M. Adelson-Velskii si E.M. Landis, care au conceput o structura arborescenta in care subarborii unei radacini nu difera in inaltime prea mult(arbori AVL). Solutia foloseste un camp in plus pentru nodurile arborilor, dar limiteaza foarte mult numarul mediu de operatii pentru cautarea unui element in arbore. In plus, metoda lor conduce la o metoda generala, convenabila pentru reprezentarea listelor liniare cu un numar determinat de elemente, imbinand avantajele alocarii secventiale si inlantuite a elementelor.

Definitie: se numeste inaltimea unui arbore ca fiind lungimea celui mai lung drum de la nodul radacina la unul din nodurile terminale.

Definitie: un arbore binar se numeste echilibrat daca inaltimea subarborelui din stranga nu difera cu mai mult de o unitate fata de inaltimea celui din dreapta. Se numeste factor de echilibrare diferenta dintre inaltimea subarborelui drept si a celui stang.

Atasand fiecarui nod un camp care reprezinta factorul de echilibrare al sau, un arbore binar inseamna ca este echilibrat cand toti factorii de echilibru ai nodurilor sunt -1, 0 sau +1.

In exemplul urmator, in noduri s-au figurat factorii de echilibrare, iar alaturi informatia utila atasata nodurilor. Exemplu de arbore echilibrat:

Sa observam acum ce se intampla daca dorim sa inseram un nou nod in arbore. Echilibrul arborelui nu se schimba daca s-ar atasa un nod dupa nodurile C,D,M,G,J. Acest echilibru se destrama daca s-ar atasa acesta dupa unul din nodurile K,L,I. In ultimul caz este necesara o reajustare a nodurilor.

Aceasta problema se pune atunci cand se va insera un nou element in subarborele din stanga al unui nod cu factorul de echilibru -1, sau in subarborele drept al unui nod cu factorul de echilibru +1.

In principal sunt doua cazuri cand se pune problema reajustarii nodurilor:

Primul caz este prezentat in figura urmatoare:

Am notat cu h, h, h+1 inaltimile celor trei subarbori.