In java,

1. extend the BSTNode class (as below) 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-totate algorithm is given below. Following that algorithm, devise the Right-rotate algorithm and implement the methods.

3. Implement a method RBInsert(K key, V value) in to insert a node to a Red Black Tree (this method uses the insert method of ; 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.

public class BinaryTree> private BinaryTreeNode root; 1/ the root of the tree private BinaryTreeNode node) root = node; *Moves the cursor to the root. public void toRoot O cursor = root; * Returns the cursor node. *Greturn cursor public BinaryTreeNode getCursor()[ return cursor; * Sets the root to the provided node. * ONLY USE IN THE DELETE ME THOD * @param node public void setRoot (BinaryTreeNode node) root = node; public class BinaryTree> private BinaryTreeNode root; 1/ the root of the tree private BinaryTreeNode node) root = node; *Moves the cursor to the root. public void toRoot O cursor = root; * Returns the cursor node. *Greturn cursor public BinaryTreeNode getCursor()[ return cursor; * Sets the root to the provided node. * ONLY USE IN THE DELETE ME THOD * @param node public void setRoot (BinaryTreeNode node) root = node