1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Please add a reference to the original source. $\endgroup$ – John L. Jan 30 '19 at 12:17
  • 1
    $\begingroup$ What is $n$? $n$ cannot be the number of Find operations. Is $n$ the number of all nodes in the tree? $\endgroup$ – John L. Jan 30 '19 at 15:53
  • $\begingroup$ Yes, sorry about that, it's the number of nodes in the tree. Edited the question. $\endgroup$ – Wanderer Jan 30 '19 at 18:15
  • $\begingroup$ This fact should have been proved somewhere. Since I could not find it, I just wrote an answer. $\endgroup$ – John L. Jan 30 '19 at 19:44
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.