Anyone? J unit test cases

/** * @(#)Red_Black_Tree.java * * Red_Black_Tree application * * @author * @version 1.00 2013/1/8 */ import java.util.Random; import java.util.Stack; class RedBlackTree { /* *************************************************** * * PRIVATE FIELDS * * *************************************************** */ private RedBlackTree tree; private int size; /* If during an insert() or delete() it is found that * the key is present in the tree, keyFound will be true * and prevValue will contain the previous value * associated with the key before the update. */ private boolean keyFound; private Object prevValue; /* *************************************************** * * PUBLIC INTERFACE * * *************************************************** */ /* * Constructs a new empty red-black tree. */ public RedBlackTree() { tree = null; size = 0; } /** * Maps the key to the specified value in this red-black tree. * Neither the key, nor the value can be * <code>null</code>. * @return the previous value to which the key was mapped, * or <code>null</code> if the key did not have a previous * mapping in the red-black tree. */ public synchronized Object put(String key, Object value) { if (key == null || value == null) throw new NullPointerException(); RBTree node = new RBTree(); node.key = key; node.value = value; keyFound = false; tree = insert(node, tree); if (keyFound) return prevValue; else { size++; return null; } } /** * Gets the object associated with the specified key in the red-black tree. * @return the value to which the key is mapped in the red-black tree, or * <code>null</code> if the key is not mapped to any value in * this red-black tree. */ public synchronized Object get(String key) { RBTree t = tree; int comp; while (t != null && (comp = key.compareTo(t.key)) != 0) if (comp < 0) t = t.left; else t = t.right; return t != null ? t.value : null; } /** * Returns <code>true</code> if this red-black tree contains no mappings. */ public boolean isEmpty() { return tree == null; } /** * Removes tke key (and its corresponding value) from this red-black tree. * This method does nothing if the key is not in the red-black tree. * @return the value to which the key had been mapped in this red-black tree, * or <code>null</code> if the key did not have a mapping. */ public synchronized Object remove(String key) { RBTree node = tree; while (node != null) { int comp = key.compareTo(node.key); if (comp < 0) node = node.left; else if (comp > 0) node = node.right; else { prevValue = node.value; tree = delete(node, tree); size--; return prevValue; } } return null; } /** * Clear the red-black tree so that it contains no mappings. */ public synchronized void clear() { tree = null; size = 0; } /** * Returns the number of keys in this red-black tree. */ public int size() { return size; } /* This overrides the default toString method to print out a traversal of the tree *. This should be in the form of a preorder traversal of the tree in which each node * is printed out in the form of the key, followed by a colon and then a B or an R, * all in square brackets. So a tree with root 5 and children 3 and 9 would look like * [5:B][3:R][9:R].*/ public String toString() { if (key != null || value != null) throw new NullPointerException(); RBTree node = new RBTree(); node.key = key; node.value = value; keyFound = true; while (node != null) { if(node.color == RBTree.RED && node.key() = node.value()) { string x = "R"; System.out.println("[" + value +":" + x + "]"+ " "); if(node.color == RBTree.BLACK && node.key() = node.value()) { string x = "B"; System.out.println("[" + value +":" + x + "]"+ " "); } return key; } } } /** * Returns a string displaying the tree structure * and the priority numbers. */ public synchronized String printDebug() { StringBuffer strbuf = new StringBuffer(); String newline = System.getProperty("line.separator"); strbuf.append("size: " + size + newline); if (tree != null) tree.printDebug(0, strbuf); return strbuf.toString(); } public String printStat() { StatStruct stat = new StatStruct(); collectStat(tree, 0, stat); StringBuffer strbuf = new StringBuffer(); String newline = System.getProperty("line.separator"); strbuf.append("Aver depth: " + (float) stat.totDepth / this.size + newline); strbuf.append("Max depth: " + stat.maxDepth + newline); return strbuf.toString(); } /* *************************************************** * * PRIVATE METHODS * * *************************************************** */ /* Inserts a node into tree and returns the updated red-black tree */ private RBTree insert(RBTree node, RBTree tree) { RBTree father = null, son = tree; /* Insert the new node into the tree. */ while (son != null) { father = son; int comp = node.key.compareTo(son.key); if (comp < 0) son = son.left; else if (comp > 0) son = son.right; else { keyFound = true; prevValue = son.value; son.value = node.value; return tree; } } node.parent = father; if (father == null) tree = node; else if (node.key.compareTo(father.key) < 0) father.left = node; else father.right = node; /* Inforce the color invariants of the red-black tree. */ node.color = RBTree.RED; while (node != tree && node.parent.color == RBTree.RED) { if (node.parent == node.parent.parent.left) { son = node.parent.parent.right; if (son != null && son.color == RBTree.RED) { node.parent.color = RBTree.BLACK; son.color = RBTree.BLACK; node = node.parent.parent; node.color = RBTree.RED; } else { if (node == node.parent.right) { node = node.parent; tree = node.rotateLeft(tree); } node.parent.color = RBTree.BLACK; node.parent.parent.color = RBTree.RED; tree = node.parent.parent.rotateRight(tree); } } else { son = node.parent.parent.left; if (son != null && son.color == RBTree.RED) { node.parent.color = RBTree.BLACK; son.color = RBTree.BLACK; node = node.parent.parent; node.color = RBTree.RED; } else { if (node == node.parent.left) { node = node.parent; tree = node.rotateRight(tree); } node.parent.color = RBTree.BLACK; node.parent.parent.color = RBTree.RED; tree = node.parent.parent.rotateLeft(tree); } } } tree.color = RBTree.BLACK; return tree; } { /* Deletes a node from a red-black tree and * returns the updated red-black tree. */ private RBTree delete(RBTree node, RBTree tree) { RBTree x, y; if (node.left == null || node.right == null) y = node; else y = node.successorGet(); if (y.left != null) x = y.left; else x = y.right; if (x != null) x.parent = y.parent; if (y.parent == null) tree = x; else if (y == y.parent.left) y.parent.left = x; else y.parent.right = x; if (y != node) { node.key = y.key; node.value = y.value; } /* If the node to be removed is BLACK, * restore the red-black tree invariants. * The color of a null leaf is BLACK. */ if (y.color == RBTree.BLACK) { RBTree father = y.parent; while (x != tree && (x == null || x.color == RBTree.BLACK)) { if (x == father.left) { RBTree w = father.right; if (w == null) x = tree; else { if (w.color == RBTree.RED) { w.color = RBTree.BLACK; father.color = RBTree.RED; tree = father.rotateLeft(tree); continue; } if ((w.left == null || w.left.color == RBTree.BLACK) && (w.right == null || w.right.color == RBTree.BLACK)) { w.color = RBTree.RED; x = father; father = x.parent; } else { if (w.right == null || w.right.color == RBTree.BLACK) { if (w.left != null) { w.left.color = RBTree.BLACK; w.color = RBTree.RED; tree = w.rotateRight(tree); w = father.right; } } w.color = father.color; father.color = RBTree.BLACK; if (w.right != null) w.right.color = RBTree.BLACK; tree = father.rotateLeft(tree); x = tree; } } } else { RBTree w = father.left; if (w == null) x = tree; else { if (w.color == RBTree.RED) { w.color = RBTree.BLACK; father.color = RBTree.RED; tree = father.rotateRight(tree); continue; } if ((w.right == null || w.right.color == RBTree.BLACK) && (w.left == null || w.left.color == RBTree.BLACK)) { w.color = RBTree.RED; x = father; father = x.parent; } else { if (w.left == null || w.left.color == RBTree.BLACK) { if (w.right != null) { w.right.color = RBTree.BLACK; w.color = RBTree.RED; tree = w.rotateLeft(tree); w = father.left; } } w.color = father.color; father.color = RBTree.BLACK; if (w.left != null) w.left.color = RBTree.BLACK; tree = father.rotateRight(tree); x = tree; } } } } if (x != null) x.color = RBTree.BLACK; } return tree; } } private class StatStruct { int totDepth = 0; int maxDepth = 0; } private void collectStat(RBTree t, int depth, StatStruct stat) { if (t == null) return; else { if (depth > stat.maxDepth) stat.maxDepth = depth; stat.totDepth += depth; collectStat(t.left, depth + 1, stat); collectStat(t.right, depth + 1, stat); } } /*This method will traverse the tree and return true if any red node has a red child.*/ public boolean redViolationExists() { node.color = RBTree.RED; while (node != tree && node.parent.color == RBTree.RED) { if (node.parent == node.parent.parent.left) { son = node.parent.parent.right; if (son != null && son.color == RBTree.RED) { return true; } } } } /** The following function checks the red black tree black height * @param n the root node is inputed then a traversal is done to calculate the black-height * @return Return an error message / mesages informing the user whether or not the black height was maintained * @author */ public static void getCount (SkaRedBlackTreeNode skaRedBlackTreeNode) { VizRedBlackTreeNode n = skaRedBlackTreeNode.getVizRep(); if (validRoot(n)) { static int lcount = leftCount(n); static int rcount = rightCount(n); if (rcount == lcount) { n.displayMsg("Black height maintained"); } else // n.displayWarning("rcount " + rcount + " lcount " + lcount); n.displayError("Red Black Tree is unbalanced"); } } /** The following function counts all the black node of the left side of the tree * @param n the left child is inputed and a traversal is done to count all the black nodes * */ public static int leftCount (VizRedBlackTreeNode n) { if (n == null) return 0; else if (n.getrbtColr() == Color.black) return 1 + leftCount(n.getLeft()); else leftCount(n.getLeft()); } /** The following function counts all the black node of the right side of the tree * @param n the right child is inputed and a traversal is done to count all the black nodes * */ public static int rightCount (VizRedBlackTreeNode n) { if (n == null) return 0; else if (n.getrbtColr() == Color.black) { return 1 + rightCount (n.getRight()); else rightCount(n.getRight()); } } }