betaFeedback

WorksComputer Science

A Binary Search Tree with the Unified Bound

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 XX of mm searches on nn keys at total cost O(m+UB(X))O(m+\mathrm{UB}(X)), and every single search at cost O(log⁡n)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σ))O((m+n)(1+\log c_σ)) on every sequence of searches that avoids a fixed permutation σσ, where cσ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)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 XX of mm operations, starting from n0n_0 keys, costs O(n0+m+UB(X))O(n_0+m+\mathrm{UB}(X)) in total, where UB\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.

Introduction

A binary search tree (BST) stores the keys 1,…,n1,\ldots,n and serves a sequence of searches X=(x1,…,xm)X=(x_1,\ldots,x_m). In the standard model of dynamic BSTs [38, 40], which we state in the form of [20] that is equivalent up to a constant factor, each search starts at the root, walks down to the searched key, and may rearrange the nodes it has visited by rotations, and its cost is the number of nodes it touches. The cost of the optimal BST, OPT⁡(X)\operatorname{OPT}(X), is the least total cost of serving XX when the whole sequence is known in advance. Sleator and Tarjan conjectured that splay trees, the BSTs that move each searched key to the root by rotations, serve every sequence at cost O(OPT⁡(X))O(\operatorname{OPT}(X)) [38]. This dynamic optimality conjecture is still open, and much of the work around it asks which regularities of a search sequence an optimal tree can exploit. Each such regularity is expressed by a formula in XX that bounds OPT⁡(X)\operatorname{OPT}(X) from above.

Two regularities are classical. The working-set bound charges a search about the logarithm of the number of distinct keys searched since the previous search for the same key (a first search for a key is charged about log⁡2n\log_2 n). The dynamic-finger bound charges a search log⁡2(∣xt−xt−1∣+2)\log_2(|x_t-x_{t-1}|+2). Splay trees satisfy both, the second by a long proof of Cole [17], which builds on a special case proved by Cole, Mishra, Schmidt and Siegel [16], so the optimum satisfies both. Iacono [29] proposed a single bound that is at most both of them up to an additive O(m)O(m).

To state it, write ρ(u,t)\rho(u,t), for times u<tu<t, for the number of distinct keys among xu+1,…,xt−1x_{u+1},\ldots,x_{t-1}. The unified bound of XX is

UB⁡(X):=log⁡2(n+2)+∑t=2mmin⁡1≤u<tlog⁡2(∣xt−xu∣+ρ(u,t)+2).\operatorname{UB}(X) := \log_2(n+2) + \sum_{t=2}^{m}\min_{1\le u<t}\log_2\left(|x_t-x_u|+\rho(u,t)+2\right).

Choosing u=t−1u=t-1 recovers the dynamic-finger term, and choosing uu to be the previous search for the key xtx_t recovers the working-set term. Iacono’s definition, in the form of [1], minimizes over keys instead of times, and the two definitions agree up to an additive O(m)O(m) (Remark 7.4). The minimum lets each search use whichever earlier search is closest. Consider two scans that move rightwards through two distant parts of the key space, one step at a time, with their searches interleaved. Every key is searched once and consecutive searches are far apart, so the working-set and dynamic-finger bounds are both about mlog⁡nm\log n. Yet each search is adjacent to the search two steps earlier, so the unified bound is O(m)O(m).

This paper answers the following question, which underlies the conjecture of Iacono that splay trees satisfy the unified bound [29] and is stated as open in [9]: is there a BST that satisfies the unified bound, that is, serves every sequence XX at cost O(m+n+UB⁡(X))O(m+n+\operatorname{UB}(X))? Iacono stated his conjecture for searches in a static set of keys, as here. Bădoiu, Cole, Demaine and Iacono later stated it for searches, insertions and deletions [1]; we return to this form below. A weaker, offline form of the question, whether the optimal BST satisfies the unified bound, was also open [11, 12]. Since every BST costs at least OPT⁡(X)\operatorname{OPT}(X), a negative answer to the offline question would rule out the unified bound for every BST.

