private STNode<Key, Value> put(STNode<Key, Value> x, Key key, Value val)
	{
		// Found the place for the given key
		if (x == null)
			return new STNode<Key, Value>(key, val, 1, 0);

		int cmp = key.compareTo(x.key);
		if (cmp < 0)
			x.left = put(x.left, key, val);
		else if (cmp > 0)
			x.right = put(x.right, key, val);
		else
			x.val = val;
		// Update the size and height of each node above
		x.N = size(x);
		x.h = height(x);

		// On the way up balance the subtree rooted at x
		return balance(x);
	}