ANSWER IN C LANGUAGE PLEASE
Part 1:You need to define abinary search tree data structure .Also, you need to implement the following functions:
1.Insert Sorted
·BSTREE insert(BSTREE root, int num): root points to a node in a binary search tree; num is a number to be inserted in the tree rooted at “root”. This function returns the root of the modified tree.
2.Print Elements
·void inorderTraversal(BSTREE root, FILE *fp): root points to a node in a binary search tree. This function does not return anything, but prints out, to the file specified, the nodes in the tree rooted at “root” by performing an inorder traversal.
Part 2:Test the performance of the designed data structure using theoretical and experimental approaches as follows:
1.Dataset 1-Dataset is sorted-Add codetoinsert the numbers 1...nin that orderin an initially emptydoubly linked list andabinary search tree.
a.Run it on different values ofnwhere :
i.n = 20,000
ii.n = 50,000
iii.n = 100,000
b.Do an in-order traversal of the tree, printing out the contents to a file (named “sorted”) to verify that you indeed built the data structure correctly.
c.Note the time for eachprogram executions to just build the data structure (i.e., don’t include printing in the time) and include the timings in your report. For eachn, you must run it 3 times and then take the average time. Don’t forget to submit all your data though.
d.Report the results of the analyzed algorithms for each data structure using the Big-O andthe timings.
2.Dataset 2-Dataset is random - Add codeto read in values from “dataToBuildDS.txt” and properly insert them in an initially emptydoubly linked listand binary search tree.
1.Run your program on different values ofnby doing the following:
·Read in the first 20,000 entries only found in “dataToBuildDS.txt”
·Read in the first 50,000 entries only found in “dataToBuildDS.txt”
·Read in the first 100,000 entries only found in “dataToBuildDS.txt”
2. Do an in-order traversal of the tree, printing out the contents to a file(named “unsorted”) to verify that you indeed built the data structure correctly.
3. Note the time to build the data structure. For eachn, you must run it at least 3 times and then take the average. Include all timings as well as the average in your report.
4. Report the results of the analyzed algorithms for each data structure using the Big-O andthe timings.
Your Answer should include the following parts :
·[25 marks] Implementation of the data structures that shows the experimental study in timings for the datasets for insertion and printalgorithms for each data set.
·[25 marks] Report:
oDescribe the data structure [BST] and algorithms [insert, find and print] in pseudocode.
oComparison in terms of:
§Big-O and datasets for insert and print
§Timings and datasets for insert and print