Iacono [29] gave a static comparison-based structure that serves XX in time O(m+UB⁡(X))O(m+\operatorname{UB}(X)), and Bădoiu and Demaine [3] a simpler one that also supports insertions, and deletions at an additional cost of O(log⁡log⁡n)O(\log\log n). The journal version [1] supports searches, insertions and deletions within the unified bound. These structures store the keys in several trees and are not BSTs. In the BST model all known bounds pay an overhead. Skip-splay trees [23], the layered working-set trees of Bose, Drouïlhet, Dujmović and Howat combined with skip-splay [4], the combination of trees of Demaine, Iacono, Langerman and Özkan [DILLÖ13], and the group-access trees of Charalampopoulos, Gupta, Jiamjitrak, Pareek and Yingchareonthawornchai [9] cost O(UB⁡(X)+mlog⁡log⁡n)O(\operatorname{UB}(X) + m \log\log n), with an additional O(nlog⁡n)O(n \log n) in the case of [22]. Derryberry’s thesis [19] proposed the cache-splay tree and claimed that it achieves the unified bound. Demaine, Iacono, Langerman and Özkan reported that this claim was withdrawn [22 footnote 4 of the arXiv version], see also [28 Section 1], and we know of no published account of the gap. Chalermsook, Goswami, Kozma, Mehlhorn and Saranurak [12] proved that OPT⁡(X)\operatorname{OPT}(X) is at most a factor times UB⁡ℓ(X)\operatorname{UB}_{\ell}(X) for a time-windowed bound UB⁡ℓ\operatorname{UB}_{\ell}, in which only the last ℓ\ell searches may serve as uu, with a factor O(ℓ!⋅ℓlog⁡ℓ)O(\ell! \cdot\ell\log\ell), and [9] obtained O(UB⁡ℓ(X)+mlog⁡ℓlog⁡log⁡n)O(\operatorname{UB}_{\ell}(X) + m \log\ell\log\log n) in expectation, with a randomized tree and for sufficiently long sequences.

The known BSTs lose in similar ways. Skip-splay trees cut the keys into about log⁡log⁡n\log\log n levels of nested blocks whose sizes grow doubly exponentially, and a search can pass through all of these levels, paying a constant at each, even when it is adjacent to the previous search. The multi-finger approach of [12] lets a BST simulate kk pointers that move in the tree, called fingers, at a cost of O(1+log⁡k)O(1+\log k) per finger move, and its bound for a window of the last ℓ\ell searches uses up to ℓ!\ell! fingers, so covering every earlier search would require the number of fingers to grow with the sequence. In both cases the overhead comes from serving all scales, or all fingers, uniformly, although a given search needs only one of them.

Our results. We answer the question positively, with a deterministic online BST. An online BST decides how to serve each search knowing only the searches so far.

Theorem 1.1 (Main theorem; see Theorems 4.4 and 7.3). There is a deterministic online BST algorithm that, starting from a fixed tree on the keys 1,…,n1,\ldots,n, serves every sequence XX of mm searches at total cost

O(m+UB⁡(X)),O(m+\operatorname{UB}(X)),

and every single search at cost O(log⁡n)O(\log n).

The bound has no additive term nn: the initial tree is a fixed balanced tree, and the first search is paid for by the term log⁡2(n+2)\log_2(n+2) of the unified bound. If the initial tree is prescribed, the first search can rebuild it at cost nn, which gives O(m+n+UB⁡(X))O(m+n+\operatorname{UB}(X)), the form of the question above. The bound on a single search is optimal up to a constant factor, since every BST on nn keys has a key of depth at least log⁡2(n+1)−1\log_2(n+1)-1. Both bounds also hold for the running time on a word RAM, after an initialization of O(n)O(n) time (Proposition 9.1). Since OPT⁡(X)\operatorname{OPT}(X) is at most the cost of any execution on XX, the offline question is answered as well.

Corollary 1.2. For every sequence XX of mm searches over the keys 1,…,n1,\ldots,n, OPT⁡(X)=O(m+UB⁡(X))\operatorname{OPT}(X)=O(m+\operatorname{UB}(X)).

The difficulty is that a single tree must keep the neighbourhood of every recent search near its root, at every scale at once. Cut the keys into blocks of 2s2^s consecutive keys at every scale ss, and count a block as searched whenever one of its keys is searched. The locality scale of a search is the least scale ss such that the block of scale ss that contains its key was searched before and fewer than about 2s2^s distinct keys were searched since, and in total the unified bound charges the searches about these scales (§ 2.5). Say that a block of scale ss is in use while it is among the 2s2^s blocks of its scale that were searched most recently. At any single moment a tree in which the keys carry weights, and heavier keys are nearer the root, can place the keys of every block of scale ss that is in use within depth O(s)O(s). But blocks keep coming into use and falling out of use, and moving a block of scale ss costs about ss. A search can bring a block into use at every scale below its own, so a tree that tracks every scale pays about the square of what the bound allows (§ 2.2).

