I don't have an answer for you (I'm just making the point that when people argue about how inefficient trees are, they're usually assuming a struct with two edge pointers), but a more direct answer to your question might be:

http://www.cl.cam.ac.uk/research/srg/netos/lock-free/

(That's a lock-free red-black tree impl).