algorithmstringdata-structuresstlropes

What is the concatenation complexity of balanced ropes?


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

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?


Solution

  • 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.