On the Dynamic Finger Conjecture for Splay Trees. Part II: 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.