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

Question

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:

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?

Has anyone come up with any simplifications since then?

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?

Explanation / Answer

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

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.

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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.