IN JAVA: public boolean insert(Integer i) 

This method should use a top down insertion strategy (see below) to insert a Node with data equal to i into the Red-Black Tree provided that a Node with data equal to i does not already exist in the Red-Black Tree (i.e., no duplicate data). If the node is successfully inserted, return true, otherwise return false (tried to insert a duplicate element).

For the first part of the assignment, you will implement a top-down insertion for a red-black tree. The general outline of the algorithm is described below (adapted from https://www.rose-hulman.edu/class/cs/csse230/201420/Slides/15-RedBlackTrees.pdf). Basically the idea is to do the recoloring and rotations on the way down instead of after you insert the node. Node that the node to be inserted is always red, you may need to do one final rotation after inserting the node if its parent is red. Note that in this version of the red-black tree, we do not have parent pointers in our Node class. You cannot add a parent pointer to the node class or do additional tree traversals to find parent nodes. You will need to use a Stack to keep track of the ancestors in order to perform the correct rotations.

This is the situation you need to handle on your way down the tree Situation: A black node with two red children. Action: - Recolor the node red and the children black. - If the parent is red, perform rotations, otherwise continue down the tree If the color flip produces a red node with a red child, then perform a single or double rotation depending on the following... - If the two red nodes are both left children or both right children, perform a single rotation (see example below) - Otherwise, perform a double rotation (see example below) Single Rotation on Left Child - The rotation is done on X's grandparent, G. - Again, the rotation is done on X 's grandparent, G. - The colors of P and G are flipped