On the dynamic finger conjecture for splay trees. Part II: The proof

Research output: Contribution to journalArticlepeer-review

Abstract

The following result is shown: On an n-node splay tree, the amortized cost of an access at distance d from the preceding access is O(log(d+1)). In addition, there is an O(n) initialization cost. The accesses include searches, insertions, and deletions.

Original languageEnglish (US)
Pages (from-to)44-85
Number of pages42
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 II: The proof'. Together they form a unique fingerprint.

Cite this