2-3 trees actually do give you log-time concatenation; most species of balanced trees do, including red-black, AVL, splay (amortized, of course), skip lists, and treaps.