The way out is that a tree need not track every scale. Our tree tracks blocks only at the scales 1,2,4,8,…1, 2, 4, 8, \ldots: at such a scale ss, it keeps the 2s2^s blocks of 2s2^s keys that were searched most recently, each with a weight that puts its keys near the root. The scales grow geometrically, so the blocks that a search brings in cost only about the largest of them, and a search with locality scale ss still finds a kept block of scale less than 2s2s around its key, namely at the least power of two that is at least ss (§ 2.3). The sizes 2,4,16,256,…2, 4, 16, 256, \ldots of the blocks at these scales grow doubly exponentially, like those of the levels of skip-splay trees [23], and keeping at each level the blocks that were searched most recently is the rule of the cache-splay tree [19]. What is new is the tree that holds the blocks and the analysis. Every kept block has a weight that depends only on its size: a kept block of scale ss has the weight 4−s4^{-s}, whatever larger blocks contain it. At most 2s2^s blocks of scale ss are kept, so all weights together are O(1)O(1), and a search tree for weighted items can place an item of weight ww at depth O(log⁡(1/w))O(\log(1/w)). So a search reaches a kept block of scale ss at depth O(s)O(s). It does not pass through the levels above the block, as a search in a skip-splay tree does. The tree that holds the weighted blocks is a biased search tree of Bent, Sleator and Tarjan [7], a balanced search tree for weighted items in which heavy items are near the root. In it a block of scale ss is inserted and removed in O(s)O(s) time in the worst case, so no step is amortized over the tree. A search replaces at most one block at each scale, the least recently searched block by its own, and only at scales below its locality scale. So a search with locality scale ss costs O(s)O(s) in the worst case, and the only amortized step of the proof is the comparison of the locality scales with the unified bound.

Pattern-avoiding sequences. A search sequence avoids a permutation σ\sigma of {1,…,k}\{1,\ldots,k\} if no kk of its searches have distinct keys in the relative order given by σ\sigma. It was conjectured that OPT⁡(X)=O(n)\operatorname{OPT}(X)=O(n) for every permutation XX of {1,…,n}\{1,\ldots,n\} that avoids a fixed pattern σ\sigma; Berendsohn, Kozma and Opler [6] attribute the conjecture to [10]. Berendsohn, Kozma and Opler proved it [6 Section 3], with the bound OPT⁡(X)=O(ncσ2)\operatorname{OPT}(X)=O(nc_\sigma^2). Here cσc_\sigma is the Füredi–Hajnal limit of σ\sigma, the least constant such that every 0-1 matrix with M1M_1 rows, M2M_2 columns and more than cσmax⁡(M1,M2)c_\sigma\max(M_1,M_2) ones has kk ones, in kk different rows and kk different columns, that lie relative to one another as the ones of the permutation matrix of σ\sigma; it is finite by the theorem of Marcus and Tardos [33]. They also noted a lower bound of Ω(nlog⁡cσ)\Omega(n\log c_\sigma) for some σ\sigma-avoiding XX, by counting the σ\sigma-avoiding permutations of {1,…,n}\{1,\ldots,n\}, whose number grows like LnL^n for a constant LL that is polynomially related to cσc_\sigma [14, 15], and they called sharpening the dependence on cσc_\sigma a challenging open question. We close the gap.

Theorem 1.3 (see Proposition 8.2). There is a deterministic online BST algorithm on the keys 1,…,n1,\ldots,n that, for every permutation σ\sigma of length at least 2, serves every sequence XX of mm searches over {1,…,n}\{1,\ldots,n\} that avoids σ\sigma at cost

O((m+n)(1+log⁡cσ)).O((m+n)(1+\log c_\sigma)).

The algorithm does not depend on σ\sigma, and the constant in the OO-notation does not depend on σ\sigma.

For a permutation XX, where m=nm=n, this gives OPT⁡(X)=O(n(1+log⁡cσ))\operatorname{OPT}(X)=O(n(1+\log c_\sigma)), which matches the lower bound of [6, 14] for the worst σ\sigma-avoiding permutations. Since cσ=2O(k)c_\sigma=2^{O(k)} for patterns of length kk [24], the bound is also O((m+n)k)O((m+n)k). Berendsohn, Kozma and Opler asked whether bounds of this kind hold for online algorithms such as splay trees or Greedy [6], the algorithm of Lucas and Munro [31, 34] in the online form of [20], which is the other leading candidate for dynamic optimality. Before this work, the best bound for any online BST on all σ\sigma-avoiding permutations was n⋅21+o(1)α(n)n\cdot2^{1+o(1)\alpha(n)} for fixed σ\sigma, where α\alpha is the inverse Ackermann function, for Greedy [18]. Theorem 1.3 follows from the bound in terms of scales (Theorem 4.4) and the

