On the sequential access theorem and deque conjecture for splay trees

摘要

We give a new, simple proof for the sequential access theorem for splay trees. For an n-node splay tree, our bound on the number of rotations is 4.5n, with a smaller constant than the bound of 10.8n concluded by Tarjan. We extend our proof to prove the deque conjecture for output-restricted deques. Our proofs provide additional insights into the workings of splay trees.