What is the concatenation complexity of balanced ropes?

Question

I've looked at different papers and here is the information that I've gathered:

• SGI implementation and C cords neither guarantee O(1) time concatenation for long ropes nor ~log N depth for shorter ones.
• Different sources contradict each other. Wikipedia claims O(1) concatenation. This page says that concatenation is O(1) only when one operand is small and O(log N) otherwise.

So, what is the time complexity of concatenation? When exactly rebalancing is performed to ensure this concatenation complexity while maintaining tree balance? Are some specific usage patterns assumed when talking about this complexity?

Answer 1

The wikipedia article is unclear, the paper "Ropes: an Alternative to Strings" that it cites nowhere, claims such a complexity result.

On the other hand, this recent paper (by Gerth Stølting Brodal, Christos Makris and Kostas Tsichlas) does: "Purely Functional Worst Case Constant Time Catenable Sorted Lists". They also have O(logn) search, so indeed you can tag it "balanced", I haven't read the details though, just the results.

"Rope" is a term that is (relatively) common in practice, but not in research. Instead, I searched for catenable queues (or lists), especially research done by people as Tarjan, Okasaki, Kaplan and others, I think that's where your real answer is.