**Reference**:- 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. **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*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. **Comments**:- This paper is available as arXiv.org:1304.7604 of the Computing Research Repository (CoRR).
**Length**:- The paper is 12 pages.
**Availability**:- The paper is available in PDF (329k).
- See information on file formats.
- [Google Scholar search]

See also other papers by Erik Demaine.

Last updated January 13, 2020 by Erik Demaine.