For a given binary-search tree obtain an isomorphic splay tree

Question

I will assume that the reader is familiar with some undergraduate algorithms and data structures. To people who are not familiar with splay trees I recommend to read through this link : https://en.wikipedia.org/wiki/Splay_tree

An interesting problem is :

Given a binary search tree $T$ with $n$ nodes. Find the sequence $S$ of operations (find, insert, delete) to obtain a Splay tree $T_{Splay}$, such that $T_{Splay} = T$.

For example the splay tree equal to this one

could be generated by the following sequence:

Insert(3), Insert(2), Insert(1), Find(2)

My questions are:

• Is it possible to obtain $T_{Splay}$ for every binary search tree $T$?
• If the answer for the above question is positive, find an algorithm to solve this problem. What about its complexity?
• If the answer for the above question is positive, how long need to be the sequence $S$?

Unfortunately I can't find any solutions to these problems which means that either it could be hard or simply uninteresting for most of us. I found also a few links about similar problems but none of them could be applied to this case. The full list of links below:

• https://stackoverflow.com/questions/14564437/a-sequence-that-forms-the-same-avl-and-splay-trees
• https://stackoverflow.com/questions/22413727/determining-if-a-binary-search-tree-can-be-constructed-by-a-sequence-of-splay-tr

Thanks for any answers,
Bartosz Bednarczyk

Answer 1

It can be done with a linear number of operations.

Suppose you start with an arbitrary given tree $T_0$ over keys $[n]$ and want to reach an arbitrary given $T$ over keys $[n]$ using splay operations. (In case we have to start with the empty tree, just insert $[n]$ in any order.)

A result of Cleary [*1] (see also Lucas [*2]) shows that you can get from $T_0$ to $T$ using $O(n)$ normal rotations, even if you restrict yourself to rotations at the root and at the right child of the root.

Let's try to simulate these restricted rotations with splay operations. Rotation at the root is easy, just splay the corresponding child.

What about rotations at the right child? There are two cases (see figure). The first case (left to right) is easy: splay y, then splay x.

The second case (right to left) is more tricky:

Suppose z has a right child t. Then we can:

splay t, then splay z, then splay x, obtaining the required rotation.

We had to assume that t exists. We can make sure of this, by inserting an $\infty$ key element in the beginning and making sure that it will always remain a leaf. We can make sure it is a leaf in the beginning, for instance by splaying $\infty$, and then 1,2,3,...,n. Afterwards, t $=\infty$ is never splayed, except if the above situation arises where it is the right child of z, and then we can see that it stays a leaf after the transformation.

In the end, we just need to clip away this leaf and get the target tree $T$. This last step is a bit of cheating, since a proper splay deletion would clip away the leaf, then splay its parent.

We can get around this cheating by deleting $\infty$ earlier, i.e. the last time when the above right-to-left transformation involving $\infty$ happens. Then, after the splay z and before the splay x steps, we can do a proper splay-delete t (t $= \infty$) operation, and since t is the child of the root at that time, no unintended side-effect happens.

A (perhaps simpler) alternative formulation is that, if in the above right-to-left transformation z has no right child, then we do the sequence: insert(n+1), splay(z), delete(n+1), splay(x). (assuming that insert works by inserting as a leaf and then splaying an element).

[*1] S. Cleary, Restricted rotation distance between binary trees, Inform. Process. Lett. 84 (2002) 333–338

[*2] J. Lucas, A direct algorithm for restricted rotation distance, Inform. Process. Lett. 90 (2004) 129–134