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

2007/07/14 by Seth Pettie, Pettie, Seth · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #cs.DS #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.0707.2160

arxiv created 2007/07/14 · openalex publication_date 2007/07/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Amortized efficiency of list update and paging rules
• Self-Adjusting Heaps
• Self-adjusting binary search trees

Cited by

• On the zone of a circle in an arrangement of lines
• The Greedy Binary Search Tree is Non-trivially Competitive

Related

• Random planar trees and the Jacobian conjecture
• Splay trees are almost dynamically optimal
• A coefficient related to splay-to-root traversal, correct to thousands of decimal places
• Sharp Bounds on Davenport-Schinzel Sequences of Every Order
• Greedy Is an Almost Optimal Deque