CS Paper Radar

A Refined Analysis of the Sequential Access Theorem for Splay Trees

Naonori Kakimura, Yoshihiko Terai

cs.DS ·submitted 2026-09-17 06:12 UTC · v2
theory

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$.

Closest papers

Nearest neighbours by meaning across the whole index.

A Binary Search Tree with the Unified Bound

cs.DS ·2026-11-12 ·Yang Cao, Haoran Qi, Hanzhi Wang
theory similarity 0.70
Abstract

We give a deterministic online binary search tree (BST) that satisfies the unified bound of Iacono [SODA 2001], which subsumes the working-set and dynamic-finger bounds: it serves every sequence $X$ of $m$ searches on $n$ keys at total cost $O(m+\mathrm{UB}(X))$, and every single search at cost $O(\log n)$. Previously, no BST was known to satisfy the unified bound, even offline. As a consequence, the dynamic optimality conjecture implies Iacono's conjecture that splay trees satisfy the unified bound. We also show that the unified bound is $O((m+n)(1+\log c_σ))$ on every sequence of searches that avoids a fixed permutation $σ$, where $c_σ$ is the Füredi-Hajnal limit of $σ$. Hence every BST that satisfies the unified bound, including ours, serves such sequences at this cost. For permutations this bound is tight, and it improves the previous upper bound $O(nc_σ^2)$ on the optimal cost, due to Berendsohn, Kozma and Opler [STOC 2024]. Finally, we extend the tree to support insertions and deletions: a sequence $X$ of $m$ operations, starting from $n_0$ keys, costs $O(n_0+m+\mathrm{UB}(X))$ in total, where $\mathrm{UB}$ is now the extension of the unified bound to insertions and deletions by Bădoiu, Cole, Demaine and Iacono [TCS 2007]. Hence, if splay trees are dynamically optimal for searches, insertions and deletions, then they serve every such sequence at this total cost as well.

0.25

Optimal Pattern-Avoidance Bounds for Binary Search Trees

cs.DS ·2026-11-15 ·Anita Dürr, Arturo Merino, Karol Węgrzycki, Sorrachai Yingchareonthawornchai
theorycode/datahot direction similarity 0.68
Abstract · 37 pages. Submitted to STOC 2027. Publicly available at https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/906.pdf

Self-adjusting binary search trees (BSTs) perform better than balanced BSTs if the access sequence has additional structure. For example, splay trees serve a sequential access sequence in linear time. Pattern avoidance captures regularity in an access sequence and unifies several classic examples of efficient BST access, such as deque and traversal sequences. A central question is how well a BST algorithm can exploit a pattern-avoiding access sequence. We present an online BST algorithm that serves an access sequence avoiding a permutation pattern $π$ in linear time, matching the information-theoretic lower bound. The algorithm does not need to know that pattern $π$ a priori. Our results answer an open problem asked by [Kozma 2016, Problem 44, strong variant]. Previously, the best known offline bound was optimal only for constant-size patterns [Berendsohn, Kozma, and Opler, STOC'24], and the best known online bound was superlinear [Chalermsook, Pettie, Yingchareonthawornchai, SODA'24] even for a constant-size pattern. As a corollary, our BST algorithm yields an optimal sorting algorithm for a pattern-avoiding sequence that supports online insertions. Previously, an optimal sorting algorithm was achieved using a mergesort-like approach [Opler, FOCS'24] in a batch setting. A key technique is to apply recursive split decomposition [Chalermsook, Chuzhoy, Saranurak, ToC'23] jointly in time and space, along with the Marcus-Tardos proof of the Stanley-Wilf conjecture. We show that the framework can be implemented online using $k$-finger BSTs, which is of independent interest. Finally, this framework also yields a constant-factor-approximation FPT algorithm in the offline setting.

0.41

Amortized Cell-Probe Lower Bounds for Dynamic Boolean Problems

cs.DS cs.CC ·2026-11-08 ·Young Kun Ko
theoryhot direction similarity 0.66
Abstract · 20 pages

