7
$\begingroup$

A dynamic predecessor data structure supporting findPredecessor, insert, and delete over unique ordered keys in an unbounded universe in $O(\lg n)$ worst-case time can be stored contiguously using only $O(1)$ extra words of storage in addition to the storage for the keys themselves:

"Optimal Worst-Case Operations for Implicit Cache-Oblivious Search Trees", Franceschini and Grossi

The structure is complex (IMHO).

Storing $n$ keys in an array that can grow dynamically requires at space for at least $\Theta(\sqrt{n})$ additional keys:

"Resizable Arrays in Optimal Time and Space", Brodnik et al.

Given the latter constraint, is there a simpler dynamic predecessor data structure that uses contiguous space for $n + O(\sqrt{n})$ keys?

There were many implicit ($O(1)$ extra words) dynamic predecessor data structures that predate the result of Franceschini and Grossi:

"Implicit Data Structures for the Dictionary Problem", Frederickson

"Searchability in merging and implicit data structures", Munro and Poblete (does not support delete)

"Developing Implicit Data Structures", Munro

I'm wondering if it is possible to simplify even these structures by using $\Theta(\sqrt{n})$ extra space. I am hoping to find a structure supporting all three operations in $o(n^\varepsilon)$ time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.