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.)

Improve this question
$\endgroup$
8
  • $\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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 10:23

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\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, 2015 at 1:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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