On the dynamic finger conjecture for splay trees
Richard Cole · 1990
The Dynamic Finger Conjecture for splay trees states that the cost of m searches on an n-node splay tree isInwhere the jth access is to the ij th 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 0(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.In this paper, the following bound is shown:So instead of an O(n) initialization cost, an O(n log log n) initialization cost is demonstrated.Due to lack of space, in this extended abstract only some elements of the proof are shown.A complete proof outline is not given.