I was reading the Kode Vicious column in the April 2010 issue of Communications of the ACM. He was discussing data structures as the canon of computer science, like elementary equations are the canon of physics. The four data structures listed were the array, list, tree, and hash table.

I know that there are concurrent and thread-safe implementations of these structures and variations on them (e.g. vectors and hash maps in TBB). One variation on the simple tree structure are self-balancing trees that maintain a search depth as items are added or removed from the tree. I've always thought that a thread-safe red-black or AVL tree structure might be hard to implement, without locking the entire structure for rebalancing.

Has anyone used or implemented a thread-safe self-balancing tree? Is there a key idea to not needing to lock the entire tree when nodes are being shifted around? Or is this kind of structure too complex to do in an efficient method?