GIVEN:

package redblack; import java.util.Stack; public class RBTree { /* * For coloring the nodes. */ enum Color { RED, BLACK; } /* * Nested class for a Tree node */ static class Node { Node left; Node right; Node parent; int data; Color color; public Node(int data, Color c) { this.data = data; color = c; left = right = parent = null; } } Node root; void leftRotate(Node node) { //Done } void rightRotate(Node node) { //Done } /* * NO DUPLICATE VALUES SHOULD BE INSERTED! */ public void insert(int i) { //Done } void insertFixup(Node node) { } /* * This method should return a string representation of the tree from an in order traversal * This method has to be completed iteratively (HINT: you might want to use a Stack) * An in order traversal means that the data will be in sorted order * An empty tree should return the String "{}" * A tree with the nodes inserted in the order 2, 1, 3 * should return the String "{(1,RED),(2,BLACK),(3,RED)}" */ public String toString() { //returns an inOrder traversal of the tree (data will be in sorted order) if(root == null){ return "{}"; } } } 

void insertFixUp (Node node) This method recolors and rotates the tree to ensure that the tree remains a valid red-black tree after inserting a new value. See the pseudocode below. IbInsertFixup (T,z) 1 while (zpcolor==RED) if zp==zpp left y=zppright if ycoOr==REF zpColor=BLACK y color = BLACK zPPCOlOr=RED z=zpp else if z==zpright z=zp leftrotate (T,z) zpCOlOr=BLACK zppcolor==RED rightRotate (T,zpp) else //zp==zppright, swap left and right from if statement T. root. color = BLACK public String tostring() This method should return a string representation of the tree from an in order traversal. An in order traversal visits the left subtree, then the current node, then the right subtree resulting in the data being printed in sorted order. This method has to be completed iteratively (HINT: you might want to use a Stack). Examples - An empty tree should return the String " } " - A tree with the nodes inserted in the order 2,1,3 should return the String " {(1,RED),(2,BLACK),(3,RED)}