IntTree<V> plus(final long key, final V value) {
        if (size == 0)
            return new IntTree<V>(key, value, this, this);
        if (key < this.key)
            return rebalanced(left.plus(key - this.key, value), right);
        if (key > this.key)
            return rebalanced(left, right.plus(key - this.key, value));
        // otherwise key==this.key, so we simply replace this, with no effect on balance:
        if (value == this.value)
            return this;
        return new IntTree<V>(key, value, left, right);
    }