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
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2685/
|
Go to the corresponding Portal |
Iacono, John ;
Özkan, Özgür
Mergeable Dictionaries
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.
BibTeX - Entry
@InProceedings{iacono_et_al:DagSemProc.10091.2,
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 = {https://drops.dagstuhl.de/opus/volltexte/2010/2685},
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 |
