Combining binary search trees

Erik D. Demaine, John Iacono, Stefan Langerman, Özgür Özkan

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    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.

    Original languageEnglish (US)
    Title of host publicationAutomata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings
    Number of pages12
    EditionPART 1
    StatePublished - 2013
    Event40th International Colloquium on Automata, Languages, and Programming, ICALP 2013 - Riga, Latvia
    Duration: Jul 8 2013Jul 12 2013

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    NumberPART 1
    Volume7965 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Other40th International Colloquium on Automata, Languages, and Programming, ICALP 2013

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'Combining binary search trees'. Together they form a unique fingerprint.

    Cite this