Extend the BSTNode class (you can define your own BSTnode) 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: a. Implement Left Rotation and Right Rotation methods in the RBNode class. The Left-Rotate algorithm is given in the next page. Following that algorithm, devise the Right-Rotate algorithm and implement the methods. b. 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, look at the algorithm next page).

Question. Implement the case for which parent of x is the left child of grandparent of x. and write a driver program to test the RBTree class. Make sure you use all the methods implemented above.

RB-INSERT (T, z) LEFT-ROTATE (T, x) y = T.nil x = T. root whilex T.nil y = x.right x.right = y, left if y, leftT. nil // turn y's left subtree into x's right subtree le if z.key