Here is a helper fact.
(Simple cost of splaying) Let $c(v)$ be the time it takes to find an element $v$ in a splay tree. There exists a constant $c_0$ independent of the splay tree and $v$ such that $c(v)\le c_0d(v)$, where $d(v)$ is the depth of $v$.
Here is the sketch of a proof.
There are two tasks that contribute to $c(v)$.
- To locate $v$ by going from the root downwards to the $v$, which takes at most $c_1d(v)$ time for some constant $c_1$.
- To splay $v$ to the root. It takes each splay operation of zig, zag, zig-zig, zag-zag, zig-zag, zag-zig some constant time to move $v$ nearer to the root by 1 or by 2, splaying $v$ to the root takes at most $c_2d(v)$ time for some constant $c_2$.
Let $c_0=c_1+c_2$. Proof is done.
Suppose we have a splay tree and a sequence of Find operations, where the elements we are searching for are in increasing order. Then the total time necessary to run the sequence is $O(n)$, where $n$ is the number of nodes in the tree.
Let $v_0, v_1,\cdots, v_m$ be an array of elements in increasing order.
It takes $O(n)$ to find $v_0$ (including splaying $v_0$ to the root).
What about finding the remaining $m$ elements?
- Finding $v_1$ when $v_0$ is at the root takes at most $c_0d_{v_0}(v_1)$ time, where $d_{v_0}(v_1)$ is the depth of $v_1$ in the splay tree with $v_0$ as the root. Note that splay tree is a binary search tree, $d_{v_0}(v_1)$ is at most one one more than the number of elements between $v_0$ and $v_1$ exclusively.
- Finding $v_2$ when $v_1$ is at the root takes at most $c_0d_{v_1}(v_2)$ time, where $d_{v_1}(v_2)$ is at most one one more than the number of elements between $v_1$ and $v_2$ exclusively.
- $\vdots$
- Finding $v_{m}$ when $v_{m-1}$ is at the root takes at most $c_0d_{v_{m-1}}(v_m)$ time, where $d_{v_{m-1}}(v_m)$ is at most one more than the number of elements between $v_{m-1}$ and $v_m$ exclusively.
So, the total time necessary to run the sequence of finding $v_1, v_2,\cdots,v_m$ is at most $c_0d(v_0, v_m)$, where $d(v_0, v_m)$ is at most one more than the number of elements between $v_0$ and $v_m$ exclusively, i.e., $d(v_0, v_m)\le m\lt n$.
So the total time necessary to run the sequence of finding $v_0, v_1, v_2,\cdots,v_m$ is at most $O(n) + c_0n$, which is $O(n)$ still.