Recursively rotated orders and implicit data structures: A lower bound
Let n values be stored in the first n locations of an array. Suppose that a dictionary is maintained on these values, so that the operations of insert, delete, and search are supported. Since no additional space is allowed, no explicit pointers can be used. Thus any information about the relationship of values must be encoded in their arrangement. Such a structure is called an implicit data structure. The paper addresses a relaxation of a sorted order, called a recursively rotated order. If the values are stored in a fashion consistent with such an order, search times of \(O(\log n)\) can be achieved. The main result of the paper is that the number of data swaps for an exchange (an insertion of one element combined with a deletion of another element) for any such order is in the worst case \(\Omega(2^{\sqrt{2 \log n}}(\log n)^{1/2}).\) This matches to within a constant factor an upper bound on the number of data swaps.
- scientific article; zbMATH DE number 2079398
- Implicit \(B\)-trees: A new data structure for the dictionary problem
- An implicit data structure supporting insertion, deletion, and search in O( ^ 2\,n) time
- Optimal implicit dictionaries over unbounded universes
- Optimal worst-case operations for implicit cache-oblivious search trees.
This page was built for publication: Recursively rotated orders and implicit data structures: A lower bound
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q792764)