theorem of Marcus and Tardos, applied at every scale ss to the grid of blocks of 2s2^s keys and intervals of 2s2^s consecutive searches (§ 8). The same count gives UB(X)=O((m+n)(1+log⁡cσ))\mathrm{UB}(X)=O((m+n)(1+\log c_\sigma)) for every σ\sigma-avoiding sequence (Proposition 8.2). So the unified bound captures pattern avoidance, which answers, for permutations, the question of [10] whether some parameter subsumes both pattern avoidance and the dynamic-finger bound.

Insertions and deletions. The question above concerns searches in a fixed set of keys, and this is the setting of the earlier BSTs as well; skip-splay trees, for instance, do not support insertions and deletions [4]. The unified bound, however, also makes sense for a set that changes. Bădoiu, Cole, Demaine and Iacono [1] extended it to insertions and deletions, with the distance between two keys counted among the keys that are present. We call this the unified bound with updates. They gave a structure that satisfies it and is not a BST, and they conjectured that splay trees satisfy it for all three operations. We extend our tree to support insertions and deletions (Theorem 10.1): it serves every sequence XX of mm searches, insertions and deletions, starting from a set of n0n_0 keys, at total cost O(n0+m+UB(X))O(n_0+m+\mathrm{UB}(X)), and every single operation at a cost that is logarithmic in the current number of keys. Up to the additive term n0+mn_0+m, the unified bound with updates therefore bounds the cost of the best BST for every sequence of searches, insertions and deletions (Corollary 10.2). The algorithm is the same, except that the blocks of keys are no longer those of a fixed grid. They are split and merged as the set changes, which happens rarely and changes the tree only near its root.

Consequences for dynamic optimality. By Corollary 1.2, the unified bound is a sound bound in the sense of [11]: it bounds the optimum. Consequently, the dynamic optimality conjecture implies the conjecture of Iacono that splay trees satisfy the unified bound, and in the same way, if Greedy is dynamically optimal [20], then it satisfies the unified bound. Iacono noted that his own structure, built from several search trees rather than one, gives no such implication [29], and the same is noted in [1]. The implication also holds with insertions and deletions: if splay trees are dynamically optimal for searches, insertions and deletions, then by Corollary 10.2 they serve every such sequence at total cost O(n0+m+UB(X))O(n_0+m+\mathrm{UB}(X)). For sequences that start from the empty set this is the conjecture of [1], stated for the total cost and up to the convention for keys that were never accessed (§ 10). Corollary 1.2 also transfers to every competitive BST. A BST that is cc-competitive, that is, serves every sequence at cost O(c(OPT⁡(X)+n))O(c(\operatorname{OPT}(X)+n)), therefore costs O(c(m+n+UB(X)))O(c(m+n+\mathrm{UB}(X))); this applies to Tango trees [21] and multi-splay trees [39] with c=O(log⁡log⁡n)c=O(\log\log n), and, by recent preprints, to splay trees with c=O(log⁡log⁡n⋅(log⁡log⁡n)2)c=O(\log\log n\cdot(\log\log n)^2) [13] and to Greedy with c=2O(log⁡log⁡n)c=2^{O(\sqrt{\log\log n})} [27]. Since UB(X)≤UBℓ(X)\mathrm{UB}(X)\leq\mathrm{UB}_\ell(X) for every ℓ\ell, Theorem 1.1 also gives O(m+UBℓ(X))O(m+\mathrm{UB}_\ell(X)) for the time-windowed bound, with no dependence on ℓ\ell. For the cost of a single search, a general transformation [2] turns every BST algorithm into one that performs O(log⁡n)O(\log n) BST operations per search at the same total cost up to a constant factor.

