<p>You can trivially make a data structure with O(1) <em>amortized</em> concatenation time, by just reinserting everything from one tree on the other on concatenation (which has O(n log n) cost, exactly the same as was used in constructing that tree in the first place, so the overall time is still O(n log n)), but this is cheating.</p>

<p>For worst-case O(1) time, the authors claim it was an open problem for any data structure, so I don't think you're going to find an easy answer.</p>

CC BY-SA 3.0
2014-07-10T23:52:07.923Z
Is this trivial solution actually correct?  It's obvious to me that it works only if a given tree is concatenated to another only once.  If I apply the same construction to recursive concatenation of $n$ singleton lists, I get $O(n \log n)$ complexity, which corresponds to $O(n \log^2 n)$ complexity in the tree case.
Geoffrey Irving
CC BY-SA 2.5
2010-09-08T22:23:05.457Z
I downloaded the paper, but it clearly states that "They [K&T] asked whether the join operation can be implemented in O(1) worst-case time even in an ephemeral setting, while supporting searches and updates in logarithmic time."
Blaisorblade
CC BY-SA 2.5
2010-09-10T20:41:29.830Z
Good point, Blaisorblade. I missed that sentence.
jbapple
CC BY-SA 2.5
2010-08-16T23:11:32.883Z
I'm not sure if Brodal et al. meant that it was an open problem even in an ephemeral setting. Are you talking about the sentence in the abstract that references "an open problem posed by Kaplan and Tarjan"? If so, I think it's clear from the context of *that* paper that K&T were saying that the question was open in a purely functional structure.
jbapple
CC BY-SA 2.5
2010-08-16T22:53:40.137Z
2010-08-16T22:53:40.137Z
Alexandre Passos
<p>I downloaded the paper you mention, and it answers "no", at least at the publishing time of the paper. That's for two reasons:</p>

<ol>
<li><p>a paper is required to properly review related work, and they do so in the introduction, with a summary in Fig. 1, which says "no". At least if it has been published in a reputable conference, but it looks like that (Brodal is cited a couple of times in "Purely functional data structures" by C. Okasaki, a reference on the subject).</p>

<p>However, they mention in the text an algorithm with search time O(log n log log n) and concatenation in O(1) time, sketched in the K&amp;T paper from STOC '96. It might be interesting for you.</p>

<ul>
<li>the open challenge by K&amp;T that they solve is about dictionaries with O(1) concatenation and O(log N) search/insert/delete, even for ephemeral structures.</li>
</ul></li>
</ol>

<p>Point 1. also ensures that you can simply look for papers citing this one to find any later results, they would need to cite it.</p>

<p>If the question were of practical relevance (but it is not supposed to be), I believe that constant factors are more important than the difference between O(1) and O(log N) (as discussed in Sedgewick's Introduction to algorithms), so you need to look just for benchmarks for the use case of your application.</p>

CC BY-SA 2.5
2010-09-09T08:03:39.460Z
ESOP is a reputable conference, if that is what you meant.
Charles Stewart
CC BY-SA 2.5
2010-09-10T14:59:10.207Z
That was my question, but for ESA, where the paper is published, not ESOP (maybe you meant that). I was not sure I could rely on the conference rank.
This unofficial ranking page suggests that also ESA is quite reputable: http://www3.ntu.edu.sg/home/assourav/crank.htm
Blaisorblade
CC BY-SA 2.5
2010-09-08T22:49:38.953Z
2010-09-08T22:49:38.953Z
Blaisorblade
<p>In <a href="http://www.cs.au.dk/~gerth//pub/esa06trees.html">Purely Functional Worst Case Constant Time Catenable Sorted Lists</a>, Brodal et al. present purely functional balanced trees with O(1) concatenate and O(lg n) insert, delete, and find. The data structure is somewhat complicated.</p>

<p>Is there a simpler balanced search tree with O(1) concatenate, functional or not?</p>

<functional-programming><ds.data-structures>
Simple balanced trees with O(1) concat?
jbapple
# Simple balanced trees with O(1) concat?

(Asked by: username_0 on 2010-08-16)

In [Purely Functional Worst Case Constant Time Catenable Sorted Lists](http://www.cs.au.dk/~gerth//pub/esa06trees.html), Brodal et al. present purely functional balanced trees with O(1) concatenate and O(lg n) insert, delete, and find. The data structure is somewhat complicated.

Is there a simpler balanced search tree with O(1) concatenate, functional or not?

**Tags:** functional-programming, ds.data-structures

---

## 2 answers

### Answer by username_1 on 2010-08-16. Score: 5 | Accepted answer

You can trivially make a data structure with O(1) *amortized* concatenation time, by just reinserting everything from one tree on the other on concatenation (which has O(n log n) cost, exactly the same as was used in constructing that tree in the first place, so the overall time is still O(n log n)), but this is cheating.

For worst-case O(1) time, the authors claim it was an open problem for any data structure, so I don't think you're going to find an easy answer.

> **Comments:**
> **username_0**: I'm not sure if Brodal et al. meant that it was an open problem even in an ephemeral setting. Are you talking about the sentence in the abstract that references "an open problem posed by Kaplan and Tarjan"? If so, I think it's clear from the context of *that* paper that K&T were saying that the question was open in a purely functional structure.  
> **username_3**: I downloaded the paper, but it clearly states that "They [K&T] asked whether the join operation can be implemented in O(1) worst-case time even in an ephemeral setting, while supporting searches and updates in logarithmic time."  
> **username_0**: Good point, Blaisorblade. I missed that sentence.  
> **username_2**: Is this trivial solution actually correct?  It's obvious to me that it works only if a given tree is concatenated to another only once.  If I apply the same construction to recursive concatenation of $n$ singleton lists, I get $O(n \log n)$ complexity, which corresponds to $O(n \log^2 n)$ complexity in the tree case.  

---

### Answer by username_3 on 2010-09-08. Score: 4

I downloaded the paper you mention, and it answers "no", at least at the publishing time of the paper. That's for two reasons:

1. a paper is required to properly review related work, and they do so in the introduction, with a summary in Fig. 1, which says "no". At least if it has been published in a reputable conference, but it looks like that (Brodal is cited a couple of times in "Purely functional data structures" by C. Okasaki, a reference on the subject).

   However, they mention in the text an algorithm with search time O(log n log log n) and concatenation in O(1) time, sketched in the K&T paper from STOC '96. It might be interesting for you.

   * the open challenge by K&T that they solve is about dictionaries with O(1) concatenation and O(log N) search/insert/delete, even for ephemeral structures.

Point 1. also ensures that you can simply look for papers citing this one to find any later results, they would need to cite it.

If the question were of practical relevance (but it is not supposed to be), I believe that constant factors are more important than the difference between O(1) and O(log N) (as discussed in Sedgewick's Introduction to algorithms), so you need to look just for benchmarks for the use case of your application.

> **Comments:**
> **username_4**: ESOP is a reputable conference, if that is what you meant.  
> **username_3**: That was my question, but for ESA, where the paper is published, not ESOP (maybe you meant that). I was not sure I could rely on the conference rank. This unofficial ranking page suggests that also ESA is quite reputable: http://www3.ntu.edu.sg/home/assourav/crank.htm  

---

