Re:What are the lesser known but cool data structures?
by tptacek on Saturday May 22, 2010 @09:12PM
(#1371464)
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).