Related work. Our structure can be seen as a multi-finger tree [12] with one finger for each block that it holds, kept in a weighted tree. It differs in which fingers it keeps and how they are weighted: a finger stands for a block of keys around a recent search at one of the scales 1,2,4,…1,2,4,\ldots, and its weight depends only on the size of the block, which is what removes the logarithmic factor (§ 2.4). Storing a tree as a tree of search trees, one for each piece of a decomposition, goes back to the link-cut trees of Sleator and Tarjan [37] and is the basis of multi-splay trees [39], where the pieces are paths of a fixed balanced tree. Our tree has two levels only: a biased search tree [7] whose leaves are the intervals into which the kept blocks cut the keys, and a biased search tree on the keys of each interval. The cache-splay tree of [19], whose rule for keeping blocks we use, stores each of its log⁡log⁡n\log\log n levels in splay trees, and its analysis is amortized, with a potential function and a random shift of the block boundaries. Our analysis is worst-case for each search, and § 7 compares the locality scales with the unified bound by a deterministic charging argument for the fixed grid. We do not know where the analysis of [19] fails; our proof uses no step of it. The lazy-finger bound of Bose, Douïeb, Iacono and Langerman [5] and the weighted dynamic-finger bound of Iacono and Langerman [30] measure the distance between consecutive searches in a static reference tree or with key weights, rather than taking the best earlier witness with a charge for recency. Outside the BST model, Rutschmann [36] recently gave a heap that satisfies the unified bound.