We prove the first unconditional amortized $Ω\big((\log N/\log\log N)^2\big)$ cell-probe lower bound for a Boolean dynamic problem. For insert-only multiphase Disjointness with $N$ query sets over $[N]$ and word size $w=Θ(\log N)$, a fixed distribution of interleaved insertions and queries forces this expected average cost per operation, excluding preprocessing. The bound allows sufficiently small constant error for each query of every fixed legal sequence and imposes no restriction on individual operation costs. It transfers to incremental directed reachability, incremental subgraph connectivity, and fully dynamic triangle detection. We also prove $t_q=Ω\big((\log N/\log(t_uw))^2\big)$ for amortized insertion time $1\le t_u=N^{o(1)}$ and expected query time $t_q$, when the number of insertions before the final query is not announced in advance. We reach the quadratic-logarithmic scale with bounded error by combining interleaving with the 2.5-round communication framework [Ko26a, Ko26b] and controlling errors among accepted simulations.

0.27

Succinct Representation of Search Trees on Trees

cs.DS ·2026-09-18 ·Seungbum Jo, Nodari Sitchinava
similarity 0.64
Abstract

A search tree on trees (STT) is a data structure for performing a search for a target vertex in a reference tree. A standard binary search tree is a special case of an STT, where the reference tree is a path of totally ordered elements. In this paper, we study the problem of succinct representation of STTs. We consider two cases: (1) general search trees on trees, and (2) Steiner-closed search trees on trees [Bose et al. TALG 2023]. For both cases, we present representations that can be constructed in polynomial time and achieve optimal space up to the lower-order additive terms. We also present data structures for supporting fast traversals of both general and Steiner-closed STTs. For general STTs our data structure still takes optimal space up to lower-order additive terms.

0.20

Online and Fully-Dynamic Sorting

cs.DS ·2026-11-16 ·Yossi Azar, Sujoy Bhore, Devdan Dey, Debmalya Panigrahi, Or Vardi +1 more
theory similarity 0.63
Abstract

Online sorting asks how to place $n$ sequentially arriving elements in an array to minimize the sum of absolute differences between consecutive elements. Fully-dynamic sorting further extends the problem to allow both element insertions and deletions. Without recourse, these problems face strong lower bounds on the competitive ratio: $Ω(\sqrt{n})$ for online sorting and $Ω(n)$ for fully-dynamic sorting. In sharp contrast, we show that allowing only poly-logarithmic recourse yields at least exponential improvements in the competitive ratio for both problems:(1) Our main algorithmic result is a deterministic fully-dynamic sorting algorithm that is $O(\log^2 n)$-competitive and has $O(\log^4 n)$ amortized recourse per update. We complement this with a lower bound showing that any deterministic algorithm with any $O(\mathrm{polylog}(n))$ competitive ratio has amortized recourse at least $Ω(\sqrt{\log n})$.(2) For the insertion-only setting, we establish a family of approximation--recourse tradeoffs, including $O(\log\log n)$ competitive ratio with $O(\log\log n)$ amortized recourse. Given the lower bound in the fully-dynamic case, this result shows that the insertion-only problem yields exponentially better bounds than the fully-dynamic one.(3) Finally, we show that the stronger approximation-recourse tradeoff for the insertion-only case extends to the fully-dynamic setting when the array has $(1+\varepsilon)n$ space.

0.12

Dynamically optimal weight-balanced binary search trees

cs.DS ·2026-10-21 ·John Iacono, Akash Pareek
similarity 0.63
Abstract

