Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
For an arbitrary spay tree with n nodes, if we perform n find operations, is there a way of generalizing what the tree would look like after n operations and proving it mathematically?
One such example (Sequential Access Theorem): if the splay tree has the elements V1, V2,..., Vn, where V1 ≤ V2 ≤ ... ≤ Vn. And the find operations are in the order: V1, V2,..., Vn.
AFAIK, there is no general expected form for a splay tree given some arbitrary search sequence. Despite this, it is known to perform as good as any balanced BST. For some specific kind of search sequences with special properties, splay tree is known to perform better. Although, it is open whether it performs optimally for all kind search sequence (Dynamic Optimality Conjecture).
As for the latter case where you search items in sorted order, you are interested with the sequential access on splay tree. This is one of the special sequence that a splay tree handles efficiently. Although the form of the tree may vary based on the tree's initial form, the way the tree changes can be characterized and analyzed. The original analysis of Tarjan can be found here. You can also check this alternative analysis if you have no access to the previous paper.
