Sequential access in splay trees takes linear time
\textit{D. D. Sleator} and the present author [J. Assoc. Comput. Mach. 32, 652-686 (1985)] have invented a form of self-adjusting binary search tree called the splay tree. On any sufficiently long access sequence, splay trees are as efficient, to within a constant factor, as both dynamically balanced and static optimum search trees. The authors of the mentioned paper have made a much stronger conjecture; namely, that on any sufficiently long access sequence and to within a constant factor, splay trees are as efficient as any form of dynamically updated search tree. This dynamic optimality conjecture implies as a special case that accessing the items in a splay tree in sequential order takes linear time, i.e. O(1) time per access. In this paper we prove this special case of the conjecture, generalizing an unpublished result of Wegman. Our sequential access theorem not only supports belief in the dynamic optimality conjecture but provides additional insight into the workings of splay trees. As a corollary of our result, we show that splay trees can be used to simulate output-restricted deques (double-ended queues) in linear time. We pose several open problems related to our result.
- Self-adjusting multi-way search trees
- Splaying a search tree in preorder takes linear time
- On the deque conjecture for the splay algorithm
- Randomized splay trees: Theoretical and experimental results.
- On the sequential access theorem and deque conjecture for splay trees
- A priority queue with the time-finger property
- Splaying preorders and postorders
- A unified access bound on comparison-based dynamic dictionaries
- On the hierarchy of distribution-sensitive properties for data structures
- A study on splay trees
- Alternatives to splay trees with O( n) worst-case access times
- Inorder traversal of splay trees
- A history of distribution-sensitive data structures
- Greedy is an almost optimal deque
- Self-adjusting binary search trees: what makes them tick?
- scientific article; zbMATH DE number 65701 (Why is no real title available?)
- scientific article; zbMATH DE number 140488 (Why is no real title available?)
- scientific article; zbMATH DE number 2050892 (Why is no real title available?)
- On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
- File maintenance: when in doubt, change the layout!
- scientific article; zbMATH DE number 910910 (Why is no real title available?)
- Smooth heaps and a dual view of self-adjusting data structures
- A new path from Splay to dynamic optimality
- Belga B-trees
- scientific article; zbMATH DE number 7758335 (Why is no real title available?)
- The group access bounds for binary search trees
This page was built for publication: Sequential access in splay trees takes linear time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1072706)
