Racket: Arbori binari

• Responsabil: Mihai Nan
• Deadline soft: 24.03.2016, apoi depunctare 0.5p/zi
• Deadline hard: 29.03.2016 ora 23.59
• Data publicării: 08.03.2016
• Data ultimei modificări: 16.03.2016 (21:00)
• Tema se va încărca pe vmchecker
• Data tester-ului: 18.03.2016 | vmchecker
• Forum tema 1
• changelog

Un arbore combină avantajele oferite de alte două structuri de date: tablourile și listele înlănțuite. Arborii permit, pe de o parte, executarea unor căutări rapide, la fel ca și tablourile ordonate, iar, pe de altă parte, inserarea și ștergerea elementelor sunt operații rapide, la fel ca în cazul unei liste simplu înlănțuite.

Această temă dorește să vă introducă în vasta lume a arborilor și vă propune spre analiză și implementare o metodă de reprezentare a mulțimilor, folosind arbori binari de căutare, precum și o serie de operații specifice acestora.

Reprezentarea internă a arborelui binar de căutare va fi la alegere, însă va trebui să implementați corespunzător setul de funcții de acces.

Fazele pe care trebuie sa le aveti in vedere pentru realizarea acestei teme sunt urmatoarele:

• decizia asupra reprezentării interne a arborelui binar;
• implementarea setului de funcții de acces pentru reprezentarea aleasă;
• construcția unui arbore binar de căutare și conversia unei liste într-o mulțime, realizată uzitând reprezentarea propusă;
• implementarea operațiilor de bază cu mulțimi: apartenență, inserare element, reuniune, intersecție, diferență;
• determinarea unor submulțimi cu o anumită proprietate;
• BONUS: construcția arborelui sintactic asociat unei expresii matematice și evaluarea acesteia pe baza arborelui binar.

Pentru a putea utiliza un arbore binar de căutare în reprezentarea unei mulțimi, va trebui să definiți o serie de operații. Astfel, pentru început, veți defini funcțiile enumerate în fișierul binary-tree.rkt pentru task-ul pregătitor.

În continuare, se va descriere funcționalitatea fiecarei funcții.

• init-node - primește o valoare și returnează o frunză ce conține acea valoare;
• make-node - returnează un nod, având componentele specificate;
• is-leaf? - verifică dacă un nod este frunză;
• get-value - returnează valoarea reținută într-un nod;
• get-left - returnează subarborele stâng al unui arbore;
• get-right - returnează subarborele drept al unui arbore;
• is-node? - verifică dacă parametrul primit respectă reprezentarea aleasă pentru un nod;
• is-empty? - verifică dacă arborele primit ca parametru este vid;
• has-left? - verifică dacă arborele conține un subarbore stâng nevid;
• has-right? - verifică dacă arborele conține un subarbore drept nevid;
• minimum - determină valoarea minimă din arborele binar de căutare;
• maximum - determină valoarea maximă din arborele binar de căutare;
• height - întoarce înălțimea unui arbore binar;
• inorder - formează o listă cu valorile nodurilor parcurse în inordine;
• preorder - formează o listă cu valorile nodurilor parcurse în preordine (opțional);
• postorder - formează o listă cu valorile nodurilor parcurse în postordine (opțional);
• successor - primește un arbore binar de căutare și o valoare și determină succesorul valorii;
• predecessor - primește un arbore binar de căutare și o valoare și are ca rezultat predecesorul valorii.

Pentru testarea acestor funcții, se va defini (manual) arborele de mai jos, în fișierul binary-tree.rkt. Acesta va avea ca identificator binary-search-tree.

Principalele operații cu mulțimi sunt:

• apartenența - verifică dacă o valoare se găsește într-o mulțime;
• eliminarea unui element din mulțime;
• reuniunea a doua mulțimi, având ca rezultat o mulțime care conține elementele din cele doua mulțimi;
• intersecția a doua mulțimi, având ca rezultat o mulțime care conține elementele comune din cele doua mulțimi;
• diferența a doua mulțimi, având ca rezultat o mulțime care conține elementele care se afla in prima mulțime, dar nu și în a doua.

Implementați aceste operații pentru mulțimi reprezentate folosind arbori binari de căutare.

Un arbore este neechilibrat dacă rădăcina are mai mulți descendenți stângi decât drepți sau invers. De obicei, arborii neechilibrați rezultă în urma unui proces de inserare a nodurilor cu valori ordontate (crescător / descrescător). În cazul unui arbore binar de căutare neechilibrat, operațiile nu mai sunt eficiente. Având în vedere că în cadrul acestei teme folosim arborii pentru reprezentarea mulțimilor care sunt ordonate, șansele ca arborele pe care dorim să îl realizăm să rezulte neechilibrat sunt foarte mari. De aceea, va trebui să utilizați arbori binari pentru care diferența dintre înălțimea subarborelui stâng și a subarborelui drept este -1, 0 sau 1 (Arbori AVL). Pentru a implementa un astfel de arbore, va trebui să realizați o serie de rotații specifice la fiecare modificare a arborelui (inserarea unui element, ștergerea unui element).

