JAVA Program: Create an implementation of a red-black tree using a subclass of BinaryNode

In addition to the normal functions of a red-black tree, you will add the following methods:

a) Count the number of leaves in a tree with data.

b) Return the height of the tree.

c) Return a listing of all the nodes in our tree with values between a and b (a and b being values given to us by the user)

Your program should:

-Randomly generate 100 values

-Load the values which were generated into both an instance of your BST and red-black tree programs

Offer the user a menu with the following options:

oInsert a new value (ignore repetitions , values should be added to both trees)

o Delete a value (values should be deleted from both trees)

o Return a count of the leaves of both trees

oReturn a listing of all values in the tree between a and b, where a and b are input by the user.

o An option for the user to delete the first 20 entries in the trees encountered by a preorder traversal if possible. Once completed this option will automatically display the new height of the tree, and the count of the remaining leaves in both trees.

Provide an option to exit the program

(Your program should continue displaying the menu after each action is completed until the user chooses to quit)

//This is the BinaryNode class

class BinaryNode { private T data; private BinaryNode leftChild; private BinaryNode rightChild; public BinaryNode(){ this(null);//call next constructor } public BinaryNode(T dataPortion){ this(dataPortion, null, null); // call next constructor } public BinaryNode(T dataPortion, BinaryNode newLeftChild, BinaryNode newRightChild){ data = dataPortion; leftChild = newLeftChild; rightChild = newRightChild; } // end of constructor // method:getData // purpose: retrieves the data of the node and return // the object in the data of the node public T getData(){ return data; } //method: setData // purpose: sets the data of the node public void setData( T newData){ data = newData; } // method: getLeftChild // purpose: retrieves the left child of the current node public BinaryNode getLeftChild(){ return leftChild; } //method : hasLeftChild // purpose: checks if the node has a left child public boolean hasLeftChild(){ return leftChild != null; } // method: setLeftChild // purpose: sets the node left child to the current node public void setLeftChild(BinaryNode newLeftChild){ leftChild = newLeftChild; } // method: isLeaf // purpose: checks if the node is a leaf or not public boolean isLeaf(){ return (leftChild == null) && (rightChild == null); } // method: getRightChild // purpose: retrieves the right child of the current node public BinaryNode getRightChild(){ return rightChild; } // method: setRightChild // purpose: sets the node right child to the current node public void setRightChild(BinaryNode newRightChild){ rightChild = newRightChild; } // method: hasRightChild // purpose: checks if the node has a left child public boolean hasRightChild(){ return rightChild !=null; } // method: getNumber of Nodes // calculates the number of nodes in the tree recursively public int getNumberOfNodes(){ int leftNum = 0 ; int rightNum = 0; if(leftChild != null) leftNum = leftChild.getNumberOfNodes(); if(rightChild !=null) rightNum = rightChild.getNumberOfNodes(); return 1+leftNum +rightNum; } // method: getHeight // purpose: computes the height of the subtree // of the the current node public int getHeight(){ return getHeight(this); // calls the private recursive method } // the recursive method to count the height of the tree private int getHeight(BinaryNode node){ int height = 0; if(node != null) height = 1 + Math.max(getHeight(node.getLeftChild()),getHeight(node.getRightChild())); return height; } // method: copy // purpose: copies the subtree that is rooted to the current node public BinaryNode copy(){ BinaryNode newRoot = new BinaryNode<> (data); if(leftChild != null) newRoot.setLeftChild(leftChild.copy()); if(rightChild != null) newRoot.setRightChild(rightChild.copy()); return newRoot; } }