Metraipolis › archive › dc_eac58de49853
A Refined Analysis of the Sequential Access Theorem for Splay Trees — arXiv:2609.19746
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.19746
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-10T05:39:45.771Z
- SHA-256 of the archived text
ca477c3d2868b51218ee1af9be71589c9dccf7fc980fd1cd9cee96a172b0b417- Stable URL of this page
https://metraipolis.com/documento/dc_eac58de49853
How to cite
A Refined Analysis of the Sequential Access Theorem for Splay Trees — arXiv:2609.19746 — arXiv (en), https://arxiv.org/abs/2609.19746 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_eac58de49853 (Metraipolis archive dc_eac58de49853, sha256 ca477c3d2868b51218ee1af9be71589c9dccf7fc980fd1cd9cee96a172b0b417)
BibTeX
@misc{dceac58de49853,
title = {A Refined Analysis of the Sequential Access Theorem for Splay Trees — arXiv:2609.19746},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.19746},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_eac58de49853; sha256 ca477c3d2868b51218ee1af9be71589c9dccf7fc980fd1cd9cee96a172b0b417},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.19746. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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$. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-18 in cs.DS). Categorie arXiv: Data Structures and Algorithms (cs.DS). Pagina del lavoro: https://arxiv.org/abs/2609.19746 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-10T05:08:06.548Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).