License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.10091.2
URN: urn:nbn:de:0030-drops-26854
Go to the corresponding Portal

Iacono, John ; Özkan, Özgür

Mergeable Dictionaries

10091.IaconoJohn.Paper.2685.pdf (0.6 MB)


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.

BibTeX - Entry

  author =	{Iacono, John and \"{O}zkan, \"{O}zg\"{u}r},
  title =	{{Mergeable Dictionaries}},
  booktitle =	{Data Structures},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10091},
  editor =	{Lars Arge and Erik D. Demaine and Raimund Seidel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-26854},
  doi =		{10.4230/DagSemProc.10091.2},
  annote =	{Keywords: Data structures, amortized analysis}

Keywords: Data structures, amortized analysis
Collection: 10091 - Data Structures
Issue Date: 2010
Date of publication: 26.07.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI