In Purely Functional Worst Case Constant Time Catenable Sorted Lists, Brodal et al. present purely functional balanced trees with O(1) concatenate and O(lg n) insert, delete, and find. The data structure is somewhat complicated.Is there a simpler balanced search tree with O(1) concatenate, functional or not?
Simple balanced trees with O(1) concat?
functional programming;ds.data structures
You can trivially make a data structure with O(1) amortized concatenation time, by just reinserting everything from one tree on the other on concatenation (which has O(n log n) cost, exactly the same as was used in constructing that tree in the first place, so the overall time is still O(n log n)), but this is cheating.For worst-case O(1) time, the authors claim it was an open problem for any data structure, so I don't think you're going to find an easy answer.