Aqui está a implementação do RedBlackTree que estou usando (de 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();
     }
  }

Estou tentando escrever o método de remoção que o autor não escreveu. Aqui está o que eu tenho até agora

@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;
}

Alguém vê algum problema com o meu método. Toda a lógica faz sentido para mim. Quando executei meus casos de teste JUnit,

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());

O teste falhou