Mergeable Dictionaries

Authors John Iacono, Özgür Özkan



PDF
Thumbnail PDF

File

DagSemProc.10091.2.pdf
  • Filesize: 0.63 MB
  • 34 pages

Document Identifiers

Author Details

John Iacono
Özgür Özkan

Cite AsGet BibTex

John Iacono and Özgür Özkan. Mergeable Dictionaries. In Data Structures. Dagstuhl Seminar Proceedings, Volume 10091, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
https://doi.org/10.4230/DagSemProc.10091.2

Abstract

A data structure is presented for the Mergeable Dictionary abstract data type, which supports the following operations on a collection of disjoint sets of totally ordered data: Predecessor-Search, Split and Union. While Predecessor-Search and Split work in the normal way, the novel operation is Union. While in a typical mergeable dictionary (e.g. 2-4 Trees), the Union operation can only be performed on sets that span disjoint intervals in keyspace, the structure here has no such limitation, and permits the merging of arbitrarily interleaved sets. Our data structure supports all operations, including Union, in O(log n) amortized time, thus showing that interleaved Union operations can be supported at no additional cost vis-a-vis disjoint Union operations.
Keywords
  • Data structures
  • amortized analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail