12
$\begingroup$

In Purely Functional Worst Case Constant Time Catenable Sorted Lists, 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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – jbapple
    Aug 16, 2010 at 23:11
  • $\begingroup$ 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." $\endgroup$
    – Blaisorblade
    Sep 8, 2010 at 22:23
  • $\begingroup$ Good point, Blaisorblade. I missed that sentence. $\endgroup$
    – jbapple
    Sep 10, 2010 at 20:41
  • $\begingroup$ 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. $\endgroup$
    – Geoffrey Irving
    Jul 10, 2014 at 23:52
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ ESOP is a reputable conference, if that is what you meant. $\endgroup$
    – Charles Stewart
    Sep 9, 2010 at 8:03
  • $\begingroup$ 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: www3.ntu.edu.sg/home/assourav/crank.htm $\endgroup$
    – Blaisorblade
    Sep 10, 2010 at 14:59

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.