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?

Orlantha

all operations are log(N) time complexity. Rope essentially is a Binary Search Tree composed of implicit keys, which are in nature refer to the size of the subtree. That allows powerful operations such concat/split. One of the possible implementations is using a Treap data structure, which is purposefully made to work with implicit keys and with high probability keeping the height of the tree withing 4*log(n) range, which is O(log n). I have done some simple implementation of it using Treap: ideone.com/uMt0Mi. – Understructure

@Yerken: thanks, since I asked this question I've implemented ropes myself -- with guaranteed deterministic log N complexity. It appears that O(1) concatenation is a misconception spread by some people, doing it in O(log N) is trivial. I've glanced at your code, but it doesn't seem to fit rope implementations: if you use parent pointers you must clone the whole tree (in O(N) time) when doing local changes. The point of ropes is that they avoid that. – Orlantha

sorry, don't quite get it, what do u mean by cloning whole tree? All local changes are done through merge and split, which are done only along the cutting line (where pointers are dereferenced) which is a height of the tree – Understructure

@Yerken: where is your concatenation function? I cannot find it. It should work non-destructively in O(log N) time. – Orlantha

I didn't put it separately, but you can see how concatenation is done in the process method. – Understructure

@Yerken: Well, it is not a rope concatenation. If you claim otherwise you should prove it. See this test that passes with my implementation in 70 microseconds. If you can show me how you can do it with your rope implementation I'll take my words back. :) – Orlantha

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.

Doloroso

Thank you for the article, unfortunately it can't be used to implement ropes since it doesn't support efficient split operation (last paragraph of the paper) so we can't retrieve substring efficiently. – Orlantha

Well, if you could find a solution to that, it would be publishable :) The article on ropes is hard to follow, apparently the authors had something against the big-oh notation - but such a notation would make very precise what they are after. On the rebalancing, they are as vague as it gets. "We do rebalancing 'rarely'". Ok... sounds good, I guess... – Doloroso