In STOC 1972, J{ü}rg Nievergelt and Edward M.~Reingold introduced the $BB[α]$-tree, also known as a \emph{weight-balanced} tree, which for any $α\in (0,\frac{1}{2}]$ is a binary search tree where every node with induced subtree size $s$ has children with induced subtree sizes at least $α(s+1)-1$. A new rotation-based binary search tree, the \emph{PopTree}, is introduced. The PopTree stores $n$ elements and is a $BB[\tfrac1{20}]$-tree after the execution of each search and a $BB[\tfrac1{729}]$-tree at all times, notably while rebalancing. For any constant $α$, its performance on search sequences of length $Ω(n \log n)$ is proved to be within a constant factor (which can depend on $α$) of the optimal offline rotation-based binary search tree that maintains the $BB[α]$ balance invariant.

0.23

Incremental Minimum Spanning Trees on a Napkin

cs.DS ·2026-11-03 ·Lucian Bicsi, Adrian Budău
similarity 0.61
Abstract · 20 pages, 5 figures, 3 tables

In the incremental minimum spanning forest problem, weighted edges arrive one at a time. After each insertion we must report the edge that leaves the minimum spanning forest, and queries ask for the bottleneck distance of two vertices: the smallest possible maximum edge cost on a path between them. Link-cut trees solve both in $O(\log n)$ amortized time. In 2021 we wrote the folklore BottleneckTree, a short competitive-programming structure that stores one parent pointer and one cost per vertex, and conjectured that it also runs in $O(\log n)$ amortized time. We show that this conjecture is false: on a family of inputs, its amortized cost per operation is $Ω(\sqrt{n})$. We then present a structure with the same state, two arrays and a single loop, and prove that it runs in $O(\log n)$ amortized time per insertion and per query. Unlike the AM-tree of Ding, Gu and Sun, which attains the same bound, it stores no subtree sizes and maintains no balance invariant. For a connected graph with distinct costs, the structure can be viewed as an implicit link-cut tree on the Kruskal reconstruction tree: each rotation corresponds to exactly one preferred-child change, and each skip acts on a stale path-parent pointer. In experiments it is 1.3-2.1 times faster than the folklore BottleneckTree on insertions, up to 480 times faster on its adversarial input, and 6.3-16 times faster than an explicit link-cut tree.

0.32

Tree Edit Distance: Near-Linear-Time Approximate, Sublinear, and Dynamic

cs.DS ·2026-10-15 ·Bingbing Hu, Tomasz Kociumaka, Jakob Nogler, Barna Saha
published similarity 0.61
Abstract · SODA 2027

Tree edit distance (TED), the analog of string edit distance (ED) for hierarchical data, is the minimum number of node insertions, deletions, and substitutions transforming one labeled rooted ordered tree into another. We narrow polynomial gaps between TED and ED in near-linear-time approximation, sublinear algorithms, and dynamic algorithms. We give an $n^{o(1)}$-approximation in $O(n)$ time and, for every $0<δ<1$, a $(\log n)^{O(1/δ)}$-approximation in $O(n^{1+δ})$ time. This improves the previous near-linear-time $O(\sqrt n)$-approximation [Boroujeni et al., STOC'19] and brings TED to parity with ED in this regime up to polylogarithmic factors. With query access to the balanced-parentheses (Euler-tour) representation of the input trees, we give the first sublinear-time TED algorithm: for every $τ\in[1,n]$, it computes a $τn^{o(1)}$-approximation of $1+\mathrm{ted}$ in $O(n/τ)$ time. For dynamic TED, we give an exact algorithm with amortized update time $\tilde{O}(k^7)$ and a $(1+\varepsilon)$-approximation with amortized update time $\tilde{O}_{\varepsilon}(k)$, where $k$ caps the distance that must be reported. The exact algorithm is the first to beat recomputation in a nontrivial parameter regime. The approximation improves prior dynamic guarantees [Das et al., FOCS'25] and cannot be significantly improved in any parameter regime without a breakthrough for static $(1+\varepsilon)$-approximation of ED. All results use dynamic programming on a new hierarchical tree decomposition, analogous to partitioning strings into blocks of geometrically decreasing sizes. It combines structural properties previously achieved only in isolation, providing a framework for transferring algorithmic ideas from ED to TED, with additional ingredients addressing the obstacles in each computational setting.

0.34