arXiv preprint ·
A Refined Analysis of the Sequential Access Theorem for Splay Trees
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
A splay tree is a self-adjusting binary search tree that allows access, insertion, and deletion to be performed in amortized $O(\log n)$ time, where $n$ is the number of stored elements. The sequential access theorem states that, when the elements of a splay tree are accessed in increasing order, the amortized cost per operation becomes a constant. In this paper, we show that the upper bound for this constant is at most $5.5$ by refining the existing analysis and introducing a new potential function. Furthermore, we complement our result by showing that there exists a splay tree for which the constant is lower-bounded by almost $4$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Spectral Gap of Down-Up Walks via Trickle-Down: A Simplified and Sharpened Analysis
Succinct Representation of Search Trees on Trees
Universal set families for maximization of nonnegative submodular and XOS functions
The Complexity of Computing Class Probabilities in BID Probabilistic Databases
A $(1+1/\sqrt{2})$-Approximation for the Multiple-Depot Traveling Salesman Problem
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.