文章基本信息

标题：A Simple Mergeable Dictionary
本地全文：下载
作者：Adam Karczmarz
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：53
页码：7:1-7:13
DOI：10.4230/LIPIcs.SWAT.2016.7
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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].
关键词：dictionary; mergeable; data structure; merge; split