On the Dynamic Finger Conjecture for splay trees extended abstract

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The Dynamic Finger Conjecture for splay trees states that the cost of m searches on an n-node splay tree is O(m + n + Σ log(|ij - ij-1$/|), where the sum is from i = 1 to m and the jth access is to the ijth item in symmetric order (the i0th item is the item originally at the root of the tree). In other words, the amortized cost of an access is O(1 + log d), where the current access is at distance d from the previous access (distance being measured in terms of the number of items straddled by the two successive accesses); in addition, there is an additive O(n) initialization cost. A bound on the cost is obtained.

Original languageEnglish (US)
Title of host publicationProc 22nd Annu ACM Symp Theory Comput
PublisherPubl by ACM
Pages8-17
Number of pages10
ISBN (Print)0897913612
StatePublished - 1990
EventProceedings of the 22nd Annual ACM Symposium on Theory of Computing - Baltimore, MD, USA
Duration: May 14 1990May 16 1990

Publication series

NameProc 22nd Annu ACM Symp Theory Comput

Other

OtherProceedings of the 22nd Annual ACM Symposium on Theory of Computing
CityBaltimore, MD, USA
Period5/14/905/16/90

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'On the Dynamic Finger Conjecture for splay trees extended abstract'. Together they form a unique fingerprint.

Cite this