Paper by Erik D. Demaine

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]