<p><a href="https://github.com/patmorin/tds/blob/master/spacesaving.tex" rel="nofollow">Pat Morin demonstrates a structure with $O(\sqrt{n})$ extra words of space and $O(\log^2 n)$ insert, delete, and predecessor search in his notes for his advanced data structures class.</a></p>

CC BY-SA 3.0
2014-10-26T15:57:55.377Z
2014-10-26T15:57:55.377Z
jbapple
<p>A dynamic predecessor data structure supporting <code>findPredecessor</code>, <code>insert</code>, and <code>delete</code> 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:</p>

<p><a href="http://www.di.unipi.it/~grossi/PAPERS/wads03final.ps.gz">"Optimal Worst-Case Operations for Implicit Cache-Oblivious Search Trees", Franceschini and Grossi</a></p>

<p>The structure is complex (IMHO).</p>

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

<p><a href="http://erikdemaine.org/papers/ResizableArrays_WADS99/">"Resizable Arrays in Optimal Time and Space", Brodnik et al.</a></p>

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

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

<p><a href="http://dl.acm.org/citation.cfm?id=322364">"Implicit Data Structures for the Dictionary Problem", Frederickson</a></p>

<p><a href="http://dx.doi.org/10.1007/BF01933727">"Searchability in merging and implicit data structures", Munro and Poblete</a> (does not support <code>delete</code>)</p>

<p><a href="http://dx.doi.org/10.1007/BFb0016241">"Developing Implicit Data Structures", Munro</a></p>

<p>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.</p>

<ds.data-structures><succinct>
Simple succinct dynamic predecessor with $O(\sqrt{n})$ redundancy in contiguous space
jbapple
# Simple succinct dynamic predecessor with $O(\sqrt{n})$ redundancy in contiguous space

(Asked by: username_0 on 2012-05-27)

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](http://www.di.unipi.it/~grossi/PAPERS/wads03final.ps.gz)

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.](http://erikdemaine.org/papers/ResizableArrays_WADS99/)

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](http://dl.acm.org/citation.cfm?id=322364)

["Searchability in merging and implicit data structures", Munro and Poblete](http://dx.doi.org/10.1007/BF01933727) (does not support `delete`)

["Developing Implicit Data Structures", Munro](http://dx.doi.org/10.1007/BFb0016241)

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.

**Tags:** ds.data-structures, succinct

---

## 1 answers

### Answer by username_0 on 2014-10-26. Score: 1 | Accepted answer

[Pat Morin demonstrates a structure with $O(\sqrt{n})$ extra words of space and $O(\log^2 n)$ insert, delete, and predecessor search in his notes for his advanced data structures class.](https://github.com/patmorin/tds/blob/master/spacesaving.tex)


---

