class RedBlackTree {

    public void deleteEntry(RedBlackNode<K,V> p) {
        size--;

    	// If strictly internal, first swap position with successor.
	    if (p.left != null && p.right != null) {
            RedBlackNode<K,V> node = p.getSuccessor();
    	    swapPosition(node, p);
	    }

    	// Start fixup at replacement node, if it exists.
	    RedBlackNode<K,V> replacement = (p.left != null ? p.left : p.right);

    	if (replacement != null) {
	        // Link replacement to parent
	        replacement.parent = p.parent;
            if (p.parent == null) {
	    	    root = replacement;
            }
            else if (p.isLeftChild()) {
	    	    p.parent.left  = replacement;
            }
    	    else {
    		    p.parent.right = replacement;
            }

    	    // Null out links so they are OK to use by fixAfterDeletion.
	        p.left = p.right = p.parent = null;

            // Fix replacement
	        if (p.color == BLACK) {
    		    fixAfterDeletion(replacement);
            }
	    }
        else if (p.parent == null) { // return if we are the only node.
	        root = null;
	    }
        else { //  No children. Use self as phantom replacement and unlink.
	        if (p.color == BLACK) {
		        fixAfterDeletion(p);
            }

            if (p.parent != null) {
		        if (p.isLeftChild()) {
		            p.parent.left = null;
                }
		        else if (p == p.parent.right) {
		            p.parent.right = null;
                }
		        p.parent = null;
	        }
	    }
    }

    public  RedBlackTree(Comparator<K> comparator, boolean allowDuplicateKeys);
    public  RedBlackTree(RedBlackTree<K, V> tree);

}