dichloromethane

That is a very cool idea. Maybe a bit annoying to use, as you need a fixed size (I think?) special purpose allocator, and having these span across a page boundary doesn't seem possible.

I definitely need to try this out, though.

This code seems broken, though. The big challenge with these kinds of lock-free parallel algorithms is always how to deal with lifetimes and prevent use-after-frees (unless you never want to free anything from this tree, which seems a bit unlikely).

The fundamental problem is that nothing prevents a reader from dereferencing a node the writer has free()'d. Fixing this requires either adding RCU or Hazard pointers.