Part 1

1. Extend the BSTNode class to form a new class RBNode to add a color field and a value field to each node (let the color field be of type boolean and the value field be a generic type). Also extend the BinarySearchTree class to create the RBTree class and include the following methods.

2. Implement Left Rotation and Right Rotation methods in the RBNode class. The Left-Rotate algorithm is given below. Following that algorithm, devise the RightRotate algorithm and implement the methods.

3. Implement a method RBInsert(K key, V value) in RBTree.java to insert a node to a Red Black Tree (this method uses the insert method of BinarySearchTree; see the algorithm below). In class implement the case for which parent of x is the left child of grandparent of x.

4. Write a driver program to test the RBTree class. Make sure you use all the methods implemented above.

Part 2

1. Implement the case for which parent of x is the right child of grandparent of x.

2. Use the RBTree class to build a search tree using the given input file that consists of two fields: a UPC key and the corresponding description.

a. Use the search tree created to find the description associated with a given set of UPC keys.

b. The input file UPC.csv provides the key and corresponding descriptions in a comma separated file and the various search keys are provided in the file input.dat.

c. First test the program by entering couple of keys manually and print the description. Once you are convinced the program is working correctly, test the program for the given search keys and determine the total time taken to complete the search.