Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.
Both sides previous revision Versiuni anterioare Urmatoarea versiune | Versiuni anterioare | ||
16:teme:racket-arbori-binari [2016/03/10 15:29] Mihai Nan [Construcția arborelui - 30 de puncte] |
16:teme:racket-arbori-binari [2016/03/18 21:55] (curent) Mihai Nan [Racket: Arbori binari] |
||
---|---|---|---|
Linia 5: | Linia 5: | ||
* Deadline hard: __29.03.2016 ora 23.59__ | * Deadline hard: __29.03.2016 ora 23.59__ | ||
* Data publicării: 08.03.2016 | * Data publicării: 08.03.2016 | ||
- | * Data ultimei modificări: 08.03.2016 | + | * Data ultimei modificări: 16.03.2016 (21:00) |
- | * Tema se va încărca pe **vmchecker** (disponibil în curând) | + | * Tema se va încărca pe **vmchecker** |
+ | * Data tester-ului: 18.03.2016 | [[https://elf.cs.pub.ro/vmchecker/ui/#PP|vmchecker]] | ||
* [[http://cs.curs.pub.ro/2015/mod/forum/view.php?f=732|Forum tema 1]] | * [[http://cs.curs.pub.ro/2015/mod/forum/view.php?f=732|Forum tema 1]] | ||
* [[#changelog|changelog]] | * [[#changelog|changelog]] | ||
Linia 51: | Linia 52: | ||
* ''postorder'' - formează o listă cu valorile nodurilor parcurse în postordine (**//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; | * ''successor'' - primește un arbore binar de căutare și o valoare și determină succesorul valorii; | ||
- | * ''predecessor'' - primește un arbore binat de căutare și o valoare și are ca rezultat predecesorul 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''. | 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''. | ||
Linia 68: | Linia 69: | ||
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** ([[https://en.wikipedia.org/wiki/AVL_tree|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). | 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** ([[https://en.wikipedia.org/wiki/AVL_tree|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 [[https://www.cs.usfca.edu/~galles/visualization/AVLtree.html|aici]]. | ||
=== Submulțimi - 20 de puncte === | === Submulțimi - 20 de puncte === | ||
Linia 89: | Linia 100: | ||
* Este indicată utilizarea funcționalelor. Folosirea adecvată a acestora sau nefolosirea acestora aduc modificări în punctajul temei (în limita a 1 punct). | * 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. | * 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. | ||
== Resurse == | == Resurse == | ||
* {{:16:teme:binary-tree.zip|Arhiva de pornire}} | * {{:16:teme:binary-tree.zip|Arhiva de pornire}} | ||
+ | * {{:16:teme:binary-tree-v1.zip|Arhiva de pornire - varianta actualizată}} | ||
* [[https://www.cs.usfca.edu/~galles/visualization/AVLtree.html|AVL Tree Visualization]] | * [[https://www.cs.usfca.edu/~galles/visualization/AVLtree.html|AVL Tree Visualization]] | ||
== Changelog == | == Changelog == | ||
+ | * 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 - 50 de puncte|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). |