Mergeable dictionaries

John Iacono, Özgür ̈ Özkan

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


    A data structure is presented for the Mergeable Dictionary abstract data type, which supports the operations Predecessor-Search, Split, and Merge on a collection of disjoint sets of totally ordered data. While in a typical mergeable dictionary (e.g. 2-4 Trees), the Merge operation can only be performed on sets that span disjoint intervals in keyspace, the structure here has no such limitation. A data structure which can handle arbitrary Merge operations in O(log n) amortized time in the absence of Split operations was presented by Brown and Tarjan [2]. A data structure which can handle both Split and Merge operations in amortized time was presented by Farach and Thorup [4]. In contrast, our data structure supports all operations, including Split and Merge, in amortized time, thus showing that interleaved Merge operations can be supported at no additional cost vis-à-vis disjoint Merge operations.

    Original languageEnglish (US)
    Title of host publicationAutomata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings
    Number of pages12
    EditionPART 1
    StatePublished - 2010
    Event37th International Colloquium on Automata, Languages and Programming, ICALP 2010 - Bordeaux, France
    Duration: Jul 6 2010Jul 10 2010

    Publication series

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


    Other37th International Colloquium on Automata, Languages and Programming, ICALP 2010


    • amortized analysis
    • data structures

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'Mergeable dictionaries'. Together they form a unique fingerprint.

    Cite this