{"id":8572,"date":"2023-04-23T15:47:34","date_gmt":"2023-04-23T13:47:34","guid":{"rendered":"https:\/\/blue.pri.ee\/ttu\/?p=8572"},"modified":"2026-04-24T10:40:12","modified_gmt":"2026-04-24T08:40:12","slug":"pr2en13-trees","status":"publish","type":"post","link":"https:\/\/blue.pri.ee\/ttu\/labs\/pr2en13-trees\/","title":{"rendered":"PR2EN13: Trees"},"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\/labs\/pr2en13-trees\/#Lab_materials\" >Lab materials<\/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\/labs\/pr2en13-trees\/#Lab_tasks\" >Lab tasks<\/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\/labs\/pr2en13-trees\/#Lab_task_W13-1_Comparing_performance_of_linear_search_and_binary_search_tree\" >Lab task [W13-1]: Comparing performance of linear search and binary search tree<\/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\/labs\/pr2en13-trees\/#Requirements\" >Requirements<\/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\/labs\/pr2en13-trees\/#Program_1_Linear_search\" >Program 1: Linear search<\/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\/labs\/pr2en13-trees\/#Testing_the_linear_algorithm\" >Testing the linear algorithm<\/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\/labs\/pr2en13-trees\/#Program_2_Binary_search_tree\" >Program 2: Binary search tree<\/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\/labs\/pr2en13-trees\/#Testing_binary_search_tree\" >Testing binary search tree<\/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\/labs\/pr2en13-trees\/#Comparing_runtime_for_programs\" >Comparing runtime for programs<\/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\/labs\/pr2en13-trees\/#Extra_task_W13-2_Trie_implementation\" >Extra task [W13-2]: Trie implementation<\/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\/labs\/pr2en13-trees\/#Recommended_data_structure\" >Recommended data structure<\/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\/labs\/pr2en13-trees\/#After_this_class_you_should\" >After this class, you should<\/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\/labs\/pr2en13-trees\/#Additional_materials\" >Additional materials<\/a><\/li><\/ul><\/nav><\/div>\n<h3><span class=\"ez-toc-section\" id=\"Lab_materials\"><\/span>Lab materials<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<ul>\n<li>Slides: <a href=\"https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/slaidid-en\/13_trees.pdf\"><strong>Tr<\/strong><strong>e<\/strong><strong>es<\/strong><\/a><\/li>\n<\/ul>\n<h3><span class=\"ez-toc-section\" id=\"Lab_tasks\"><\/span>Lab tasks<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>This lab has a base task that requires you to write two programs, both performing the same task. Once written, you need to compare the performance of those two tasks. Extra task has you adding a third solution and adding it to the comparison.<\/p>\n<h4><span class=\"ez-toc-section\" id=\"Lab_task_W13-1_Comparing_performance_of_linear_search_and_binary_search_tree\"><\/span><span style=\"font-size: 20px; font-weight: bold;\">Lab task [W13-1]: Comparing performance of linear search and binary search tree<\/span><span class=\"ez-toc-section-end\"><\/span><\/h4>\n<p>For this task, you will create two programs. Both of them will count how many times each name combination occurred in the data file. For the first program, we will implement a linear search algorithm using a dynamic array as the data structure. For the second one, we will create a binary search tree.<\/p>\n<ul>\n<li>Download the sample applications you will base your lab task on: <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>Download the lab task data file: <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>The lab should be completed by following the step-by-step guide provided.<\/p>\n<h5><span class=\"ez-toc-section\" id=\"Requirements\"><\/span>Requirements<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<ul>\n<li>Find all the name combinations (first + last name) in the data file<\/li>\n<li>Count the number of times each name combination occurred in the provided data file<\/li>\n<li>Print the results in an output file\n<ul>\n<li>Use the following structure for the output:<br \/>\n<span class=\"lang:default highlight:0 decode:true crayon-inline\">&lt;first name&gt; &lt;last name&gt; &lt;count&gt;<\/span><\/li>\n<\/ul>\n<\/li>\n<li>Provide two solutions for the same task\n<ul>\n<li>First one uses a dynamic array that is expanded using <span class=\"lang:c highlight:0 decode:true crayon-inline \">realloc()<\/span><\/li>\n<li>Second one uses a binary search tree<\/li>\n<\/ul>\n<\/li>\n<li>Print the number of different name combinations on the screen<\/li>\n<li>Optimize your program\n<ul>\n<li>When building the binary tree, use<\/li>\n<\/ul>\n<\/li>\n<li>Calculate the time it took your program to process the data\n<ul>\n<li>The calculation must at least include reading from the file and creation of the data structure.<\/li>\n<li>You can also include printing and freeing.<\/li>\n<li>Results must be comparable &#8211; if one program includes freeing in the time calculation, so must the other.<\/li>\n<\/ul>\n<\/li>\n<li>Focus on performance\n<ul>\n<li>Avoid printing the list on the screen &#8211; this has a large performance penalty<\/li>\n<li>When creating the binary tree, use a global variable to count the number of elements<\/li>\n<li>For printing the results in the binary tree, use a global file pointer that is only opened and closed once during the entire program.<\/li>\n<li>Leave the name variable in the struct statically declared &#8211; i.e. <span class=\"lang:default highlight:0 decode:true crayon-inline\">char combinedName[64]<\/span><\/li>\n<\/ul>\n<\/li>\n<li>Before defending, prepare answers for the questions presented in the chapter\u00a0<a href=\"#Comparing_time\">#Comparing_time<\/a><\/li>\n<\/ul>\n<h5><span class=\"ez-toc-section\" id=\"Program_1_Linear_search\"><\/span>Program 1: Linear search<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>To begin, open up the <span class=\"lang:default highlight:0 decode:true crayon-inline\">example_linear.c<\/span>\u00a0 and <span class=\"lang:default highlight:0 decode:true crayon-inline\">example_linear.h<\/span> . Familiarize yourself with the code. Try to run it and look at the output. This will become your starter code for the first program.<\/p>\n<p>Also notice that the program uses a command line arguments. To execute, use <span class=\"lang:default highlight:0 decode:true crayon-inline\">.\/program_name input_file_name<\/span><\/p>\n<p>Once you&#8217;ve familiarized yourself with the example code, you need to start modifying the code to fit the task.<\/p>\n<ol>\n<li>Alter the data reading function\n<ul>\n<li>The current reading function works with a single name (one word). The lab task data file contains 4 fields per row &#8211; eID, first name, last name and city.<\/li>\n<li>Alter the <span class=\"lang:default highlight:0 decode:true crayon-inline\">fscanf()<\/span>\u00a0 function call to work with the extra fields. You can immediately discard the eID and city &#8211; they won&#8217;t be needed.<\/li>\n<li>Concatenate the name as <span class=\"lang:default highlight:0 decode:true crayon-inline\">&#8220;Firstname Lastname&#8221;<\/span> . The concatenated form is used to both compare with the existing names and to store the name into the struct<br \/>\n<strong>Hint:<\/strong> <span class=\"lang:default decode:true crayon-inline\">snprintf()<\/span> helps to combine the name<br \/>\n<strong>Hint:<\/strong> <span class=\"lang:c highlight:0 decode:true crayon-inline \">%*s<\/span>\u00a0 format can be used to discard a field<\/li>\n<\/ul>\n<\/li>\n<li>Count the number of times a name combination is present in the data file. Counting is done during reading of the data\n<ul>\n<li>Add the counter variable to the struct. Both\u00a0 <span class=\"lang:default decode:true crayon-inline\">int<\/span>\u00a0or <span class=\"lang:default decode:true crayon-inline \">unsigned<\/span>\u00a0 will work.<\/li>\n<li>Before going forward, look at how the provided example code finds non-recurrent values<br \/>\n<strong>Hint:<\/strong> look at the return value of <span class=\"lang:default decode:true crayon-inline\">GetNameIndex()<\/span>\u00a0 function provided in the code. Make use of the return value,<strong>\u00a0do not alter the <span class=\"lang:c highlight:0 decode:true crayon-inline \">GetNameIndex()<\/span>\u00a0 function itself!<\/strong><\/li>\n<li>The counter that was added to the struct needs to be initialized. Do it in the <span class=\"lang:c highlight:0 decode:true crayon-inline\">ReadData()<\/span>\u00a0\u00a0function. Think about when this initialization needs to occur!<\/li>\n<li><span class=\"lang:c highlight:0 decode:true crayon-inline\">ReadData()<\/span>\u00a0 also needs to handle updating the counter when the name is already present in the database (think about what\u00a0<span class=\"lang:default decode:true crayon-inline \">GetNameIndex()<\/span>\u00a0 returns when the name was found in the array).<\/li>\n<\/ul>\n<\/li>\n<li>Update the print function.\n<ul>\n<li>Alter the printing statements so that the list of names would be printed to a file<\/li>\n<li>Change what is being printed, so it would also include the number of times a name occurred.<\/li>\n<\/ul>\n<\/li>\n<li>Add a print statement that displays how many different names were in the data file<\/li>\n<li>Add freeing of the struct memory<\/li>\n<li>Add the timers\n<ul>\n<li>Time needs to be measured in four different points. For this, it&#8217;s best to create a new structure\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>Place time checkpoints in your <span class=\"lang:c highlight:0 decode:true crayon-inline \">main()<\/span>\u00a0 function to the appropriate locations<\/li>\n<li>To calculate the appropriate time intervals, the following function is proposed\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>Test your code without valgrind first, check the count and the output file.<\/li>\n<li>Once the functionality is working, test the program with valgrind. When running in valgrind, you need to write arguments to valgrind before the executable and arguments for your program in the end. <strong>Running with valgrind will take approximately 1 minute to complete!<\/strong><br \/>\nE.g. <span class=\"lang:default decode:true crayon-inline\">valgrind .\/example_linear random_people_city_data.txt<\/span><\/li>\n<\/ol>\n<h5><span class=\"ez-toc-section\" id=\"Testing_the_linear_algorithm\"><\/span><strong>Testing the linear algorithm<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>When testing the program, the\u00a0 two things to look for in the output is the number of different name combinations it found and the time it took for different parts of the program. Pay attention to the subparts and think critically whether they are realistic or not!<\/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>To validate the name counts, we&#8217;ve listed the beginning of the output file so you can compare it to yours.<\/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>Once you&#8217;ve made sure that the results are functionally correct, test the memory correctness using valgrind. This will take over a minute to run!<\/p>\n<h5><span class=\"ez-toc-section\" id=\"Program_2_Binary_search_tree\"><\/span>Program 2: Binary search tree<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>To begin, open up the <span class=\"lang:default highlight:0 decode:true crayon-inline \">example_bin_search_tree<\/span><span class=\"lang:default highlight:0 decode:true crayon-inline\">.c<\/span>\u00a0 and <span class=\"lang:default highlight:0 decode:true crayon-inline \">example_bin_search_tree<\/span><span class=\"lang:default highlight:0 decode:true crayon-inline\">.h<\/span> . Familiarize yourself with the code. Try to run it and look at the output. This will become your starter code for the first program.<\/p>\n<p>Also notice that the program uses a command line arguments. To execute, use <span class=\"lang:default highlight:0 decode:true crayon-inline\">.\/program_name input_file_name<\/span><\/p>\n<p>Once you&#8217;ve familiarized yourself with the example code, you need to start modifying the code to fit the task. The goal is to solve the same task, but by using a binary search tree.<\/p>\n<ol>\n<li>Alter the struct. You need to store the name and a counter, just as with linear search<\/li>\n<li>Alter the reading function similarly to what we did with linear search\n<ul>\n<li>Modify the <span class=\"lang:c highlight:0 decode:true crayon-inline\">fscanf()<\/span>\u00a0 statement to read 4 fields, you will only need the first and last name fields.<\/li>\n<li>Concatenate the name so you can store it in a single variable.<\/li>\n<\/ul>\n<\/li>\n<li>Update the function responsible for inserting nodes to the tree, i.e. <span class=\"lang:c highlight:0 decode:true crayon-inline \">InsertNode()<\/span>\n<ul>\n<li>Change the function parameter &#8211; the example inserts integers to the tree, we need to insert a string<\/li>\n<li>Change the comparison statements to work with strings (instead of integers). Make sure not to cause any unnecessary performance penalties while doing so!<\/li>\n<li>Note what happens when you try to insert a value that already exists in the tree &#8211; the example code will ignore it and not do anything. The final solution can&#8217;t ignore it. If the name already exists, we need to count up the number of times it occurred! Add an update to the counter!<\/li>\n<\/ul>\n<\/li>\n<li>Update the function responsible for allocating a new tree node, i.e. <span class=\"lang:default highlight:0 decode:true crayon-inline \">CreateNode()<\/span>\n<ul>\n<li>Change the parameter type to suit the task<\/li>\n<li>Add an initialization to the counter<\/li>\n<\/ul>\n<\/li>\n<li>Update the <span class=\"lang:default highlight:0 decode:true crayon-inline \">PrintTree()<\/span>\u00a0 function\n<ul>\n<li>Make alterations to work with the updated data structure<\/li>\n<li>Note: because we are time optimizing the solution, you should make the <span class=\"lang:default highlight:0 decode:true crayon-inline\">FILE *<\/span>\u00a0 pointer as a global variable. Open the file before calling this function and close it after.<\/li>\n<li>The sample print function is using &#8220;pre-order&#8221; traversal. Change the traversal mode to such that the tree would be printed in the alphabetical order. For this you need to change the order of the statements are executed to print the current node and the recursive calls to the child nodes.<\/li>\n<\/ul>\n<\/li>\n<li>Implement a free function for the data structure\n<ul>\n<li>Just as any tree function, this also has to be a recursive function. Take inspiration from the <span class=\"lang:c highlight:0 decode:true crayon-inline\">PrintTree()<\/span>\u00a0 function for how to traverse nodes. <strong>NB!<\/strong> You need to pick the correct traversal (pre-, in- or post-order) for the freeing to be correctly performed!<\/li>\n<\/ul>\n<\/li>\n<li>Add the time measurements. This can be implemented exactly the same way as you did with the linear data structure. All statements, the data structure and the print function remain the same.<\/li>\n<li>Run your code through valgrind. You can also use command line arguments with valgrind.<br \/>\nE.g. <span class=\"lang:default decode:true crayon-inline\">valgrind .\/example_bin_search_tree random_people_city_data.txt<\/span><\/li>\n<\/ol>\n<h5><span class=\"ez-toc-section\" id=\"Testing_binary_search_tree\"><\/span><strong>Testing binary search tree<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>For this testing section, we are not showing you the time intervals we got on our solution. The task of analyzing the measured time (are they realistic?) and comparing the time intervals is left as a task for you. This is also a part of the task defense.<\/p>\n<p>Regardless of the algorithm, the number of name combinations needs to be the same, i.e. 27454.<\/p>\n<p>We do offer you a look into the data file. Compare the beginning of the data file from our solution with yours!<\/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=\"Comparing_runtime_for_programs\"><\/span>Comparing runtime for programs<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>Once we&#8217;re sure about the correctness of our programs, let&#8217;s compare the runtime of both of them.<\/p>\n<ul>\n<li>Which program was faster, which slower?<\/li>\n<li>Was one program faster than the other one in all aspects or were there differences?<\/li>\n<li>Were there any sub components of either of the programs that took significantly different amount of time?<\/li>\n<li>Don&#8217;t forget to elaborate your answers!<\/li>\n<\/ul>\n<p>Also think about how the following could affect the runtime of the programs<\/p>\n<ul>\n<li>The binary search tree solution contains one feature that the linear search does not have.\n<ul>\n<li>Which functionality is this?<\/li>\n<li>How would linear search be affected if this functionality would be added?<\/li>\n<\/ul>\n<\/li>\n<li>How would the runtime be affected by changing the <span class=\"lang:c highlight:0 decode:true crayon-inline \">realloc()<\/span>\u00a0 strategy from (n + 1) to (n * 2)?<\/li>\n<li>How would the programs be affected by the increase of different (non-recurrent) name combinations . Try to express it in terms of the Big O notation (<a href=\"https:\/\/www.bigocheatsheet.com\">https:\/\/www.bigocheatsheet.com<\/a>)<\/li>\n<li>How would the programs be affected by increase of recurrences, when the number of different name combinations would remain the same?<\/li>\n<li>Think about balancing of the tree\n<ul>\n<li>Would balancing the tree affect the performance?<\/li>\n<li>What is the worst case scenario for the binary search tree (without balancing)?<\/li>\n<\/ul>\n<\/li>\n<li>If you solved the extra task with Trie, add it to the comparisons.<\/li>\n<\/ul>\n<h4><span class=\"ez-toc-section\" id=\"Extra_task_W13-2_Trie_implementation\"><\/span>Extra task [W13-2]: Trie implementation<span class=\"ez-toc-section-end\"><\/span><\/h4>\n<p>Create a third program to compare the efficiency. Use the trie data structure.<\/p>\n<p>All the other requirements remain the same.<\/p>\n<h5><span class=\"ez-toc-section\" id=\"Recommended_data_structure\"><\/span>Recommended data structure<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>Compared to the sample on the slides, we don&#8217;t use a boolean true\/false value to denote the end of a string (e.g. <span class=\"lang:default decode:true crayon-inline \">isLeaf<\/span> ). Instead, we use a counter. If the counter is 0, we consider it not to be a leaf node, if the counter is &gt; 0, it&#8217;s a leaf node where a name ends.<\/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>Hint 1: your alphabet length should also include positions for a space and a minus symbol, which are present in the names. No other special symbols are used in the file.<\/p>\n<p>Hint 2: Initialization in the <span class=\"lang:c highlight:0 decode:true crayon-inline \">CreateNode()<\/span>\u00a0 is crucial for both the counter and the pointer array.<\/p>\n<h3><span class=\"ez-toc-section\" id=\"After_this_class_you_should\"><\/span>After this class, you should<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<ul>\n<li>Be able to measure an application&#8217;s runtime internally within the program and by using a system tools<\/li>\n<li>Know how kernel time, user time, and real time are related and what they are<\/li>\n<li>Know what may happen if all processes running in parallel on the system no longer fit into the computer&#8217;s main memory<\/li>\n<li>Know the different compiler optimization levels and, at a basic level, the advantages and problems that optimization can bring<\/li>\n<li>Know concepts related to trees, such as node, root, leaf, height, etc.<\/li>\n<li>Know the types of trees and their properties (binary tree, binary search tree, and balanced binary tree)<\/li>\n<li>Know different tree traversal methods (preorder, inorder, postorder) and their use cases \u2014 when to use which traversal method<\/li>\n<li>Be able to create recursive functions for adding, searching, and deleting data in a binary tree<\/li>\n<li>Know the properties, application areas, and structure of a Trie data structure<\/li>\n<\/ul>\n<h3><span class=\"ez-toc-section\" id=\"Additional_materials\"><\/span>Additional materials<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<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Lab materials Slides: Trees Lab tasks This lab has a base task that requires you to write two programs, both performing the same task. Once written, you need to compare the performance of those two tasks. Extra task has you adding a third solution and adding it to the comparison. Lab task [W13-1]: Comparing performance &hellip; <a href=\"https:\/\/blue.pri.ee\/ttu\/labs\/pr2en13-trees\/\" class=\"more-link\">Loe edasi <span class=\"screen-reader-text\">PR2EN13: Trees<\/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":[75,105],"tags":[],"class_list":["post-8572","post","type-post","status-publish","format-standard","hentry","category-labs","category-pr2_en"],"_links":{"self":[{"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/posts\/8572","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=8572"}],"version-history":[{"count":16,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/posts\/8572\/revisions"}],"predecessor-version":[{"id":11398,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/posts\/8572\/revisions\/11398"}],"wp:attachment":[{"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/media?parent=8572"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/categories?post=8572"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/tags?post=8572"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}