A mergeable dictionary is a data structure storing a dynamic subset S of a totally ordered set U and supporting predecessor searches in S. Apart from insertions and deletions to S, we can both merge two arbitrarily interleaved dictionaries and split a given dictionary around some pivot x. We present an implementation of a mergeable dictionary matching the optimal amortized logarithmic bounds of Iacono and Ökzan [Iacono/Ökzan,ICALP'10]. However, our solution is significantly simpler. The proposed data structure can also be generalized to the case when the universe U is dynamic or infinite, thus addressing one issue of [Iacono/Ökzan,ICALP'10].
@InProceedings{karczmarz:LIPIcs.SWAT.2016.7, author = {Karczmarz, Adam}, title = {{A Simple Mergeable Dictionary}}, booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)}, pages = {7:1--7:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-011-8}, ISSN = {1868-8969}, year = {2016}, volume = {53}, editor = {Pagh, Rasmus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.7}, URN = {urn:nbn:de:0030-drops-60285}, doi = {10.4230/LIPIcs.SWAT.2016.7}, annote = {Keywords: dictionary, mergeable, data structure, merge, split} }
Feedback for Dagstuhl Publishing