Combining binary search trees

DOI10.1007/978-3-642-39206-1_33MaRDI QIDQ5326577zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1304.7604

Mathematics Subject Classification ID

Data structures (68P05)

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 $f(n)$ 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.

Recommendations

• De-amortizing binary search trees
• An \(O(\log \log n)\)-competitive binary search tree with optimal worst-case access times
• The geometry of binary search trees
• Weighted dynamic finger in binary search trees
• Dynamic Optimality—Almost

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
• Improving time and space efficiency in generalized binary search trees
• De-amortizing binary search trees
• Multi-Finger 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)