= Splaying a chosen node into a leaf
{title2=$n\geq4\Longrightarrow\text{at most three successful splays suffice}$}
Every node of a <splay tree> with at least four distinct keys can become a <leaf of a rooted tree> using only successful <splaying> operations. At an extreme key, access that key and then its sole adjacent stored key; the <consecutive keys in a binary search tree> property makes the extreme key a leaf. For an interior key $x$ with two larger stored keys, take consecutive $a<x<b<c$ and access $c,a,b$; the mirror construction handles two smaller keys.
For a quick shape proof, use $k(L,R)$ for a node and its two <subtrees>. After accessing $c,a$, the right <subtree> of $a$ can only be $c(b(x,0),D)$, $c(x(0,b),D)$, $b(x,c(0,D))$, or $x(0,c(b,D))$, with outside <subtrees> $A$ below $a$ and $D$ above $c$. This follows by inspecting the final <zig step>, <zig-zig step> or <zig-zag step> that moves $a$ above the former root $c$. In each case, accessing $b$ yields $b(a(A,x),c(0,D))$, where $x$ is a leaf and $0$ denotes an empty <subtree>. These rotations prove the bound for arbitrary outside <subtrees>.
Back to article page
