  We introduce a new technique to bound the asymptotic performance of splaytrees. The basic idea is to transcribe, in an indirect fashion, the rotationsperformed by the splay tree as a Davenport-Schinzel sequence S, none of whosesubsequences are isomorphic to fixed forbidden subsequence. We direct thistechnique towards Tarjan's deque conjecture and prove that n deque operationsrequire O(n alpha^*(n)) time, where alpha^*(n) is the minimum number ofapplications of the inverse-Ackermann function mapping n to a constant. We areoptimistic that this approach could be directed towards other open conjectureson splay trees such as the traversal and split conjectures.
The basic idea is to transcribe, in an indirect fashion, the rotations performed by the splay tree as a Davenport-Schinzel sequence S, none of whose subsequences are isomorphic to fixed forbidden subsequence.