Binary search trees, at least the ones I am thinking of, have known purely functional, and therefore lock free implementations. I am currently looking into AVL trees and they don't seem that complicated of an implementation for example.