C Programming language Binary Search Tree Empirical and Theoretical Results Part 1: we need to define a binary search tree data structure. Also, we 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 inorder traversal(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.
C
Binary Search Tree Empirical and Theoretical Results
Part 1: we need to define a binary search tree data structure. Also, we 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 inorder traversal(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 code to insert the numbers 1...n in that order in an initially empty doubly linked list and a binary search tree.
a. Run it on different values of n where :
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 each program executions to just build the data structure (i.e., don't include printing in the time) and include the timings in your report. For each n, 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
Step by step
Solved in 2 steps