Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture
| dc.creator | Pettie, Seth | |
| dc.date | 2007-07-14 | |
| dc.date.accessioned | 2026-07-07T08:18:27Z | |
| dc.date.available | 2026-07-07T08:18:27Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/0707.2160 | |
| dc.identifier | http://arxiv.org/abs/0707.2160 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/134437 | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture | |
| dc.type | text |