0
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Figured that; the sequence theorem was quite straightforward to prove, and I couldn't find any other generalization. Found the Spay tree visualizer very helpful. $\endgroup$
    – addu390
    Commented Feb 28, 2022 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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