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