Back to Search
Start Over
Mergeable Dictionaries.
- Source :
- Automata, Languages & Programming (9783642141645); 2010, p164-175, 12p
- Publication Year :
- 2010
-
Abstract
- 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 Brown and Tarjan [2]. A data structure which can handle both Split and Merge operations in ]> amortized time was presented by Farach and Thorup [4]. In contrast, our data structure supports all operations, including Split and Merge, in ]> amortized time, thus showing that interleaved Merge operations can be supported at no additional cost vis-à-vis disjoint Merge operations. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783642141645
- Database :
- Complementary Index
- Journal :
- Automata, Languages & Programming (9783642141645)
- Publication Type :
- Book
- Accession number :
- 76754634
- Full Text :
- https://doi.org/10.1007/978-3-642-14165-2_15