A Binary Search Tree with the Unified Bound

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.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-12
DOI
https://doi.org/10.48550/arxiv.2611.16272
Primary Topic
Algorithms and Data Compression
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

A Binary Search Tree with the Unified Bound

Haoran Qi, Hanzhi Wang, Yang Cao
arXiv (Cornell University)
Algorithms and Data Compression
preprint

A Binary Search Tree with the Unified Bound

Haoran Qi, Hanzhi Wang, Yang Cao
preprint en

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.

arXiv (Cornell University)
Algorithms and Data Compression
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon