Combining binary search trees
From MaRDI portal
Publication:5326577
DOI10.1007/978-3-642-39206-1_33zbMATH Open1336.68046arXiv1304.7604OpenAlexW1553603221MaRDI QIDQ5326577FDOQ5326577
Authors: Erik D. Demaine, John Iacono, Stefan Langerman, Özgür Özkan 
Publication date: 6 August 2013
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
Abstract: We present a general transformation for combining a constant number of binary search tree data structures (BSTs) into a single BST whose running time is within a constant factor of the minimum of any "well-behaved" bound on the running time of the given BSTs, for any online access sequence. (A BST has a well behaved bound with overhead if it spends at most �igoh{f(n)} time per access and its bound satisfies a weak sense of closure under subsequences.) In particular, we obtain a BST data structure that is �igoh{loglog n} competitive, satisfies the working set bound (and thus satisfies the static finger bound and the static optimality bound), satisfies the dynamic finger bound, satisfies the unified bound with an additive �igoh{loglog n} factor, and performs each access in worst-case �igoh{log n} time.
Full work available at URL: https://arxiv.org/abs/1304.7604
Recommendations
Cited In (11)
- In pursuit of the dynamic optimality conjecture
- An \(O(\log \log n)\)-competitive binary search tree with optimal worst-case access times
- De-amortizing binary search trees
- Multi-Finger Binary Search Trees
- Improving time and space efficiency in generalized binary search trees
- Belga B-trees
- Layered working-set trees
- Data structures for mergeable trees
- Weighted dynamic finger in binary search trees
- A study on splay trees
- Layered working-set trees
This page was built for publication: Combining binary search trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5326577)
