Goals: Implementation of binary search trees.
Part 1 Describe your add, display, and remove algorithms using pseudo code.
Part 2 Answer the following questions
1) When would you use a binary search tree over an ordered or unordered array?
2) Give one way how implementing a heap differs from implementing a binary search tree.
3) How does the efficiency of binary search tree operations compare to that of linked lists?
4) How can binary search insertions degrade in performance to O(N), rather than O(Lg(N))?
5) Give an example of when pre-order traversal is desirable. What about post-order?
6) What is the definition of a priority queue?
7) How would you implement a priority queue where internal nodes could change priority? How would you find one of the internal nodes in the structure?
8) Prove that heap creation is O(N).
9) Define the term: Complete Binary Treee.
10) Prove that heap sort is (O(N Lg N))
Part 3 Implement the program. Include files containing the typed answers to the part 1 questions, the pseudo-code, and the extra analysis (if this is the project that your chose to do the analysis). Make sure to name your files so I can easily recognize them.
Hints and Instructions
Implement your employee list program using the binary search tree data structure instead of the linked list implemented in the previous project. Create the employee list in a loop using random descriptions, prices, costs, and balance on hand just as was done in the previous project. Duplicate field values are ok; but duplicate item numbers are not allowed. Print out the employee list in item number order after the list is created.
Extra Analysis
Do this part if this to be your longer project or if you are a graduate student. Otherwise this will be for extra credit.
Randomly fill your employee list that uses an unordered array. Next randomly fill your employee list that uses a binary search tree. Time both approaches using different data set sizes and using data sets with different characteristics. Write a one or two page paper that analyzes the timing differences between your unordered array implementation and your binary search tree implementation.
For extra credit, implement a heap sort and quick sort that will order your unordered array. Time how long the each sort takes with different data set sizes. Write a one or two page paper that analyzes the timing differences between your two sorts.
When comparing algorithms, normally large data set sizes are needed. Also, picking array sizes that vary exponentially is useful to capture the attributes of the algorithms. For example, picking array sizes as 100000, 200000, 400000, 800000, etc. would be appropriate (Assuming that C allows array sizes that large).
You can use the C clock() for timing purposes, including < time.h>. The following is a sample snippet to demonstrate how this works
clock_t start = clock();
/* do some cool stuff here */
clock_t end = clock();
double time = 1.0*(end - start)/CLOCKS_PER_SEC;
printf("The algorithm took %lf timen", time);
fflush(stdout);