Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture

Abstract

We introduce a new technique to bound the asymptotic performance of splay trees. 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. We direct this technique towards Tarjan's deque conjecture and prove that n deque operations require O(n alpha^*(n)) time, where alpha^*(n) is the minimum number of applications of the inverse-Ackermann function mapping n to a constant. We are optimistic that this approach could be directed towards other open conjectures on splay trees such as the traversal and split conjectures.

Cited by in corpus (7)

• Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
• Three Generalizations of Davenport-Schinzel Sequences
• A Study on Splay Trees
• On the zone of a circle in an arrangement of lines
• Self-Adjusting Binary Search Trees: What Makes Them Tick?
• Greedy Is an Almost Optimal Deque
• Better Analysis of GREEDY Binary Search Tree on Decomposable Sequences