Pblack tree class implementation

Download these files and move them to your project$1-3$ folder and implementations for functions specified below in the IterableRedBlackTree.java file.

IterableSortedCollection.javaDownload IterableSortedCollection.java

IterableRedBlackTree.javaDownload IterableRedBlackTree.java

$1.$ Handling Duplicates

Our old BinarySearchTree implementation rejected duplicate values, but our song data for project one includes many duplicate$/$tied values. To address this problem without affecting any of our old tests or other code that makes use of this class, we'll override the insertHelper method.

Copy the definition of the insertHelper method from your BinarySearchTree class into your IterableRedBlackTree class. In this new copy within your IterableRedBlackTree class, comment out the first if$-$statement within this method's while$-$loop, and change the following else$-$if to an if$-$statement with the condition: compare $<=0.$ This should cause any duplicate values to be stored within the left subtree of any ancestor nodes containing the same value.

$2.$ The Iteration Start Point

Implement the setIterationStartPoint method for this class to store a copy of the argument passed to it within a private instance field.

The default start point should be set to a value that is earlier$/$smaller than any value in any possible IterableRedBlackTree. To accomplish this, initialize your private instance field using either an anonymous class or a lambda expression. And define this object to contain a compareTo method that always returns $-1$ independent of what it is being compared to$.$ If null is ever passed to the setIterationStartPoint method as an argument, then this instance field should return to being a value that is always smaller than any possible value in the tree.

$3.$ The RBTIterator

Implement the iterator$()$ method in your IterableRedBlackTree class. This method should instantiate and return a new RBTIterator object.

Define the constructor of the provided RBTIterator class to store the specified start point in a private instance field within the iterator. It should also create and store an empty Stack of Node references within a private instance field. This stack will be used by the iterator to help track the parts of the tree that are left to iterate through in future calls of the iterator's next method.

The last thing that should happen in this constructor, is that the buildStackHelper method should be called, and passed the root of the tree that is being iterated through.

$4.$ The buildStackHelper Method

The job of the buildStackHelper method is to both $1)$ find the next data value stored in a tree $($or subtree$)$ that is bigger than or equal to the specified start point, and $2)$ to build up the stack of ancestor nodes that are larger than or equal to the start point, so that those nodes' data can be visited in the future.

This recursive method will have one base case and two recursive cases. The base case is reached when a null reference is passed as the node argument, and the method simply returns in that case. When the data within the node argument is smaller than the start value, this method should recursively be called on the node's right subtree $($where values large than the start point can be found$).$ When the data within the node argument is greater than or equal to the start point, $1)$ that node should be pushed on the stack so that it's data can be visited later, and $2)$ a recursive call should continue to build the stack through this node's left sub$-$tree $($where smaller and equal values that we want to iterate through can be found$).$

$5.$ The Iterator Methods

Implement the next$()$ and hasNext$()$ methods of the RBTIterator class. The stack built by the method above should always contain the node with the next value to iterate through, and ONLY the ancestors of that node that contain values larger than or equal to that node's data. As you step through the values in the tree, you will sometimes need to build this stack to contain more values, and the buildStackHelper method will be convenient to re$-$use for this purpose. If next$()$ is called with an empty stack, the method should throw a NoSuchElementException.

I