private STNode<Key, Value> delete(STNode<Key, Value> x, Key key)
	{
		STNode<Key, Value> savedRoot = x;

		STNode<Key, Value> p = null;
		while (x != null)
		{
			int cmp = x.key.compareTo(key);
			if (cmp < 0)
			{
				p = x;
				p.N--;
				x = x.left;
			}
			else if (cmp > 0)
			{
				p = x;
				p.N--;
				x = x.right;
			}
			else
			// cmp == 0
			{
				if (p.left == x && x.left == null)
					p.left = x.right;
				else if (p.right == x && x.left == null)
					p.right = x.right;
				else if (p.left == x && x.right == null)
					p.left = x.left;
				else if (p.right == x && x.right == null)
					p.right = x.left;
				else
				// non-empty left and right subtrees
				{
					// replace with in-order successor
					STNode<Key, Value> s = min(x.right);
					x.key = s.key;
					x.val = s.val;
					deleteMin(x.right);
				}
			}
		}
		return savedRoot;
	}