private STNode<Key, Value> put(STNode<Key, Value> x, Key key, Value val,
			boolean update)
	{
		STNode<Key, Value> savedRoot = x;

		// Save parent of x while travelling down. Needed to insert x
		STNode<Key, Value> p = null;
		while (x != null)
		{
			p = x;
			int cmp = key.compareTo(x.key);
			if (cmp < 0)
			{
				if (!update)
					p.N++;
				x = x.left;
			}
			else if (cmp > 0)
			{
				if (!update)
					p.N++;
				x = x.right;
			}
			else
			{// cmp == 0. Key already present. Update the value and return
				assert update;
				x.val = val;
				return savedRoot;
			}
		}

		assert !update;
		STNode<Key, Value> t = new STNode<Key, Value>(key, val, 1, 0);

		// if tree is empty
		if (p == null)
		{
			root = t;
			return root;
		}

		boolean adjustHeight = false;
		if (key.compareTo(p.key) < 0)
		{
			p.left = t;
			if (p.right == null)
				adjustHeight = true;
		}
		else
		{
			p.right = t;
			if (p.left == null)
				adjustHeight = true;
		}

		if (adjustHeight)
		{
			x = savedRoot;
			while (x != null)
			{
				x.h++;
				int cmp = key.compareTo(x.key);
				if (cmp < 0)
					x = x.left;
				else if (cmp > 0)
					x = x.right;
				else
					// cmp = 0
					break;
			}
		}
		return savedRoot;
	}