如何在RedBlackTree实现中修复删除？

这是我正在使用的RedBlackTree的实现（来自Mark Allen Weiss，Data Structures

public class RedBlackTree<AnyKey extends Comparable, AnyValue extends Comparable> implements MyTreeMap{ 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 header; // Used in place of a null link. Will always be colored black. private RedBlackNode nullNode; private RedBlackNode current; private RedBlackNode parent; private RedBlackNode grand; private RedBlackNode great; public RedBlackTree( ){ nullNode = new RedBlackNode( null, null ); nullNode.left = nullNode.right = nullNode; header = new RedBlackNode( null, null ); header.left = header.right = nullNode; } private final int compare( AnyKey theKey, RedBlackNode 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( 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 rotate( AnyKey item, RedBlackNode 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  RedBlackNode rotateWithLeftChild( RedBlackNode k2 ){ RedBlackNode k1 = k2.left; k2.left = k1.right; k1.right = k2; return k1; } @Override public void put(AnyKey x, AnyValue y) { RedBlackNode 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  RedBlackNode rotateWithRightChild( RedBlackNode k1 ){ RedBlackNode k2 = k1.right; k1.right = k2.left; k2.left = k1; return k2; } /** * Node in the red black tree. * @author Letian Sun * @param  can be any object type * @param  can be any object type */ private static class RedBlackNode{ AnyKey key; AnyValue value; RedBlackNode left; RedBlackNode right; int color; RedBlackNode( AnyKey theKey, AnyValue theValue ){ this( theKey, theValue, null, null ); } RedBlackNode( AnyKey theKey, AnyValue theValue, RedBlackNode lt , RedBlackNode rt ) { key = theKey; value = theValue; left = lt; right = rt; color = RedBlackTree.BLACK; } public String toString() { return "element:" + key.toString() + " times:" + value.toString(); } } 

我正在尝试编写作者没有写的删除方法。 这是我到目前为止所拥有的

 @Override public void remove( AnyKey x ){ header.right = remove( x, header.right ); } private RedBlackNode remove( AnyKey x, RedBlackNode t ){ if( t == nullNode ) return t; // Item not found; do nothing int compareResult = x.compareTo( t.key ); 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 findMin(RedBlackNode t ){ if(t != null && t.left != null) { t = findMin(t.left); } return t; } 

有没有人看到我的方法有任何问题。 所有的逻辑都对我有意义。 当我运行我的JUnit测试用例时，

 RedBlackTree testTree = new RedBlackTree(); 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()); 

测试失败了