Unelte utilizator
16:teme:racket-arbori-binari
Diferențe
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/14 15:24] Mihai Nan [Changelog] |
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: 14.03.2016 (15:30) | + | * 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 69: | Linia 70: | ||
| 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 cautare și o valoare pe care o inserează în arbore, dacă nu există, returnând arborele rezultat; | + | * ''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''); | * ''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); | * ''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); | ||
| Linia 106: | Linia 107: | ||
| * {{: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]] | ||
| Linia 112: | Linia 114: | ||
| * 10.03 -- mențiune, în enunț, a tipului de arbore primit ca parametru de funcțiile ''maximum'' / ''minimum'' / ''successor'' / ''predecessor''. | * 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. | * 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]]) | + | * 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). | ||
16/teme/racket-arbori-binari.1457961840.txt.gz · Ultima modificare: 2016/03/14 15:24 de către Mihai Nan
