class RedBlackBSTWithNoExtraMemory extends BST<Key, Val> {

    @Override
    public boolean remove(Key key) {
        if (key == null)
            throw new IllegalArgumentException("key not null");
        if (!contains(key)) return false;
        if (!isRed(root.left) && !isRed(root.right))
            setRed(root);
        boolean res = super.remove(key);
        if (!isEmpty()) setBlack(root);
        return true;
    }

}