= Solution
Write $y=x+1$. After <splaying> on $x$, that key is at the root, and $y$ is the smallest key in its right <subtree>. This uses the <integer> assumption: no stored key lies strictly between $x$ and $y$. Thus $y$ has an empty left <subtree> while it remains within the right <subtree> of $x$.
Now perform ordinary bottom-up <splaying> on $y$. Until the final step involving $x$, all <tree rotations> occur below $x$ and leave it at the root. There are only two possible final cases.
* If $y$ is the right child of $x$, a single <zig step> rotates $y$ above $x$, placing $x$ immediately to its left.
* Otherwise $y$ is a grandchild of $x$. Its parent $p$ lies in the right <subtree> of $x$ and must satisfy $p>y$. Hence the last two directions are right then left. A <zig-zag step> rotates $y$ above $p$ and then above $x$, again placing $x$ immediately to its left. A right-right final configuration is impossible because $y$ is the minimum of this <subtree>.
Therefore \b[$x$ becomes the left child of $x+1$]. The argument applies more generally to <consecutive keys in a binary search tree>, even when their numerical difference is not one.
Back to article page
