How to fix uninstall in a RedBlackTree implementation?

Question

Here is the RedBlackTree implementation I'm using (from Mark Allen Weiss, Data Structures

public class RedBlackTree<AnyKey extends Comparable<? super AnyKey>, AnyValue extends Comparable<? super AnyValue>> implements MyTreeMap<AnyKey, AnyValue>{ private static final int BLACK = 1; private static final int RED = 0; // The psuedo(bogus) root, has a key value of negative infinity and a right link to the real root. private RedBlackNode<AnyKey, AnyValue> header; // Used in place of a null link. Will always be colored black. private RedBlackNode<AnyKey, AnyValue> nullNode; private RedBlackNode<AnyKey, AnyValue> current; private RedBlackNode<AnyKey, AnyValue> parent; private RedBlackNode<AnyKey, AnyValue> grand; private RedBlackNode<AnyKey, AnyValue> great; public RedBlackTree( ){ nullNode = new RedBlackNode<AnyKey, AnyValue>( null, null ); nullNode.left = nullNode.right = nullNode; header = new RedBlackNode<AnyKey, AnyValue>( null, null ); header.left = header.right = nullNode; } private final int compare( AnyKey theKey, RedBlackNode<AnyKey, AnyValue> t ){ if( t == header ) return 1; else return theKey.compareTo( t.key ); } private void insert( AnyKey theKey, AnyValue theValue ){ current = parent = grand = header; nullNode.key = theKey; nullNode.value = theValue; while( compare( theKey, current ) != 0 ){ great = grand; grand = parent; parent = current; current = compare( theKey, current ) < 0 ? current.left : current.right; // Check if two red children; fix if so if( current.left.color == RED && current.right.color == RED ) handleReorient( theKey); } // Insertion fails if already present if( current != nullNode ) throw new IllegalArgumentException( theKey.toString( ) ); current = new RedBlackNode<AnyKey, AnyValue>( theKey, theValue, nullNode, nullNode ); // Attach to parent if( compare( theKey, parent ) < 0 ) parent.left = current; else parent.right = current; handleReorient( theKey ); } /** * Remove from the tree. * @param x the item to remove. * @throws UnsupportedOperationException if called. */ public void remove( AnyKey x ){ } /** * Internal routine that is called during an insertion * if a node has two red children. Performs flip and rotations. * @param item the item being inserted. */ private void handleReorient( AnyKey key ){ // Do the color flip current.color = RED; current.left.color = BLACK; current.right.color = BLACK; if( parent.color == RED ){ // Have to rotate grand.color = RED; if( ( compare( key, grand ) < 0 ) != ( compare( key, parent ) < 0 ) ) parent = rotate( key, grand ); // Start dbl rotate current = rotate( key, great ); current.color = BLACK; } header.right.color = BLACK; // Make root black } /** * Internal routine that performs a single or double rotation. * Because the result is attached to the parent, there are four cases. * Called by handleReorient. * @param item the item in handleReorient. * @param parent the parent of the root of the rotated subtree. * @return the root of the rotated subtree. */ private RedBlackNode<AnyKey, AnyValue> rotate( AnyKey item, RedBlackNode<AnyKey, AnyValue> parent ){ if( compare( item, parent ) < 0 ) return parent.left = compare( item, parent.left ) < 0 ? rotateWithLeftChild( parent.left ) : // LL rotateWithRightChild( parent.left ) ; // LR else return parent.right = compare( item, parent.right ) < 0 ? rotateWithLeftChild( parent.right ) : // RL rotateWithRightChild( parent.right ); // RR } /** * Rotate binary tree node with left child. * @param k2 the node to rotate with. */ private static <AnyKey, AnyValue> RedBlackNode<AnyKey, AnyValue> rotateWithLeftChild( RedBlackNode<AnyKey, AnyValue> k2 ){ RedBlackNode<AnyKey, AnyValue> k1 = k2.left; k2.left = k1.right; k1.right = k2; return k1; } @Override public void put(AnyKey x, AnyValue y) { RedBlackNode<AnyKey, AnyValue> bN = find(x); if(bN == null) { insert(x, y); } else { bN.value = y; } } /** * Rotate binary tree node with right child. * @param k1 the node to rotate with. */ private static <AnyKey, AnyValue> RedBlackNode<AnyKey, AnyValue> rotateWithRightChild( RedBlackNode<AnyKey, AnyValue> k1 ){ RedBlackNode<AnyKey, AnyValue> k2 = k1.right; k1.right = k2.left; k2.left = k1; return k2; } /** * Node in the red black tree. * @author Letian Sun * @param <AnyKey> can be any object type * @param <AnyValue> can be any object type */ private static class RedBlackNode<AnyKey, AnyValue>{ AnyKey key; AnyValue value; RedBlackNode<AnyKey, AnyValue> left; RedBlackNode<AnyKey, AnyValue> right; int color; RedBlackNode( AnyKey theKey, AnyValue theValue ){ this( theKey, theValue, null, null ); } RedBlackNode( AnyKey theKey, AnyValue theValue, RedBlackNode<AnyKey, AnyValue> lt , RedBlackNode<AnyKey, AnyValue> rt ) { key = theKey; value = theValue; left = lt; right = rt; color = RedBlackTree.BLACK; } public String toString() { return "element:" + key.toString() + " times:" + value.toString(); } } 

I am trying to write a delete method that the author did not write. That's what i still have

 @Override public void remove( AnyKey x ){ header.right = remove( x, header.right ); } private RedBlackNode<AnyKey, AnyValue> remove( AnyKey x, RedBlackNode<AnyKey, AnyValue> t ){ if( t == nullNode ) return t; // Item not found; do nothing int compareResult = x.compareTo( t.key ); if( compareResult < 0 ) t.left = remove( x, t.left ); else if( compareResult > 0 ) t.right = remove( x, t.right ); else if( t.left != nullNode && t.right != nullNode ){ // Two children t.key = findMin( t.right ).key; t.right = remove( t.key, t.right ); } else t = ( t.left != nullNode ) ? t.left : t.right; return rotate(t.key, t ); } private RedBlackNode<AnyKey, AnyValue> findMin(RedBlackNode<AnyKey, AnyValue> t ){ if(t != null && t.left != null) { t = findMin(t.left); } return t; } 

Does anyone see any problems with my method. All logic makes sense to me. When I ran my JUnit test cases,

 RedBlackTree testTree = new RedBlackTree<Integer,Integer>(); for(int c=0;c<1000;c++) { testTree.put(c, c); } int attempt = 60; testTree.remove(attempt); assertEquals(attempt - 1,testTree.get(attempt - 1).intValue()); 

Test failed