{"ID":23475035,"CreatedAt":"2026-09-18T01:09:05.407443952Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.19746","arxiv_id":"2609.19746","title":"A Refined Analysis of the Sequential Access Theorem for Splay Trees","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$.","short_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...","url_abs":"https://arxiv.org/abs/2609.19746","url_pdf":"https://arxiv.org/pdf/2609.19746v1","authors":"[\"Naonori Kakimura\",\"Yoshihiko Terai\"]","published":"2026-09-17T06:12:46Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}