6
$\begingroup$

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 which got no answer.)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Kaveh Mar 24 '15 at 15:41
  • 1
    $\begingroup$ 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? $\endgroup$ – Manu Mar 24 '15 at 15:54
  • 1
    $\begingroup$ 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. $\endgroup$ – Kaveh Mar 24 '15 at 18:08
  • 1
    $\begingroup$ I think what was non-trivial was to go from O(n) cells to n + O(1) cells. $\endgroup$ – Kristoffer Arnsfelt Hansen Mar 24 '15 at 22:15
  • 1
    $\begingroup$ OK thanks for the discussion. I'll accept Kristoffer's answer since it gives the stronger result. $\endgroup$ – Manu Mar 25 '15 at 10:23
4
$\begingroup$

I believe you are looking for the paper Optimal Worst-Case Operations for Implicit Cache-Oblivious Search Trees by Franceschini and Grossi.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mark Hurd Mar 31 '15 at 1:07

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.