class RedBlackTree {

    public Pair<RedBlackNode<K, V>, Boolean> put(K key, V value) {
        if (root == null) {
            size++;
            root = new RedBlackNode<K,V>(key,value,null);
            return new Pair<RedBlackNode<K, V>, Boolean>( root, Boolean.TRUE );
        }
        RedBlackNode<K,V> node = root;

        while (true) {
        	int comp = comparator.compare(key, node.key);
            if (comp == 0 && !allowDuplicateKeys) {
                node.value = value;
                return new Pair<RedBlackNode<K, V>, Boolean>( node, Boolean.FALSE );
            }
            else if (comp < 0) {
                if (node.left != null) {
                    node = node.left;
                }
                else {
                    size++;
                    RedBlackNode<K, V> newNode = new RedBlackNode<K,V>(key, value, node); 
                    node.left = newNode;
                    fixAfterInsertion(newNode);
                    return new Pair<RedBlackNode<K, V>, Boolean>( newNode, Boolean.TRUE );
                }
            }
            else {
                if (node.right != null) {
                    node = node.right;
                }
                else {
                    size++;
                    RedBlackNode<K, V> newNode = new RedBlackNode<K,V>(key, value, node); 
                    node.right = newNode;
                    fixAfterInsertion(newNode);
                    return new Pair<RedBlackNode<K, V>, Boolean>( newNode, Boolean.TRUE );
                }
            }
        }
    }

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

}