CISC220 F2021 Lab5
1. Binary Search Tree (BST) implementation
Write two versions of a templatized binary search tree class BSTree_Fast and BSTree_Slow (details below). For each version you should define the following FOUR member functions: insert(), contains(), findMin(), and findMax() [2 points for Fast version, 1 point for Slow]. Both classes will use the templatized class BSTNode to store an inserted element. When an element (aka key) is inserted more than once, there should not be multiple BSTNodes created, but rather the number member variable of the original BSTNode should be incremented.
Starter code is provided here
- BSTree_Fast
- Implement the BST using a traditional pointer-based linked structure as detailed in Chap. 6.2 of the textbook.
- Write a member function print() which does the following [0.5 points]:
- Prints a count of how many unique keys there are
- Prints how many keys total there are
- Prints the min and max keys
- BSTree_Slow
- Implement the BST using an unordered STL vector of pointers to BSTNodes (the left and right pointer variables of each node will be NULL and unused). Do not attempt to keep things organized: contains() should be a simple loop through the vector, insert() should just be push_back() if this is the first occurrence of the key, and so on. Note that this NOT the same as representing a binary tree's structure with an array as described in lecture and Chap. 6.2 of the textbook.
- Write a member function print() which does the same as above [0.5 points]
2. BST testing and comparison
Write a driver function which creates and fills a separate BSTree_Fast and BSTree_Slow of C++ strings for each of the following files by reading from them word-by-word and calling insert() repeatedly. Note that all of these files have been "cleaned" (punctuation removed, all lower-case).
In your README PDF, answer the following questions for each file using the information from print() or your own custom functions. Your BSTree_Fast and BSTree_Slow should give the same answers for the first three questions [1 point for all questions answered]
- How many unique words are there?
- How many different words total are there?
- What are the alphabetically first and last words?
How long does it takes for BSTree_Fast vs. BSTree_Slow to carry out the following FOUR operations for each of the three input files [1 point total]? (To get precise timing under Unix, use the gettimeofday() function. There is a code snippet under the Unix, Linux and Mac section here that should help.)
- Create the BST
- Search for each of these words with contains():
- love
- death
- tyranny
3. Submission
- Include a PDF file <Your Name>_README.pdf which contains:
- Answers to the questions above. Do NOT include the full listing from your print() functions. However, a call to print() for both versions of the BST should be in your driver code.
- The timing measurements requested, in a nicely-formatted table, as well as comments on why you think the timings vary for the different (1) BST implementations, (2) operations being performed, and (3) files from which the BSTs were created.
- Rename your code directory <Your Last Name>_Lab5 and create a single tar/zip/rar file out of it named <Your Last Name>_Project1.tar (or .zip or .rar, etc.).
- Submit it in Canvas by midnight at the end of Tuesday, October 5
