On the dynamic finger conjecture for splay trees. Part I: Splay sorting log n-block sequences
A special case of the dynamic finger conjecture is proved; this special case introduces a number of useful techniques.
splay tree binary search tree amortized analysis finger search tree