(More) Efficient locking when rotating nodes in threaded binary tree

Question

So, I've come up with this scheme for locking nodes when rotating in a binary tree that several threads have both read and write access to at the same time, which involves locking four nodes per rotation, which seems to be an awfully lot? I figured some one way smarter then me had come up with a way to reduce the locking needed, but google didn't turn up much (I'm probably using the wrong terminology anyways).

This is my current scheme, Orange and Red nodes are either moved or changed by the rotation and need to be locked and Green nodes are adjacent to any node that is affected by the rotation but are not affected by it themselves.

binary tree rotation

I figured there has to be a better way to do this, one idea I have is to take a snapshot of the four nodes affected, rotate them in the snapshot and then replace the current nodes with the snapshot ones (assuming nothing has changed while I was doing the rotations) - this would allow me to be almost lock free but I'm afraid the memory overhead might be to much, considering that rotation is a rather quick operation (re-assigning three pointers) ?

I guess I'm looking for pointers (no pun) on how to do this efficiently.

Answer 1

Have a look at immutable binary trees. You have to change a bit more nodes (every node to the root), but that doesn't change the complexity of an insert which is log n both ways. Indeed, it may even improve the performance because you do not need any synchronization-code.

For example, Eric Lippert wrote some posts about immutable avl trees in C#. The last one was: Immutability in C# Part Nine: Academic? Plus my AVL tree implementation