zbMATH — the first resource for mathematics

Mergeable dictionaries. (English) Zbl 1287.68030
Abramsky, Samson (ed.) et al., Automata, languages and programming. 37th international colloquium, ICALP 2010, Bordeaux, France, July 6–10, 2010. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-14164-5/pbk). Lecture Notes in Computer Science 6198, 164-175 (2010).
Summary: A data structure is presented for the mergeable dictionary abstract data type, which supports the operations predecessor-search, split, and merge on a collection of disjoint sets of totally ordered data. While in a typical mergeable dictionary (e.g. 2-4 trees), the merge operation can only be performed on sets that span disjoint intervals in keyspace, the structure here has no such limitation. A data structure which can handle arbitrary merge operations in \(O(\log n)\) amortized time in the absence of split operations was presented by M. R. Brown and R. E. Tarjan [J. Assoc. Comput. Mach. 26, 211–226 (1979; Zbl 0395.68055)]. A data structure which can handle both split and merge operations in \({\mathcal O}({\log^2}n)\) amortized time was presented by M. Farach and M. Thorup [Algorithmica 20, No. 4, 388–404 (1998; Zbl 0899.68046)]. In contrast, our data structure supports all operations, including split and merge, in \({\mathcal O}({\log}n)\) amortized time, thus showing that interleaved merge operations can be supported at no additional cost vis-à-vis disjoint merge operations.
For the entire collection see [Zbl 1194.68005].

68P05 Data structures
PDF BibTeX Cite
Full Text: DOI