Sequential access in splay trees takes linear time

Research output: Contribution to journalArticlepeer-review

52 Scopus citations

Abstract

Sleator and Tarjan 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. Sleator and Tarjan 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.

Original languageEnglish (US)
Pages (from-to)367-378
Number of pages12
JournalCombinatorica
Volume5
Issue number4
DOIs
StatePublished - Dec 1 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Keywords

  • AMS subject classification (1980): 68E05, 68C25, 05C05, 68E10

Fingerprint Dive into the research topics of 'Sequential access in splay trees takes linear time'. Together they form a unique fingerprint.

Cite this