<p>I think <a href="http://www.cs.au.dk/~gerth//pub/esa06trees.html" rel="nofollow">Purely Functional Worst Case Constant Time Catenable Sorted Lists</a> by Brodal et al. supplies what you want.</p>

CC BY-SA 3.0
2015-01-23T04:55:27.027Z
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?
Kaveh
CC BY-SA 3.0
2015-01-23T05:00:51.627Z
@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.
jbapple
CC BY-SA 3.0
2015-01-23T05:06:05.210Z
It seems you are right.
Kaveh
CC BY-SA 3.0
2015-01-23T05:40:56.537Z
@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"?
eold
CC BY-SA 3.0
2015-01-23T15:22:22.567Z
@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.
jbapple
CC BY-SA 3.0
2015-01-23T04:42:55.480Z
2015-01-23T04:42:55.480Z
jbapple
<p>I am looking for a data structure $D$ which supports the following operations 
(preferably a (binary) tree-like structure): </p>

<ul>
<li><p><strong>$D$ is indexed</strong>, 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$).</p></li>
<li><p><strong>$k$-th item in $D$ can be accessed in $\mathcal{O}(\lg n)$ worst-case (non-amortized)</strong>.<br>
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).</p></li>
<li><p><strong>two instanced $D$ and $D'$ can be merged in time $\mathcal{O}(1)$ worst-case (non-amortized)</strong>. Destruction of $D$ and $D'$ is fine.<br>
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 \}$.</p></li>
</ul>

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

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

CC BY-SA 3.0
2015-01-23T05:02:16.237Z
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.
eold
CC BY-SA 3.0
2015-01-23T05:23:23.250Z
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".
Kaveh
<reference-request><ds.data-structures>
Array-like data structure with O(1) worst-case concatenate/join?
eold
# Array-like data structure with O(1) worst-case concatenate/join?

(Asked by: username_0 on 2015-01-23)

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.

**Tags:** reference-request, ds.data-structures
> **Comments:**
> **username_0**: 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.  
> **username_1**: 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".  

---

## 1 answers

### Answer by username_2 on 2015-01-23. Score: 4

I think [Purely Functional Worst Case Constant Time Catenable Sorted Lists](http://www.cs.au.dk/~gerth//pub/esa06trees.html) by Brodal et al. supplies what you want.

> **Comments:**
> **username_1**: 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?  
> **username_2**: @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.  
> **username_1**: It seems you are right.  
> **username_0**: @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"?  
> **username_2**: @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.  

---

