Project 4 - Implementing and Using a BST

Due - Tuesday, May 10, 2005

The goal of this project is to give you an opportunity to practice implementing and using binary search trees.

For this project, you will re-use portions of your solution from Project 3. Your solution to Project 4 will have almost the same behavior as your solution to Project 3. However, for Project 4 you will change the following: (1) you cannot assume that your configuration file will be ordered by arrival time and (2) you must replace your OrderedQueue with a BinarySearchTree. An example configuration file will look as follows:
numTellers 3
arrival 78 service 124
arrival 39 service 57
arrival 35 service 62
arrival 79 service 32
The output of your program should look the same as the output of Project 3.

Your program must implement a BinarySearchTree class. As you read in your configuration file, insert each arrival event into the BinarySearchTree. To sort the list of arrival events, perform an in-order traversal of the BinarySearchTree.

During the run of your program, you must still use two instances of LinkedQueue to represent the sorted list of customer arrivals and the list of customers waiting to be serviced. However, instead of using your OrderedQueue, you must use a BinarySearchTree to represent the list of customers currently being serviced. Items must be inserted into the tree in order, and you must implement a getSmallest function and a removeSmallest function. These functions will need to determine how to find/remove the smallest item in the tree. Note, you do not need to implement a heap therefore the smallest element will not be at the root.

Implementation Hints

You may look at the Binary Tree code available from http://cpp.datastructures.net/source/ch06.html. However, you may not use structs in your code.

Extra Credit Opportunity

  1. Implement a Heap and use it in place of the BinarySearchTree representing the list of customers currently being serviced. Note, you must still implement the BinarySearchTree for sorting the list of events in the configuration file.

Due Tuesday, May 10, 2005

Submit the following pieces:
  1. A complete design of your program. Include a detailed design of the BinarySearchTree (and heap if implemented) and also indicate changes to your Project 3 design to support the new implementation.
  2. All .h and .cpp files (containing well-documented functions) required to compile and run your program.
  3. A sample configuration file.
  4. Optional: a readme file providing directions for compiling and running your program.
Reminder: No part of your code may be copied from any other source unless noted on this page. All other code submitted must be original code written by you.
Sami Rollins