On the Dynamic Finger Conjecture for Splay Trees. Part 2: The Proof

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1995
Accession Number
AD1020228

Entities

People

  • Richard Cole

Organizations

  • Courant Institute of Mathematical Sciences, NYU

Tags

Fields of Study

  • Computer science

Readers

  • Cybersecurity.
  • Graph Algorithms and Convex Optimization.
  • Vision Science/Vision Psychology/Cognitive Neuroscience.