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

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

2007-07-14

arxiv.org/abs/0707.2160v1

Computer Science

Data Structures and Algorithms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-254104