I've been looking around to find interesting ideas for useful kinds of collections to consider putting into Power Collections. I found this essay, which very eloquently argues for a tree-based list class -- one that allows O(log N) insertion, deletion, and indexing. After mulling that over for a while, I was reading about SGI's extensions to STL and found the rope collection, which is also a tree-based list, although biased more toward allowing very fast copies with incremental copy-on-write, and very fast concatinations and fast sub-strings. (UPDATE: more info here on SGI's rope implementation).

I feel would be interesting to try to combine the best of these ideas into some kind of tree-based list that scales well to very large sizes, and which tries to balance the speed of insertions, deletions, copies, substrings, concatination, and indexing, so that they are all relatively (log N or better) fast in large lists.

Has anyone seen any other examples of tree-based lists in this vein? I'm sure there must be others. Anyone with practical experience using one? What are the pros and cons?