{"id":8570,"date":"2023-04-23T15:45:59","date_gmt":"2023-04-23T13:45:59","guid":{"rendered":"https:\/\/blue.pri.ee\/ttu\/?p=8570"},"modified":"2026-04-21T16:38:49","modified_gmt":"2026-04-21T14:38:49","slug":"pr2et13-puud","status":"publish","type":"post","link":"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et13-puud\/","title":{"rendered":"PR2ET13: Puud"},"content":{"rendered":"<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_85 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et13-puud\/#Praktikumi_materjal\" >Praktikumi materjal<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et13-puud\/#Praktikumi_ulesanded\" >Praktikumi \u00fclesanded<\/a><ul class='ez-toc-list-level-4' ><li class='ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et13-puud\/#Ulesanne_W13-1_Lineaarotsingu_vordlus_kahendotsingpuuga\" >\u00dclesanne [W13-1]: Lineaarotsingu v\u00f5rdlus kahendotsingpuuga<\/a><ul class='ez-toc-list-level-5' ><li class='ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et13-puud\/#Uldised_nouded\" >\u00dcldised n\u00f5uded<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et13-puud\/#Programm_1_Lineaarotsing\" >Programm 1: Lineaarotsing<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et13-puud\/#Lineaarse_algoritmi_testimine\" >Lineaarse algoritmi testimine<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et13-puud\/#Programm_2_Kahendotsingpuu\" >Programm 2: Kahendotsingpuu<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et13-puud\/#Kahendotsingpuu_testimine\" >Kahendotsingpuu testimine<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et13-puud\/#Programmide_tooaja_vordlemine\" >Programmide t\u00f6\u00f6aja v\u00f5rdlemine<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-10\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et13-puud\/#Lisaulesanne_W13-2_Trie_puu\" >Lisa\u00fclesanne [W13-2]: Trie puu<\/a><ul class='ez-toc-list-level-5' ><li class='ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-11\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et13-puud\/#Soovituslik_andmestruktuur\" >Soovituslik andmestruktuur<\/a><\/li><\/ul><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-12\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et13-puud\/#Parast_seda_tundi_peaksid\" >P\u00e4rast seda tundi peaksid<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-13\" href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et13-puud\/#Taiendav_materjal\" >T\u00e4iendav materjal<\/a><\/li><\/ul><\/nav><\/div>\n<h3><span class=\"ez-toc-section\" id=\"Praktikumi_materjal\"><\/span>Praktikumi materjal<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<ul>\n<li>Slaidid: <a href=\"https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/slaidid-et\/13_puud.pdf\"><b>Puud<\/b><\/a><\/li>\n<\/ul>\n<h3><span class=\"ez-toc-section\" id=\"Praktikumi_ulesanded\"><\/span>Praktikumi \u00fclesanded<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>Selle praktikumi baas\u00fclesande k\u00e4igus pead looma kaks programmi sama \u00fclesande lahendamiseks ning v\u00f5rdlema m\u00f5lema l\u00e4henemist omavahel. Lisa\u00fclesande raames tuleb luua kolmas programm ning v\u00f5rrelda selle j\u00f5udlust kahe eelneva.<\/p>\n<h4><span class=\"ez-toc-section\" id=\"Ulesanne_W13-1_Lineaarotsingu_vordlus_kahendotsingpuuga\"><\/span><span style=\"font-size: 20px; font-weight: bold;\">\u00dclesanne [W13-1]: Lineaarotsingu v\u00f5rdlus kahendotsingpuuga<\/span><span class=\"ez-toc-section-end\"><\/span><\/h4>\n<p>Baas\u00fclesande raames tuleb luua kaks programmi. M\u00f5lemad t\u00e4idavad t\u00e4pselt sama \u00fclesannet, leides mitu korda iga nimi kordub ette antud andmefailis. Rakendused erinevad \u00fcksteisest andmestruktuuri poolest. Esimene programm kasutab d\u00fcnaamilist massiivi ja lineaarotsingut, teine programm kahendotsingpuud.<\/p>\n<ul>\n<li>Lae alla n\u00e4idisrakendused, mille p\u00f5hjal : <strong><a href=\"https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/aluskoodid\/13_trees_samples.zip\">https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/aluskoodid\/13_trees_samples.zip<\/a><\/strong><\/li>\n<li>Lae alla praktikumi\u00fclesande andmefail: <strong><a href=\"https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/andmefailid\/13_trees_random_people_city_data.zip\">https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/andmefailid\/13_trees_random_people_city_data.zip<\/a><\/strong><\/li>\n<\/ul>\n<p>Lahenda \u00fclesanded j\u00e4lgides samm-sammulist juhendit.<\/p>\n<h5><span class=\"ez-toc-section\" id=\"Uldised_nouded\"><\/span>\u00dcldised n\u00f5uded<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<ul>\n<li>Leia k\u00f5ik failis olevad nimekombinatsioonid (ees + perenimi)<\/li>\n<li>Loenda, mitu korda iga nimekombinatsioon esines<\/li>\n<li>V\u00e4ljasta leitud tulemused v\u00e4ljundfaili\n<ul>\n<li>Kasuta j\u00e4rgnevat v\u00e4ljundi struktuuri:<br \/>\n<span class=\"lang:default highlight:0 decode:true crayon-inline\">&lt;eesnimi&gt; &lt;perenimi&gt; &lt;korduste arv&gt;<\/span><\/li>\n<\/ul>\n<\/li>\n<li>Lahenda sama \u00fclesanne kahel viisil\n<ul>\n<li>Esimeses lahenduses kasuta d\u00fcnaamilist massiivi, mida laiendad jooksvalt <span class=\"lang:c highlight:0 decode:true crayon-inline \">realloc()<\/span>\u00a0 funktsiooniga<\/li>\n<li>Teises lahenduses kasuta kahendotsingpuud<\/li>\n<\/ul>\n<\/li>\n<li>Arvuta programmi sees, kui kaua kulus erinevatel etappidel aega\n<ul>\n<li>Kasuta etteantud struktuuri ja aja kuvamise funktsiooni, mis on esitatud samm-sammulises juhendis<\/li>\n<li>M\u00f5\u00f5da ja kuva, kui kaua aega kulus andmete lugemiseks, v\u00e4ljastamiseks, vabastamiseks ning kokku.<\/li>\n<\/ul>\n<\/li>\n<li>Kuva ekraanil, mitu erinevat nimekombinatsiooni programm leidis, veendu numbri \u00f5igsuses<\/li>\n<li>Optimeeri oma programmi v\u00f5imalikult palju\n<ul>\n<li>V\u00e4ldi nimekombinatsioonide ekraanile kuvamist &#8211; see on aeglane!<\/li>\n<li>Puu loomisel kasuta globaalmuutujat elementide arvu j\u00e4lgimiseks<\/li>\n<li>Kahendpuu v\u00e4ljastamisel kasuta v\u00e4ljundfaili avamiseks globaalset failiviita, fail ava ja sulge \u00fchekordselt<\/li>\n<li>Hoia nimi struktuuris staatilisena &#8211; nt <span class=\"lang:default highlight:0 decode:true crayon-inline\">char combinedName[64]<\/span><\/li>\n<\/ul>\n<\/li>\n<li>Enne lahenduse kaitsmist m\u00f5tle, kuidas vastaksid k\u00fcsimustele, mis on esitatud peat\u00fckis <a href=\"#Programmi_tooaja_vordlemine\">Programmi t\u00f6\u00f6aja v\u00f5rdlemine<\/a><\/li>\n<\/ul>\n<h5><span class=\"ez-toc-section\" id=\"Programm_1_Lineaarotsing\"><\/span>Programm 1: Lineaarotsing<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>Alustamiseks tutvu esmalt n\u00e4idisprogrammiga. Selleks ava\u00a0 \u00a0<span class=\"lang:default highlight:0 decode:true crayon-inline\">example_linear.c<\/span>\u00a0 ja \u00a0<span class=\"lang:default highlight:0 decode:true crayon-inline\">example_linear.h<\/span>\u00a0 failid ning tutvu nende \u00fclesehitusega, ehita ja k\u00e4ivita see rakendus. See saab olema su aluskood.<\/p>\n<p>M\u00e4rka, et programm kasutab k\u00e4surea argumente &#8211; st k\u00e4ivita seda j\u00e4rgnevalt:\u00a0 <span class=\"lang:default highlight:0 decode:true crayon-inline\">.\/program_name input_file_name<\/span><\/p>\n<p>Tutvus tehtud, alustame koodi muutmist enda \u00fclesandele sobivaks.<\/p>\n<ol>\n<li>Muuda lugemisfunktsioon sobilikuks \u00fclesande andmefailile\n<ul>\n<li>Praegune versioon faili lugemisest eeldab \u00fchte nime (\u00fches\u00f5naline). Tunnit\u00f6\u00f6 andmefailis on neli v\u00e4lja rea kohta &#8211; eID, first name, last name and city.<\/li>\n<li>Muuda <span class=\"lang:c highlight:0 decode:true crayon-inline \">fscanf()<\/span>\u00a0 funktsiooni sedasi, et see saaks hakkama t\u00e4iendavate v\u00e4ljadega. eID ja linna salvestada pole vaja, \u00fclesanne neid ei vaja.<\/li>\n<li>Kleebi nimi kokku kujul\u00a0 <span class=\"lang:default highlight:0 decode:true crayon-inline\">&#8220;Eesnimi Perenimi&#8221;<\/span> . Kasuta kleebitud kuju nii otsingufunktsioonis veendumaks, kas tegu on uue nimega v\u00f5i mitte, ning uue nime puhul lisa see oma andmestruktuuri.<br \/>\n<strong>Vihje:<\/strong> <span class=\"lang:default decode:true crayon-inline\">snprintf()<\/span> on k\u00f5ige lihtsam viis nime kokku kleepida.<br \/>\n<strong>Vihje:<\/strong> v\u00e4lja ignoreerimiseks saad kasutada formaati <span class=\"lang:c highlight:0 decode:true crayon-inline \">%*s<\/span><\/li>\n<\/ul>\n<\/li>\n<li>Loenda mitu korda nimi esinenud on. Loendamine toimub faili lugemise k\u00e4igus.\n<ul>\n<li>Lisa oma struktuuri kirjeldusse loendur &#8211; kasuta kas\u00a0 <span class=\"lang:default decode:true crayon-inline\">int<\/span> v\u00f5i\u00a0 <span class=\"lang:default decode:true crayon-inline \">unsigned<\/span> andmet\u00fc\u00fcpi.<\/li>\n<li>Enne kui hakkad oma loendamist kodeerima, vaata kuidas on n\u00e4itekoodis lahendatud korduvate (juba massiivis eksisteerivate) nimede tuvastamine.<br \/>\n<strong>Vihje:<\/strong> Vaata funktsiooni <span class=\"lang:default decode:true crayon-inline\">GetNameIndex()<\/span>\u00a0 tagastust. Kasuta oma koodis tagastatavat v\u00e4\u00e4rtust vajaliku funktsionaalsuse lisamiseks. <strong>Funktsiooni <span class=\"lang:default decode:true crayon-inline\">GetNameIndex()<\/span> \u00a0\u00e4ra muuda!<\/strong><\/li>\n<li>Lisa oma struktuuris paiknevale loendurile algv\u00e4\u00e4rtustamine. Seda pead tegema\u00a0<span class=\"lang:c highlight:0 decode:true crayon-inline\">ReadData()<\/span>\u00a0 funktsioonis. M\u00f5tle l\u00e4bi, millal on k\u00f5ige sobilikum hetk v\u00e4lja algv\u00e4\u00e4rtustamiseks.<\/li>\n<li>Lisaks algv\u00e4\u00e4rtustamisele peab <span class=\"lang:c highlight:0 decode:true crayon-inline\">ReadData()<\/span>\u00a0 funktsioonis lahendama loenduri v\u00e4\u00e4rtuse suurendamise, kui nimi on varasemalt juba esinenud. Selleks meenuta, mida tagastas <span class=\"lang:default decode:true crayon-inline\">GetNameIndex()<\/span> funktsioon, kui nimi oli massiivis juba olemas.<\/li>\n<\/ul>\n<\/li>\n<li>Muuda oma v\u00e4ljastuse funktsiooni\n<ol>\n<li style=\"list-style-type: none;\">\n<ul>\n<li>Asenda ekraanile tr\u00fckkimine v\u00e4ljundfaili kirjutamisega<\/li>\n<li>V\u00e4ljastus peab koosnema t\u00e4isnimest ja korduste arvust<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n<\/li>\n<li>Kuva ekraanil, mitu erinevat nimekombinatsiooni kokku esines<\/li>\n<li>Lisa andmete vabastamine<\/li>\n<li>Lisa aja m\u00f5\u00f5tmine\n<ul>\n<li>Aega on vaja m\u00f5\u00f5ta neljas punktis. Selleks on m\u00f5istlik luua uus struktuur\n<pre class=\"toolbar:2 lang:c decode:true\">struct TimePoints\r\n{\r\n    clock_t start; \/* Right before staring to read *\/\r\n    clock_t read;  \/* After the reading function finishes, before printing *\/\r\n    clock_t print; \/* After printing to file is finished *\/\r\n    clock_t free;  \/* Data structure is freed *\/\r\n};<\/pre>\n<\/li>\n<li>Paiguta oma <span class=\"lang:c highlight:0 decode:true crayon-inline \">main()<\/span>\u00a0 funktsiooni \u00f5igetesse kohtadesse ajav\u00f5tupunktid<\/li>\n<li>Aegade arvutamiseks pakume v\u00e4lja j\u00e4rgneva funktsiooni\n<pre class=\"toolbar:2 lang:c decode:true\">void PrintTime(struct TimePoints t)\r\n{\r\n    printf(\"Reading:  %9.6lf s\\n\", (double)(t.read - t.start) \/ CLOCKS_PER_SEC);\r\n    printf(\"Printing: %9.6lf s\\n\", (double)(t.print - t.read) \/ CLOCKS_PER_SEC);\r\n    printf(\"Freeing:  %9.6lf s\\n\", (double)(t.free - t.print) \/ CLOCKS_PER_SEC);\r\n    printf(\"Total:    %9.6lf s\\n\", (double)(t.free - t.start) \/ CLOCKS_PER_SEC);\r\n}<\/pre>\n<\/li>\n<\/ul>\n<\/li>\n<li>Testi esmalt oma koodi ilma valgrindita. Veendu leitud nimede arvus ja v\u00e4ljundfaili tulemustes. M\u00e4luvigade korral on soovitav esimene test teha kasutades LibASANi (<em>address sanitizer<\/em>), valgrind on aeglane.<\/li>\n<li>Kui funktsionaalselt lahendus t\u00f6\u00f6tab, testi oma koodi ka valgrindiga. Valgrindiga jooksutades peab k\u00e4sureaargument olema p\u00e4rast programmi nime. <strong>Valgrindiga v\u00f5tab rakenduse testimine \u00fcle minuti!<\/strong><br \/>\n<span class=\"lang:c highlight:0 decode:true crayon-inline\">valgrind .\/example_linear random_people_city_data.txt<\/span><\/li>\n<\/ol>\n<h5><span class=\"ez-toc-section\" id=\"Lineaarse_algoritmi_testimine\"><\/span><strong>Lineaarse algoritmi testimine<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>Programmi v\u00e4ljundis on oluline j\u00e4lgida leitud erinevate kombinatsioonide arvu ning programmi erinevateks osadeks kulunud aegu. Erinevate aegade suhtes tuleks kriitiliselt hinnata nende realistlikkust.<\/p>\n<pre class=\"theme:cisco-router toolbar:2 nums:false lang:c highlight:0 decode:true\">risto@risto-tux:~\/$ .\/solution_linear random_people_city_data.txt \r\nFound 27454 names\r\n\r\nReading:   3.711664 s\r\nPrinting:  0.001027 s\r\nFreeing:   0.000049 s\r\nTotal:     3.712740 s<\/pre>\n<p>Loendamise korrektsuses veendumiseks vaata andmefaili algust. J\u00e4rgnevalt on esitatud andmefaili esimeste ridade n\u00e4ide.<\/p>\n<pre class=\"toolbar:2 lang:default highlight:0 decode:true\">Anna Martinson 6\r\nMoonika Vares 7\r\nValeri Teder 5\r\nLiisbeth Sild 7\r\nAnne Koort 5\r\nMarika Koppel 4\r\nTiit Valk 5\r\nKerttu Kuusik 10\r\nMaarja Lenk 8\r\nMaris Jalakas 9\r\nJevgeni Kangro 9\r\nMeelis Tiidus 10\r\nGalina Moroz 6\r\nOleg Ligi 10\r\nLiis Kuningas 8\r\n...<\/pre>\n<p>Kui programm on funktsionaalne, ajad realistlikud ja v\u00e4ljundid korrektsed, testi \u00fcle ka valgrindiga veendumaks m\u00e4luvigade puudumist.\u00a0 <strong>See v\u00f5ib v\u00f5tta minutike-kaks!<\/strong><\/p>\n<h5><span class=\"ez-toc-section\" id=\"Programm_2_Kahendotsingpuu\"><\/span>Programm 2: Kahendotsingpuu<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>Alustuseks ava n\u00e4iteprogramm\u00a0 <span class=\"lang:default highlight:0 decode:true crayon-inline\">example_bin_search_tree.c<\/span> ning tutvu selle \u00fclesehitusega. K\u00e4ivita programm, tutvu selle v\u00e4ljundiga.\u00a0 See saab olema su aluskood.<\/p>\n<p>M\u00e4rka, et programm kasutab k\u00e4surea argumente &#8211; st k\u00e4ivita seda j\u00e4rgnevalt:\u00a0 <span class=\"lang:default highlight:0 decode:true crayon-inline\">.\/program_name input_file_name<\/span><\/p>\n<p>Tutvus tehtud, alustame koodi muutmist enda \u00fclesandele sobivaks. Eesm\u00e4rk on saavutada t\u00e4pselt sama funktsionaalsus nagu esimese programmiga.<\/p>\n<ol>\n<li>Uuenda struktuuri kirjeldust. Sul on vaja hoida seal nii s\u00f5ne kui loendurit, t\u00e4pselt nagu lineaarse otsingu puhul.<\/li>\n<li>Uuenda oma lugemisfunktsioon samal p\u00f5him\u00f5ttel nagu lineaarse otsinguga\n<ul>\n<li>Muuda <span class=\"lang:c highlight:0 decode:true crayon-inline \">fscanf()<\/span>\u00a0 funktsiooni toetamaks failis olevat nelja parameetrit.<\/li>\n<li>Kleebi ees- ja perenimi kokku.<\/li>\n<\/ul>\n<\/li>\n<li>Uuenda lisamise funktsiooni <span class=\"lang:c highlight:0 decode:true crayon-inline \">InsertNode()<\/span>\n<ul>\n<li>Muuda andmet\u00fc\u00fcpi &#8211; n\u00e4idiskoodis lisatakse puusse t\u00e4isarv, meie lahenduses tuleb lisada nimi<\/li>\n<li>Muuda v\u00f5rdlemise operatsiooni s\u00f5nedele sobilikuks. Pane t\u00e4hele, et erinevalt n\u00e4itekoodist peame meie tuvastama ka olukorra, kui puus nimi juba eksisteerib. Sellisel juhul peame loendurit uuendama.<\/li>\n<\/ul>\n<\/li>\n<li>Uuenda uue tipu loomise funktsiooni <span class=\"lang:default highlight:0 decode:true crayon-inline\">CreateNode()<\/span>\n<ul>\n<li>Muuda parameetrit, et sinna saaks edastada s\u00f5ne (inimese t\u00e4isnime)<\/li>\n<li>Lisa struktuuris oleva loenduri (nime korduste arv) algv\u00e4\u00e4rtustamine<\/li>\n<\/ul>\n<\/li>\n<li>Uuenda puu v\u00e4ljastamise funktsiooni <span class=\"lang:default highlight:0 decode:true crayon-inline\">PrintTree()<\/span>\n<ul>\n<li>Vii sisse uuendused l\u00e4htuvalt muudetud andmestruktuurist<\/li>\n<li>NB! Kuna meie eesm\u00e4rgiks on kiire programm, siis tuleks failiviit luua globaalse muutujana. Fail ava enne v\u00e4ljastuse funktsiooni v\u00e4ljakutset ning sulge p\u00e4rast funktsiooni t\u00f6\u00f6 l\u00f5ppu.<\/li>\n<li>Muuda puu l\u00e4bik\u00e4iku. N\u00e4itekoodis on puu l\u00e4bik\u00e4iguks valitud eesj\u00e4rjestus. Leia selline l\u00e4bik\u00e4igu meetod, mille puhul oleks vastus sorteeritud t\u00e4hestikulises j\u00e4rjekorras. L\u00e4bik\u00e4igu muutmiseks pead vahetama rekursiivsete kutsete ja praeguse liikme v\u00e4ljastamise j\u00e4rjekorda.<\/li>\n<\/ul>\n<\/li>\n<li>Realiseeri vabastamise funktsioon\n<ul>\n<li>Nii nagu k\u00f5ik puu funktsioonid, peab ka vabastamine olema rekursiivne. V\u00f5ta inspiratsiooni puu v\u00e4ljastamise funktsioonist. <strong>NB!<\/strong> Oluline on valida \u00f5ige puu l\u00e4bik\u00e4igu meetod (ees-, l\u00f5pp- v\u00f5i keskj\u00e4rjestus). Valesti valitud j\u00e4rjestuse\u00a0 puhul ei ole v\u00f5imalik puud vabastada.<\/li>\n<\/ul>\n<\/li>\n<li>Lisa aja m\u00f5\u00f5tmine samamoodi nagu tegime seda lineaarse programmi korral &#8211; k\u00f5ik k\u00e4sud, andmestruktuur ja v\u00e4ljastus on t\u00e4pselt samasugused.<\/li>\n<li>Testi oma koodi nii valgrindiga kui ilma. Valgrindiga jooksutades peab k\u00e4sureaargument olema p\u00e4rast programmi nime, nt <span class=\"lang:c highlight:0 decode:true crayon-inline\">valgrind .\/programm andmefail<\/span><\/li>\n<\/ol>\n<h5><span class=\"ez-toc-section\" id=\"Kahendotsingpuu_testimine\"><\/span><strong>Kahendotsingpuu testimine<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>Testimise jaoks oleme alamosadeks kulunud aja j\u00e4tnud esitamata, et j\u00e4tta nende tulemuste hindamine ja v\u00f5rdlemine lineaarse algoritmiga sinu \u00fclesandeks. See on ka osa \u00fclesande kaitsmisest. Olenemata algoritmist peab leitud nimekombinatsioonide arv olema sama, st 27454.<\/p>\n<p>K\u00fcll aga pakume v\u00e4ljav\u00f5tet kahendotsingpuu poolt loodavast andmefailist. V\u00f5rdle enda andmefaili algust j\u00e4rgneva tulemusega.<\/p>\n<pre class=\"toolbar:2 lang:default highlight:0 decode:true\">Aili Aas 3\r\nAili Aasa 6\r\nAili Aavik 6\r\nAili Allik 4\r\nAili Allikas 7\r\nAili Alliksoo 5\r\nAili Anvelt 10\r\nAili Arro 7\r\nAili Aru 5\r\nAili Aus 3\r\nAili Hansen 6\r\nAili Hein 4\r\nAili Heinsoo 7\r\nAili Helme 6\r\n...<\/pre>\n<h5><span class=\"ez-toc-section\" id=\"Programmide_tooaja_vordlemine\"><\/span>Programmide t\u00f6\u00f6aja v\u00f5rdlemine<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>N\u00fc\u00fcd v\u00f5rdle m\u00f5lema programmi ajakulu.<\/p>\n<ul>\n<li>Kumb on kiirem, kumb on aeglasem?<\/li>\n<li>Kas m\u00f5ned rakenduse alamosad on puu ja lineaarse struktuuri v\u00f5rdluses ajaliselt m\u00e4rkimisv\u00e4\u00e4rselt erinevad?<\/li>\n<li>Kas \u00fcks v\u00f5i teine lahendus on l\u00e4bivalt teisest aeglasem?<\/li>\n<li>\u00c4ra unusta iga k\u00fcsimuse juures ka oma m\u00f5ttek\u00e4ike laiendamast!<\/li>\n<\/ul>\n<p>M\u00f5tle, kuidas v\u00f5iksid j\u00e4rgnevad muudatused m\u00f5jutada programmide t\u00f6\u00f6aega!<\/p>\n<ul>\n<li>Kahendotsingpuu lahendus sisaldab veel \u00fchte t\u00e4iendavat funktsionaalsust, mida lineaarne otsing ei sisalda. Mis funktsionaalsusega on tegu ning kuidas see m\u00f5jutaks lineaarset otsingut t\u00e4iendavalt?<\/li>\n<li>Kuidas muutuks lineaarse programmi t\u00f6\u00f6aeg, kui muudaksid <span class=\"lang:default highlight:0 decode:true crayon-inline\">realloc()<\/span>\u00a0 m\u00e4lu laiendamise strateegia (n + 1) pealt (n * 2) peale.<\/li>\n<li>Kuidas oleksid m\u00f5lemad programmid m\u00f5jutatud, kui erinevate nimekombinatsioonide arv suureneks m\u00e4rkimisv\u00e4\u00e4rselt? Katsu end v\u00e4ljendada<em>\u00a0Big O<\/em> notatsiooni kasutades (<a href=\"https:\/\/www.bigocheatsheet.com\">https:\/\/www.bigocheatsheet.com<\/a>)<\/li>\n<li>Kuidas oleksid m\u00f5lemad programmid m\u00f5jutatud, kui korduste arvud suureneksid m\u00e4rkimisv\u00e4\u00e4rselt, kuid erinevate kirjete arv j\u00e4\u00e4ks samaks?<\/li>\n<li>Kuidas m\u00f5jutaks puu tasakaalustamine lahendust?\n<ul>\n<li>Kas ja mil m\u00e4\u00e4ral v\u00f5iks see m\u00f5jutada rakenduse t\u00f6\u00f6kiirust?<\/li>\n<li>Mis on k\u00f5ige halvem v\u00f5imalik olukord tasakaalustamata kahendotsingpuu jaoks?<\/li>\n<\/ul>\n<\/li>\n<li>Kui lahendasid ka lisa\u00fclesande, kaasa samasse v\u00f5rdlusse ka trie andmestruktuur. Kas sellel on ka m\u00f5ni m\u00e4rkimisv\u00e4\u00e4rne eelis tavalise kahendotsingpuu ees?<\/li>\n<\/ul>\n<h4><span class=\"ez-toc-section\" id=\"Lisaulesanne_W13-2_Trie_puu\"><\/span>Lisa\u00fclesanne [W13-2]: Trie puu<span class=\"ez-toc-section-end\"><\/span><\/h4>\n<p>Loo kolmas programm ning v\u00f5rdle selle efektiivsust eelneva kahe programmiga. Kasuta kolmandas rakenduses trie andmestruktuuri.<\/p>\n<p>K\u00f5ik teised n\u00f5uded j\u00e4\u00e4vad samaks.<\/p>\n<h5><span class=\"ez-toc-section\" id=\"Soovituslik_andmestruktuur\"><\/span>Soovituslik andmestruktuur<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>Kasutame muudetud versiooni slaididel olnud n\u00e4idisest. Asendame struktuuris oleva t\u00f5ev\u00e4\u00e4rtuse ( <span class=\"lang:default decode:true crayon-inline\">isLeaf<\/span> ), mis n\u00e4itas s\u00f5ne l\u00f5ppu, hoopis t\u00e4isarvulise v\u00e4\u00e4rtusega. Kui v\u00e4\u00e4rtus on 0, siis selles asukohas nime l\u00f5ppu ei ole. Kui v\u00e4\u00e4rtus on nullist suurem, siis on tegu lehega, mis t\u00e4histab nime. Number \u00fctleb, mitu korda nimi failis eksisteeris.<\/p>\n<pre class=\"lang:default decode:true \">typedef struct TrieNode\r\n{\r\n    char ch;\r\n    int count;\r\n    struct TrieNode *chars[ALPHA_LEN];\r\n} Trie;\r\n<\/pre>\n<p>Vihje 1: Lisaks t\u00e4hestikule arvesta ka t\u00fchiku ja miinuse s\u00fcmboliga. M\u00f5lemad neist on olemas andmefailis. T\u00e4iendavaid eris\u00fcmboleid failis ei ole.<\/p>\n<p>Vihje 2: Andmestruktuuri v\u00e4ljade algv\u00e4\u00e4rtustamine <span class=\"lang:c highlight:0 decode:true crayon-inline \">CreateNode()<\/span>\u00a0 funktsioonis on \u00e4\u00e4rmiselt t\u00e4htis. Algv\u00e4\u00e4rtusta nii loendur kui kogu viitade massiiv.<\/p>\n<h3><span class=\"ez-toc-section\" id=\"Parast_seda_tundi_peaksid\"><\/span>P\u00e4rast seda tundi peaksid<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<ul>\n<li>Oskama m\u00f5\u00f5ta rakenduse t\u00f6\u00f6aega programmisiseselt ja s\u00fcsteemse t\u00f6\u00f6riistaga<\/li>\n<li>Teadma, kuidas seostuvad omavahel kerneli aeg, kasutaja aeg ning reaalne aeg<\/li>\n<li>Teadma, mis v\u00f5ib juhtuda, kui k\u00f5ik s\u00fcsteemis t\u00f6\u00f6tavad protsessid ei mahu enam arvuti p\u00f5him\u00e4llu \u00e4ra<\/li>\n<li>Teadma erinevaid kompilaatori optimeerimise tasemeid ning lihtsamal tasemel, mis eeliseid ja probleeme optimeerimine v\u00f5ib tuua<\/li>\n<li>Teadma puudega seotud m\u00f5isteid nagu tipp, juur, leht, k\u00f5rgus jne<\/li>\n<li>Teadma puu liike ja nendega seotud omadusi (kahendpuu, kahendotsingpuu ning tasakaalustatud kahendpuu)<\/li>\n<li>Teadma erinevaid puu l\u00e4bik\u00e4igu viise (eesj\u00e4rjestus, keskj\u00e4rjestus, l\u00f5ppj\u00e4rjestus) ning nende kasutusjuhte &#8211; st milleks iga l\u00e4bik\u00e4igumeetod sobilik on<\/li>\n<li>Oskama kahendpuu kasutamiseks luua rekursiivseid funktsioone andmete lisamiseks, otsimiseks ja kustutamiseks<\/li>\n<li>Teadma Trie puu omadusi, kasutusvaldkonda ja struktuuri<\/li>\n<\/ul>\n<h3><span class=\"ez-toc-section\" id=\"Taiendav_materjal\"><\/span>T\u00e4iendav materjal<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<ul>\n<li>Binary search tree<br \/>\n<strong><a href=\"https:\/\/www.geeksforgeeks.org\/binary-search-tree-data-structure\/\">https:\/\/www.geeksforgeeks.org\/binary-search-tree-data-structure\/<\/a><\/strong><\/li>\n<li>Binary search tree visualization<br \/>\n<strong><a href=\"https:\/\/www.cs.usfca.edu\/~galles\/visualization\/BST.html\">https:\/\/www.cs.usfca.edu\/~galles\/visualization\/BST.html<\/a><\/strong><\/li>\n<li>Trashing<br \/>\n<a href=\"https:\/\/en.wikipedia.org\/wiki\/Thrashing_(computer_science)\"><strong>https:\/\/en.wikipedia.org\/wiki\/Thrashing_(computer_science)<\/strong><\/a><\/li>\n<li>Algoritmid ja andmestruktuurid (Tartu \u00dclikool)<br \/>\n<strong><a href=\"https:\/\/dspace.ut.ee\/bitstream\/handle\/10062\/16872\/9985567676.pdf\">https:\/\/dspace.ut.ee\/bitstream\/handle\/10062\/16872\/9985567676.pdf<\/a><\/strong><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Praktikumi materjal Slaidid: Puud Praktikumi \u00fclesanded Selle praktikumi baas\u00fclesande k\u00e4igus pead looma kaks programmi sama \u00fclesande lahendamiseks ning v\u00f5rdlema m\u00f5lema l\u00e4henemist omavahel. Lisa\u00fclesande raames tuleb luua kolmas programm ning v\u00f5rrelda selle j\u00f5udlust kahe eelneva. \u00dclesanne [W13-1]: Lineaarotsingu v\u00f5rdlus kahendotsingpuuga Baas\u00fclesande raames tuleb luua kaks programmi. M\u00f5lemad t\u00e4idavad t\u00e4pselt sama \u00fclesannet, leides mitu korda iga nimi &hellip; <a href=\"https:\/\/blue.pri.ee\/ttu\/laborid\/pr2et13-puud\/\" class=\"more-link\">Loe edasi <span class=\"screen-reader-text\">PR2ET13: Puud<\/span> <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[97,176],"tags":[],"class_list":["post-8570","post","type-post","status-publish","format-standard","hentry","category-laborid","category-pr2-et"],"_links":{"self":[{"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/posts\/8570","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/comments?post=8570"}],"version-history":[{"count":35,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/posts\/8570\/revisions"}],"predecessor-version":[{"id":10054,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/posts\/8570\/revisions\/10054"}],"wp:attachment":[{"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/media?parent=8570"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/categories?post=8570"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/tags?post=8570"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}