Implement the following methods in class RedBlackTree. For all these methods you just need to implement the body of the methods already present in the class,

a. Insert: This method inserts a node in the red-black tree. This method must increment size variable after successful insertion. Fake nodes are not counted in size.

b. Delete: this method deletes a node in the red-black tree. This method must decrement size variable after successful deletion. Fake nodes are not counted in size.

c. Height: this method returns the height of the binary search tree

d. Blackheight: this method returns the black height of the binary search tree

e. Traversal methods: should print the values of the node traversed. These traversal methods must ignore all the fake nodes.

i. Inorder: for in-order traversal

**********************************************Red and Black Tree*********************************************

package SearchTrees;

import SearchTrees.RBNode.RBColor;

public class RedBlackTree > { private RBNode root; //private RBNode nil = new RBNode(); private int size; public RedBlackTree() { root = new RBNode<>(); //empty root size = 0; } public int Size() { return size; } /***************************************************************** * * Height of tree * ****************************************************************/ public int height() { //TODO -> Implement here return 0; } /***************************************************************** * * Black Height of a node * ****************************************************************/ public int blackHeight() { //TODO -> Implement here return 0; } /***************************************************************** * * Finding node with minimum value * ****************************************************************/ public RBNode treeMin() { return treeMin(root); } public RBNode treeMin(RBNode x) { while (!x.left.isEmpty()) { x = x.left; } return x; } /* *************************************************************** * Insert a new node * Returns true on successful insert otherwise false (when already present) *****************************************************************/ public boolean insert(T data) { //TODO -> implement here return false; } // Fix up the tree that just had node inserted private void insertFixup(RBNode z) { //TODO -> implement here } private void leftRotate(RBNode node) { //TODO -> implement here } private void rightRotate(RBNode node) { //TODO -> implement here } /***************************************************************** * Delete a node * Returns true on successful deletion and false otherwise *****************************************************************/ public boolean delete(T data) { boolean found = false; //TODO -> implement here return found; } // Assigns node v to the parent of u // useful while deletion private void assignParent(RBNode u, RBNode v) { if (u.parent == null) { root = v; } else if (u == u.parent.left) { u.parent.left = v; } else { u.parent.right = v; } v.parent = u.parent; } private void deleteFixup(RBNode x) { //TODO -> implement here } /**************************************************************** * * Reset Tree * ***************************************************************/ public void reset() { root = new RBNode<>(); size=0; } /***************************************************************** * Traversal * ******************************************************************/ public void inorder() { System.out.print("inorder RBT: "); //TODO -> Implement here System.out.println(); }

public void preorder() { System.out.print("preorder RBT: "); //TODO -> Implement here System.out.println(); }

public void postorder() { System.out.print("postorder RBT: "); //TODO -> Implement here System.out.println(); } }