Description: For this project, you will use the word files provided in Project I as input to implement dictionaries and search in dictionaries using two different data structures, binary search tree and red-black tree.
Specifications:
Using the same input files provided in Project 1, you will construct both binary search trees and red-black trees. Taking these data structures to be the “dictionary” holding the searched words, you will allow the user to (i) search for words, (ii) in selected input files,
with the user’s choice of BST versus R-B tree dictionary implementation. You will in turn output (i) whether or not the word was found in the file, (ii) the time taken to construct the dictionary from the selected data structure on the selected file, as well as (iii) the time taken to execute the user’s search query on the selected data structure on that file.
You must implement the BST and Red-Black tree yourself, consistent with the algorithms presented in chapters 12 and 13 of the CLRS text. For the red-black tree, you
must obviously implement the Insertion and Retrieval methods, but you do not need to implement deletion from the red-black tree.
Plots: You will have two sets of plots, one for the sorted inputs and one for the permuted inputs. In each plot, you are to graph the execution time of constructing your data structures, namely BST and R-B tree, as a function of size (number of words).
What to turn in:
You must turn in a single zipped file containing your source code, the PLOTS, a README file indicating how to execute your program, and a Makefile if needed for compilation. Refer to proglag.pdf for special cases.
