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].

For the entire collection see [Zbl 1194.68005].

##### MSC:

68P05 | Data structures |