= Solution
Use the usual bottom-up <splaying> operations. We prove the stronger result that \b[at most three successful calls suffice]. No insertions or deletions are needed.
If the chosen key $x$ is the minimum stored key, first perform <splaying> on $x$ and then on its immediate successor. The argument for <consecutive keys in a binary search tree> makes $x$ the left child of the successor with an empty right <subtree>; minimality makes its left <subtree> empty too. Hence $x$ is a <leaf of a rooted tree>. The maximum-key case is the mirror image.
Suppose $x$ is an interior key. Since at least four keys are stored, there are either two keys larger than $x$ or two smaller than $x$. In the former case choose four consecutive stored keys
$$
a<x<b<c,
$$
where $a$ is the predecessor of $x$, and $b,c$ are the next two successors. Perform \b[$\operatorname{Splay}(c),\operatorname{Splay}(a),\operatorname{Splay}(b)$].
Here is a complete check of the local shapes. After the first call, $c$ is the root. After the second, $a$ is the root; every key below $a$ is in its left <subtree> $A$, and every key above $c$ stays in the right <subtree> $D$ of $c$. These outside <subtrees> cannot interfere with the next search. Between $a$ and $c$ there are only $x,b$. The last step of <splaying> on $a$ is either a <zig step>, leaving $c$ as its right child; a <zig-zag step>, with the same result; or a <zig-zig step>, leaving some $p\in\{x,b\}$ as its right child with $c$ immediately to the right of $p$. Consequently the possible right <subtrees> of $a$ are exactly among these four forms, using $k(L,R)$ for a node with its left and right <subtrees>:
$$
\begin{array}{c|c}
\text{right subtree of }a\text{ after the second call}&\text{shape after splaying }b\\\hline
c\bigl(b(x,\varnothing),D\bigr)&b\bigl(a(A,x),c(\varnothing,D)\bigr)\\
c\bigl(x(\varnothing,b),D\bigr)&b\bigl(a(A,x),c(\varnothing,D)\bigr)\\
b\bigl(x,c(\varnothing,D)\bigr)&b\bigl(a(A,x),c(\varnothing,D)\bigr)\\
x\bigl(\varnothing,c(b,D)\bigr)&b\bigl(a(A,x),c(\varnothing,D)\bigr)
\end{array}
$$
Here an unexpanded $x$ or $b$ denotes a node with no children. Each row follows by the indicated one or two <tree rotations> in each bottom-up step. All rows end with $x$ as the right child of $a$, with both its <subtrees> empty. If instead two keys below $x$ are available, reflect the construction, exchanging left and right and reversing the order of keys. This proves <splaying a chosen node into a leaf> for every node of every <splay tree> of size at least four.
Back to article page
