所以，我想出了这个方案，用于在多个线程同时具有读写访问权限的二叉树中旋转时锁定节点，这涉及每次旋转锁定四个节点，这似乎非常多？我想出了一种更聪明的方法，然后我想出了一种减少所需锁定的方法，但谷歌并没有出现太多（我可能使用了错误的术语）。
这是我目前的方案，橙色和红色节点被旋转移动或更改，需要锁定，绿色节点与任何受旋转影响但本身不受旋转影响的节点相邻。
我认为必须有一种更好的方法来做到这一点，我的一个想法是拍摄受影响的四个节点的快照，在快照中旋转它们，然后用快照替换当前节点（假设在我正在做旋转）-这将使我几乎可以无锁，但考虑到旋转是一个相当快速的操作（重新分配三个指针），我担心内存开销可能会很大？
我想我正在寻找如何有效地做到这一点的指针（没有双关语）。
看看不可变二叉树。您必须更改更多节点（每个节点到根），但这不会改变双向插入的复杂性log n。事实上，它甚至可以提高性能，因为您不需要任何同步代码。
例如，Eric Lippert 写了一些关于 C# 中不可变 avl 树的文章。最后一个是：C# 中的不变性第 9 部分：学术？加上我的 AVL 树实现
Lock-free algorithms, as far as I can see, lack reference counts, which makes their general use problematic; you can't know if the pointer you have to an element is valid - maybe that element went away.
Valois' gets around this with some exotic memory allocation arrangement which is not useful in practise.
The only way I can see to do lock-free balanced trees is to use a modified MCAS, where you can also do increment/decrement, so you can maintain a reference count. I've not looked to see if MCAS can be modified in this way.
考虑到锁本身通常会占用一些严重的资源，因此通常会有一个锁用于整个数据结构。我猜你想避免这种情况，这一定是一些非常特殊的场景，你有很多 CPU 密集型工作线程不断更新树？
你可以通过让每 N 个节点共享一个锁来获得平衡。进入轮换操作时，找到受影响节点使用的唯一锁集。大多数情况下，它只是一把锁。
最佳解决方案取决于您的应用。但是，如果您喜欢一个内存数据库，并且想要对其进行并发更新并且想要非常细粒度的锁定，那么您还可以查看不需要像二叉树那样经常进行节点旋转的 B 树. 它们也是自动平衡的，与二叉树不同，二叉树需要更多的旋转来保持平衡（例如 Splay 或 AVL 树）。
如果您想对树进行事务性修改，则可以使用功能性 B 树（Thomas Danecker 将其称为不可变树）。这些是一种“写入时复制”的二叉树，您唯一需要锁定的是根节点。所以你只需要一把锁。实际上，这些操作的复杂性与二叉树相同，因为功能二叉树上的所有操作都是 O(log n) 并且无论何时从任何树下来都会花费相同的对数时间。
每个节点拥有一个锁很可能不是正确的解决方案。
John Valois 的论文简要描述了一种使用辅助节点实现二叉搜索树的方法。我在并发 LinkedHashMap 的设计中使用了辅助节点方法。您可能可以在 CiteSeerX 上找到许多其他关于并发树的论文（非常宝贵的资源）。除非真的有必要，否则我会远离使用树作为并发数据收集，因为它们由于重新平衡而往往具有较差的并发特性。通常更务实的方法，如跳过列表，效果更好。
我尝试使用写入时的部分复制使二叉树无锁读取。我在这里发布了一个不完整的实现http://groups.google.com/group/comp.programming.threads/msg/6c0775e9882516a2?hl=en&
