Mergeable dictionaries

John Iacono, Özgür ̈ Özkan

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

    Abstract

    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
    Pages164-175
    Number of pages12
    EditionPART 1
    DOIs
    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

    Other

    Other37th International Colloquium on Automata, Languages and Programming, ICALP 2010
    CountryFrance
    CityBordeaux
    Period7/6/107/10/10

    Keywords

    • amortized analysis
    • data structures

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

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

  • Cite this

    Iacono, J., & Özkan, Ö. . (2010). Mergeable dictionaries. In Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings (PART 1 ed., pp. 164-175). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6198 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-14165-2_15