Prove that a sequence of increasing find operations on a splay tree takes $\mathcal{O}(n)$ time

Question

When studying about splay trees, I found the following statement:

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 $\mathcal{O}(n)$ ($n$ is the number of nodes in the tree).

I looked around, but haven't been able to find anything. Can this be proven formally? Or shown that it is true?

Answer 1

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.