<p>I believe you are looking for the paper <a href="http://dx.doi.org/10.1007/978-3-540-45078-8_11" rel="nofollow">Optimal Worst-Case Operations for Implicit Cache-Oblivious Search Trees</a> by Franceschini and Grossi.</p>

CC BY-SA 3.0
2015-03-31T01:07:37.540Z
I understand this is a result of the "conversation" in comments and a possibly deleted other answer, but this is currently a "link-only answer". Please provide a little context.
Mark Hurd
CC BY-SA 3.0
2015-03-24T16:32:10.100Z
2015-03-24T16:32:10.100Z
Kristoffer Arnsfelt Hansen
<p>Is there a data structure that supports searching, inserting, deletion in worst-case O(log n) time and that satisfies the following "array implementation" property: at any point in time, the data structure only occupies memory cells 1..n (or 1..O(n)) if there are n elements?</p>

<p>Note that e.g. heaps do satisfy the property.</p>

<p>In particular, do standard data structures such as red-black, AVL, etc. allow for such an implementation?  (And if so, why is this not discussed in standard textbooks?)</p>

<p>(This is vaguely related to a <a href="https://cstheory.stackexchange.com/questions/30791/data-structure-for-dynamic-memory-allocation">previous question</a> which got no answer.)</p>

CC BY-SA 3.0
2015-03-24T15:41:06.047Z
Keeping a complete binary tree in palace of just the nodes with data in a balanced bst will use only twice as much memory so the answer is yes. I think CLRS separates the part about storing trees from the rest and discusses an array implementation for trees. After you discuss that you don't need to go back to the issue of how to store trees again.
Kaveh
CC BY-SA 3.0
2015-03-24T15:50:55.040Z
The problem with continuous memory usage is delete, but it is possible if you keep the address for the parents. In delete remove the node, move the last node there, and update the information in the parent.
Kaveh
CC BY-SA 3.0
2015-03-24T15:54:22.107Z
Thanks @Kaveh.  Can you give details/pointer of what happens after I delete a node, including rebalancing.  For which data structures are you claiming this is possible? AVL, red-black, ...?  What is the simplest data structure that allows for this?
Manu
CC BY-SA 3.0
2015-03-24T18:08:53.677Z
I think it works for any tree-based data structure (AVL, RB, ...). If you want to use a continuous block of memory, store the nodes of the tree in an array. Each node contains the location of children + parent + data. When we delete a node we swap it with the last item in the array and update the child pointer of its parent to point to its new location. Rebalancing does not effect where you store the nodes in the array, it only changes the pointers inside the nodes.
Kaveh
CC BY-SA 3.0
2015-03-24T19:54:39.983Z
How is your solution compatible with Kristoffer's answer?  It seems this was a non-trivial problem to solve.
Manu
CC BY-SA 3.0
2015-03-24T22:15:46.083Z
I think what was non-trivial was to go from O(n) cells to n + O(1) cells.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2015-03-25T10:23:01.237Z
OK thanks for the discussion.  I'll accept Kristoffer's answer since it gives the stronger result.
Manu
CC BY-SA 3.0
2015-03-26T03:46:06.057Z
I haven't looked at the paper. The solution I mentioned also uses n "cells" if the cells also contain pointers to children and patents. They probably do it with const overhead over the memory needed to store the actual data which is nice and surprising.
Kaveh
<ds.data-structures>
Array implementation of dictionary data structure
Manu
# Array implementation of dictionary data structure

(Asked by: username_0 on 2015-03-24)

Is there a data structure that supports searching, inserting, deletion in worst-case O(log n) time and that satisfies the following "array implementation" property: at any point in time, the data structure only occupies memory cells 1..n (or 1..O(n)) if there are n elements?

Note that e.g. heaps do satisfy the property.

In particular, do standard data structures such as red-black, AVL, etc. allow for such an implementation? (And if so, why is this not discussed in standard textbooks?)

(This is vaguely related to a [previous question](https://cstheory.stackexchange.com/questions/30791/data-structure-for-dynamic-memory-allocation) which got no answer.)

**Tags:** ds.data-structures

> **Comments:**
> **username_1**: Keeping a complete binary tree in palace of just the nodes with data in a balanced bst will use only twice as much memory so the answer is yes. I think CLRS separates the part about storing trees from the rest and discusses an array implementation for trees. After you discuss that you don't need to go back to the issue of how to store trees again.  
> **username_1**: The problem with continuous memory usage is delete, but it is possible if you keep the address for the parents. In delete remove the node, move the last node there, and update the information in the parent.  
> **username_0**: Thanks @username_1.  Can you give details/pointer of what happens after I delete a node, including rebalancing.  For which data structures are you claiming this is possible? AVL, red-black, ...?  What is the simplest data structure that allows for this?  
> **username_1**: I think it works for any tree-based data structure (AVL, RB, ...). If you want to use a continuous block of memory, store the nodes of the tree in an array. Each node contains the location of children + parent + data. When we delete a node we swap it with the last item in the array and update the child pointer of its parent to point to its new location. Rebalancing does not effect where you store the nodes in the array, it only changes the pointers inside the nodes.  
> **username_0**: How is your solution compatible with Kristoffer's answer?  It seems this was a non-trivial problem to solve.  
> **username_2**: I think what was non-trivial was to go from O(n) cells to n + O(1) cells.  
> **username_0**: OK thanks for the discussion.  I'll accept Kristoffer's answer since it gives the stronger result.  
> **username_1**: I haven't looked at the paper. The solution I mentioned also uses n "cells" if the cells also contain pointers to children and patents. They probably do it with const overhead over the memory needed to store the actual data which is nice and surprising.  

---

## 1 answers

### Answer by username_2 on 2015-03-24. Score: 4 | Accepted answer

I believe you are looking for the paper [Optimal Worst-Case Operations for Implicit Cache-Oblivious Search Trees](http://dx.doi.org/10.1007/978-3-540-45078-8_11) by Franceschini and Grossi.

> **Comments:**
> **username_3**: I understand this is a result of the "conversation" in comments and a possibly deleted other answer, but this is currently a "link-only answer". Please provide a little context.  

---

