4
$\begingroup$

I am looking for a data structure $D$ which supports the following operations (preferably a (binary) tree-like structure):

  • $D$ is indexed, i.e. there is a mapping from $\{1, \ldots, n\}$ to items in $D$, where $n$ is the size of $D$ (the number of items in $D$).

  • $k$-th item in $D$ can be accessed in $\mathcal{O}(\lg n)$ worst-case (non-amortized).
    The operation should not modify the data structure, it should be completely "read-only" (e.g. no finger searches are allowed). (Once the pointer to the $k$-th item is obtained, further changes should be supported in $O(1)$ without modification to the state of the data structure apart from the actual stored item (e.g. if it is a tree-like data structure, this means no rotation is allowed).

  • two instanced $D$ and $D'$ can be merged in time $\mathcal{O}(1)$ worst-case (non-amortized). Destruction of $D$ and $D'$ is fine.
    The result should contains the union of the elements; those that come $D$ retain their indices, while indices of those coming from $D'$ get incremented by the size of $D$, e.g. if we are merging $D=\{ 1 \to x_1, 2 \to x_2 \}$ with $D'=\{ 1 \to y_1, 2 \to y_2, 3 \to y_3 \}$ we should get $\{ 1 \to x_1, 2 \to x_2, 3 \to y_1, 4 \to y_2, 5 \to y_3 \}$.

In essence, this data structure should have the properties of the fast-mergeable array/vector with asymptotically slower random-access, but extremely fast merge/concatenation ($\mathcal{O}(1)$). It would also be cool if elements could be listed in order in linear time.

I would be mostly interested in the references to existing work / papers which describe such a data structure or algorithm on an existing data structure.

Improve this question
$\endgroup$
2
  • $\begingroup$ By sorted, I mean not by element values but by their index, which is let's say the order in which they were appended to the initially empty list-like data structure. $\endgroup$
    – eold
    Commented Jan 23, 2015 at 5:02
  • $\begingroup$ Then you can just keep a separate list of items. Btw, I think the correct term for what you want is "indexed" not "sorted" or "ordered". $\endgroup$
    – Kaveh
    Commented Jan 23, 2015 at 5:23

1 Answer 1

Reset to default
4
$\begingroup$

I think Purely Functional Worst Case Constant Time Catenable Sorted Lists by Brodal et al. supplies what you want.

Improve this answer
$\endgroup$
5
  • $\begingroup$ This feels strange, why merge is $O(1)$ but insert is $O(\lg n)$? Surely you can create a single item instance and merge, right? $\endgroup$
    – Kaveh
    Commented Jan 23, 2015 at 4:55
  • 2
    $\begingroup$ @Kaveh, this data structure doesn't support $O(1)$ merge of interleaved keys, like the merge in the merge step of a mergesort. It supports constant-time concat (aka join), in which all of the slots in one structure end up following all of the slots of the other. This matches, IIUC, what the OP is asking about. $\endgroup$
    – jbapple
    Commented Jan 23, 2015 at 5:00
  • $\begingroup$ It seems you are right. $\endgroup$
    – Kaveh
    Commented Jan 23, 2015 at 5:06
  • $\begingroup$ @jbabble: Thanks for the reference. However, it seems that my merge operation is different from their join/catenate operation in a sense that after a merge(D1, D2) operation, elements of D2 change their indices. So, if I was to use that data structure naively, I would need to change the keys by reinserting all the elements of D2. Do you see any way how I can keep the elements "ordered" but not "indexed"? $\endgroup$
    – eold
    Commented Jan 23, 2015 at 5:40
  • 1
    $\begingroup$ @leden: To use these trees, I think you don't actually need to store the indices at the elements. Instead, store at each internal node the number of descendant leaves. Starting from the root, to get to index $i$, if the left child has $j < i$ descendants, look fo index $i-j$ in the right subtree. Otherwise, look for index $i$ in the left subtree. This may not work exactly as written, but this reference is the closest thing I know of to what you request, so I think a modification of my suggestion may be the closest the literature has to an answer to your question. $\endgroup$
    – jbapple
    Commented Jan 23, 2015 at 15:22

Your Answer

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

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