Paper by Erik D. Demaine
- 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 2013), Riga, Latvia, July 8–12, 2013, pages 388–399.
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 O(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 O(log log 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
O(log log n) factor, and performs each access in
worst-case O(log n) time.
- This paper is available as arXiv.org:1304.7604 of the Computing Research Repository (CoRR).
- The paper is 12 pages.
- The paper is available in PDF (329k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated September 20, 2023 by