• insert - primește un arbore binar de căutare și o valoare pe care o inserează în arbore, dacă nu există, returnând arborele rezultat;
• balance - primește ca parametru un arbore binar de căutare neechilibrat și are ca rezultat un arbore AVL (se aplică în cazul funcțiilor ce modifică arborele: insert și delete);
• union - primește doi arbori binari de căutare și returneaza reuniunea lor, tot sub formă de arbore binar de căutare (rezultatul trebuie să fie un arbore echilibrat);
• intersection - primește doi arbori binari de căutare și returnează intersecția lor, rezultatul fiind reprezentat sub forma unui arbore binar de căutare echilibrat;
• complements - primește doi arbori binari de căutare și returnează diferența lor, rezultatul fiind reprezentat sub forma unui arbore binar de căutare echilibrat;
• contains - primește un arbore de căutare și o valoare și verifică dacă valoarea există în arbore (#t - dacă există / #f - dacă nu există);
• remove - primește un arbore binar de căutare și o valoare pe care o va șterge din arbore, returnând arborele binar de căutare rezultat.

Observație: În cazul funcției balance NU este permisă reconstrucția unui nou arbore, introducând nodurile în așa fel încât rezultatul să fie un arbore echilibrat. Pentru a înțelege mai bine cum trebuie să echilibrați arborele, puteți folosi animația de aici.

Având o mulțime, reprezentată folosind un arbore binar de căutare, dorim sa determinăm toate submulțimile acesteia, ce au cardinalul k.

Numim submulțime zig-zag o submulțime A = {x1, x2, x3, … } pentru care x1 < x2 > x3 < … sau x1 > x2 < x3 > …. Implementați funcția care determină toate submulțimile maximale, ca număr de elemente, zig-zag ale unei mulțimi.

In matematică, o expresie aritmetică este reprezentată printr-un șir de caractere compus din: variabile, constante, operatori și paranteze. O astfel de expresie aritmetică poate fi reprezentată printr-un arbore binar. Nodul rădăcină conține un operator, iar fiecare din subarborii săi reprezintă fie numele unei variabile sau unei constante, fie o altă expresie. În arborele binar asociat unei expresii nu apar parantezele. Pentru operațiile comutative, ordinea subarborilor stâng și drept nu contează, aceștia pot fi inversați, iar arborele este bine construit. În cazul operațiilor necomutative, ordinea subarborilor este strict precizată, adică subarborii nu pot fi inversați în reprezentare. În general, arborele binar asociat unei expresii nu este unic.

Construiți arborele sintactic pentru o expresie dată în forma infixată și evaluați expresia pe baza acestei reprezentări.

• Încărcarea temelor, ca și testarea și notarea lor, se va face pe vmchecker. Este suficient să includeți fișierul binary-tree.rkt (plus readme) în arhivă, testele există deja.
• În arhiva temei includeți un fișier README cu detalii despre cum ați implementat structura arborelui.
• Sunt interzise efectele laterale de orice fel (set!, set-car! etc.).
• Nu implementați arborele ca listă simplă (liniară, ne-imbricată) în care găsirea nodurilor se face prin calcul de indecși.
• Este indicată utilizarea funcționalelor. Folosirea adecvată a acestora sau nefolosirea acestora aduc modificări în punctajul temei (în limita a 1 punct).
• Se va lucra exclusiv în fișierul binary-tree.rkt. Elementele de implementat sunt clar indicate.
• Funcțiile minimum, maximum, successor, predecessor se vor realiza folosind exclusiv structura arborelui binar de căutare. NU este permisă conversia arborelui într-o altă structură de date și realizarea operațiilor pe structura respectivă!
• Operațiile cu mulțimi se vor realiza folosind exclusiv structura arborelui binar de căutare. NU este permisă conversia arborelui într-o alta structură de date (ex. listă) și realizarea operațiilor pe această structură.
• În cazul bonusului, este obligatorie folosirea arborelui sintactic asociat pentru evaluarea expresiei.

• Arhiva de pornire
• Arhiva de pornire - varianta actualizată
• AVL Tree Visualization

• 10.03 – mențiune, în enunț, a tipului de arbore primit ca parametru de funcțiile maximum / minimum / successor / predecessor.
• 10.03 – adăugarea unor precizări referitoare la reprezentarea folosită în cadrul implementării funcțiilor de la prima cerință și a operațiilor specifice mulțimilor.
• 14.03 – am detaliat funcțiile de la task-ul 1. (Operații cu mulțimi)
• 16.03 – am adăugat o arhiva actualizată (crearea arborelui începe de la empty-tree, la testarea submulțimilor nu se mai ține cont de ordinea acestora, afișează mesaje sugestive în cazul unui arbore care nu respectă propritățile la task-ul 1).