References

  1. [1]Mihai Bădoiu, Richard Cole, Erik D. Demaine, and John Iacono. A unified access bound on comparison-based dynamic dictionaries. Theoretical Computer Science, 382(2):86–96, 2007.
  2. [2]Prosenjit Bose, Sébastien Collette, Rolf Fagerberg, and Stefan Langerman. De-amortizing binary search trees. In Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP), volume 7391 of Lecture Notes in Computer Science, pages 121–132, 2012.
  3. [3]Mihai Bădoiu and Erik D. Demaine. A simplified and dynamic unified structure. In Proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN), volume 2976 of Lecture Notes in Computer Science, pages 466–473, 2004.
  4. [4]Prosenjit Bose, Karim Douïeb, Vida Dujmović, and John Howat. Layered working-set trees. Algorithmica, 63(1):476–489, 2012.
  5. [5]Prosenjit Bose, Karim Douieb, John Iacono, and Stefan Langerman. The power and limitations of static binary search trees with lazy finger. In Algorithms and Computation (ISAAC 2014), volume 8889 of Lecture Notes in Computer Science, pages 181–192. Springer, 2014.
  6. [6]Benjamin Aram Berendsohn, László Kozma, and Michal Opler. Optimization with pattern-avoiding input. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), 2024.arxiv.org/abs/2310.04236
  7. [7]Samuel W. Bent, Daniel Dominic Sleator, and Robert Endre Tarjan. Biased search trees. SIAM Journal on Computing, 14(3):545–568, 1985.DOI
  8. [8]Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Nidia Obscura Acosta, Akash Pareek, and Sorrachai Yingchareonthawornchai. Improved pattern-avoidance bounds for greedy BSTs via matrix decomposition. In Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 509–534, 2023.
  9. [9]Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Akash Pareek, and Sorrachai Yingchareonthawornchai. The group access bounds for binary search trees. In Proceedings of the 51st International Colloquium on Automata, Languages, and Programming (ICALP), volume 297 of LIPIcs, pages 38:1–38:18, 2024.
  10. [10]Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. Pattern-avoiding access in binary search trees. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 410–423, 2015.
  11. [11]Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. The landscape of bounds for binary search trees. arXiv:1603.04892, 2016.
  12. [12]Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. Multi-finger binary search trees. In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC), volume 123 of LIPIcs, pages 55:1–55:26, 2018.arxiv.org/abs/1809.01759
  13. [13]Petr Chmel, Bernhard Haeupler, Richard Hladík, Michal Koucký, Antti Roeyskoe, Václav Rozhoň, Ondřej Sladký, and Robert E. Tarjan. Splay trees are almost dynamically optimal. arXiv:2607.18498, 2026.arxiv.org/abs/2607.18498
  14. [14]Josef Cibulka. On constants in the Füredi–Hajnal and the Stanley–Wilf conjecture. Journal of Combinatorial Theory, Series A, 116(2):290–302, 2009.DOI
  15. [15]Josef Cibulka and Jan Kynčl. Better upper bounds on the Füredi–Hajnal limits of permutations. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2280–2293, 2017.
  16. [16]Richard Cole, Bud Mishra, Jeanette Schmidt, and Alan Siegel. On the dynamic finger conjecture for splay trees. Part I: Splay sorting log n-block sequences. SIAM Journal on Computing, 30(1):1–43, 2000.
  17. [17]Richard Cole. On the dynamic finger conjecture for splay trees. Part II: The proof. SIAM Journal on Computing, 30(1):44–85, 2000.DOI
  18. [18]Parinya Chalermsook, Seth Pettie, and Sorrachai Yingchareonthawornchai. Sorting pattern-avoiding permutations via 0-1 matrices forbidding product patterns. In Proceedings of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 133–149, 2024.arxiv.org/abs/2307.02294
  19. [19]Jonathan C. Derryberry. Adaptive Binary Search Trees. PhD thesis, Carnegie Mellon University, 2009. Technical report CMU-CS-09-180.
  20. [20]Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane, and Mihai Pătraşcu. The geometry of binary search trees. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 496–505, 2009.
  21. [21]Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Pătraşcu. Dynamic optimality—almost. SIAM Journal on Computing, 37(1):240–251, 2007.
  22. [22]Erik D. Demaine, John Iacono, Stefan Langerman, and Özgür Özkan. Combining binary search trees. In Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP), volume 7965 of Lecture Notes in Computer Science, pages 388–399, 2013.
  23. [23]Jonathan C. Derryberry and Daniel Dominic Sleator. Skip-splay: Toward achieving the unified bound in the BST model. In Proceedings of the 11th International Symposium on Algorithms and Data Structures (WADS), volume 5664 of Lecture Notes in Computer Science, pages 194–205, 2009.DOI
  24. [24]Jacob Fox. Stanley–Wilf limits are typically exponential. arXiv:1310.8378, 2013.arxiv.org/abs/1310.8378
  25. [25]Navin Goyal and Manoj Gupta. Better analysis of Greedy binary search tree on decomposable sequences. Theoretical Computer Science, 776:19–42, 2019.
  26. [26]Sylvain Guillemot and Dáńiel Marx. Finding small patterns in permutations in linear time. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 82–101, 2014.
  27. [27]Yuhao Guo, Seth Pettie, Daniel Skora, and Chengzhang Wan. The greedy binary search tree is non-trivially competitive. arXiv:2608.04410, 2026.arxiv.org/abs/2608.04410
  28. [28]John Howat, John Iacono, and Pat Morin. The fresh-finger property. arXiv:1302.6914, 2013.arxiv.org/abs/1302.6914
  29. [29]John Iacono. Alternatives to splay trees with O(log n) worst-case access times. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 516–522, 2001.DOI
  30. [30]John Iacono and Stefan Langerman. Weighted dynamic finger in binary search trees. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 672–691, 2016.
  31. [31]Joan M. Lucas. Canonical forms for competitive binary search tree algorithms. Technical Report DCS-TR-250, Rutgers University, 1988.
  32. [32]Kurt Mehlhorn. Nearly optimal binary search trees. Acta Informatica, 5:287–295, 1975.DOI
  33. [33]Adam Marcus and Gábor Tardos. Excluded permutation matrices and the Stanley–Wilf conjecture. Journal of Combinatorial Theory, Series A, 107(1):153–160, 2004.
  34. [34]J. Ian Munro. On the competitiveness of linear search. In Proceedings of the 8th Annual European Symposium on Algorithms (ESA), volume 1879 of Lecture Notes in Computer Science, pages 338–345, 2000.DOI
  35. [35]Michal Opler. An optimal algorithm for sorting pattern-avoiding sequences. In Proceedings of the 65th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 689–699, 2024.arxiv.org/abs/2409.07868
  36. [36]Daniel Rutschmann. Sorting under partial information with optimal preprocessing time via unified bound heaps. arXiv:2604.12653, 2026. To appear at FOCS 2026.arxiv.org/abs/2604.12653
  37. [37]Daniel D. Sleator and Robert E. Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3):362–391, 1983.
  38. [38]Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. Journal of the ACM, 32(3):652–686, 1985.DOI
  39. [39]Chengwen Chris Wang, Jonathan Derryberry, and Daniel Dominic Sleator. O(log log n)-competitive dynamic binary search trees. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 374–383, 2006.
  40. [40]Robert Wilber. Lower bounds for accessing binary search trees with rotations. SIAM Journal on Computing, 18(1):56–67, 1989.

Paper details

vlnc:W_6nfxyspn
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude Opus 5.5, Claude Fable 5.1 (bare), Claude Fable 5.2, GPT-6 Astra, GPT-5.6 Sol (bare)

View statement
Looking for related papers…
Contents