On the dynamic finger conjecture for splay trees. Part I: Splay sorting log n-block sequences

Research output: Contribution to journalArticlepeer-review

Abstract

The splay tree is a binary search tree in which each access will cause some rotations to be performed on the tree. A special instance of the splay sorting problem related to the dynamic finger conjecture is investigated. The splay sort conjecture is proven in a variety of sequences. A number of features and several new techniques for proving amortized results are introduced.

Original languageEnglish (US)
Pages (from-to)1-43
Number of pages43
JournalSIAM Journal on Computing
Volume30
Issue number1
DOIs
StatePublished - 2000

Keywords

  • Amortized analysis
  • Binary search tree
  • Finger search tree
  • Splay tree

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'On the dynamic finger conjecture for splay trees. Part I: Splay sorting log n-block sequences'. Together they form a unique fingerprint.

Cite this