6
$\begingroup$

I'm interested in persistent catenable deques: deques that can be concatenated.

Kaplan and Tarjan came up with the first such data structure in 1995; Okasaki came up with a simpler, amortized version in 1997 using lazy evaluation (see Okasaki for references). Then a couple years later, Kaplan, Okasaki, and Tarjan came up with a simpler implementation using more general mutation in a disciplined manner. Then in 2003, Mihaesau and Tarjan came up with a simpler, non-bootstrapped strictly functional version.

My questions:

  1. The Mihaesau and Tarjan catenable deques appear, to my untrained eye, to offer $O(\log n)$, or possibly even $O(\log(\min(i, n-i)))$ random access (lookup and modify). Is this correct?

  2. Has anyone come up with any simplifications since then?

  3. Has anyone either found a way to combine $O(\log n)$ (or, better yet, $O(\log(\min(i,n-i)))$) splitting along with $O(1)$ concatenation, or proved that it can't be done? For that matter, what about $O(\log n)$ arbitrary insertion and/or deletion?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Please add some links. $\endgroup$
    – jbapple
    Mar 25 '14 at 0:17
  • 1
    $\begingroup$ Are you asking us to do your research for you? Have you used Google Scholar or similar? Some engines even offer "cited by" searches, so it should be easy to find the newest work, assuming they do cite the "classics". Question 1. looks salvageable, if you made the question mostly about that fact (explanation needed). (Note that proper references should include title, authors and year at least, and an "unbreakable" link using DOI or such.) $\endgroup$
    – Raphael ♦
    Mar 25 '14 at 0:36
7
$\begingroup$

I don't think the Tarjan and Mihaesau catenable deques have that lookup/modify performance. The non-catenable ones certainly do, though.

  1. I don't think there are any published simplifications since then. As far as I can tell, the T&M version wasn't ever published in a peer-reviewed venue. Publication about purely functional data structures seems to have slowed down in the last few years.

  2. As far as adding splitting while maintaining constant-time concat, you can look at Brodal et al's "Purely Functional Worst Case Constant Time Catenable Sorted Lists" for some references. I don't think this problem is solved yet. As far as I know, the best known result is O(lg lg n) concat and O(lg min(n - i,i)) split, from Kaplan & Tarjan's "Purely functional representations of catenable sorted lists". For the insertion and deletion case that involves lookup, see the lower bounds I mentioned in another question on ropes. For the insertion and deletion case without lookup, you can use an order-maintenance structure.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Yes, of course that was a typo! Why don't you think the catenable ones have that performance? As far as I can tell, the elements of the front and rear buffers increase in size geometrically with depth, and are never empty. Am I missing something? $\endgroup$
    – dfeuer
    Mar 25 '14 at 0:30
  • $\begingroup$ Also, note that O(log n) concatenation along with O(log n) splitting gets O(log n) insertion/deletion; I was suggesting the latter as a weaker alternative to O(log n) splitting (in combination with O(1) concatenation). $\endgroup$
    – dfeuer
    Mar 25 '14 at 0:34
  • $\begingroup$ I don't think [:P] this answer adds more substance than the original question; it's "only" another data point of "up to my knowledge". That's not your fault, though, but the question's. $\endgroup$
    – Raphael ♦
    Mar 25 '14 at 0:37

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.