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, (ii) with the users 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 users search query on the selected data structure on that file. You must implement the BST and Red-Black trees yourself, consistent with the algorithms presented in chapters 12 and 13 of the CLRS text. You do not need to implement Delete(key) from the BST nor the red-black tree. As an added simplification, you may also assume that all inserted keys are unique. At a minimum, you should implement the Insert, Search, and InOrderTreeTraversal operations for both the BST and Red-Black tree. Allow the user to print to an output file the output of InOrderTreeTraversal. Additionally, please implement the following print methods allowing the user to see useful attributes of keys:

For Red-Black trees only: void PrintColor(String key)

If the key exists in the Red-Black tree, print the color of its tree-node.

For both BST and Red-Black trees: void PrintParentKey(String key)

If the key exists in the tree, print the key of its parent node. o In case the key is at the root with no meaningful parent, print NIL.

For Red-Black trees only: void PrintParentColor(String key)

If the key exists in the Red-Black tree, print the color of its parent node.

For both BST and Red-Black trees: void PrintLeftChild(String key)

If the key exists in the tree, print the key of its left child node.

In case the right child is NIL or NULL, print NIL.

For both BST and Red-Black trees: void PrintRightChild(String key)

If the key exists in the tree, print the key of its right child node.

In case the right child is NIL or NULL, print NIL.

For Red-Black trees only: void PrintUncleColor(String key)

If the key exists in the Red-Black tree, print the color of its uncle node (uncle is the sibling of the parent node).

For both BST and Red-Black trees: void PrintPathToRoot(String key)

If the key exists in the tree, print its parent nodes key, its grand-parents key, its great-grandparents key, , all the way to the root.

For the Red-Black tree, print the ancestor colors along with the keys.