如何重新平衡随机二叉搜索树
how to rebalance a random binary search tree
情况是这样的：有一棵平衡的二叉搜索树，可能被几十个线程访问。所以当我需要插入或删除一个节点时，我不想因为并发性而锁定整棵树。随着时间的流逝，它再次变得不平衡。当树不那么忙的时候，我终于有机会锁定它并重新平衡它。我该怎么做？
或者我可以使用更好的数据结构吗？
您实际上可以使用 Day-Stout-Warren algorithm 重新平衡它。它与节点数量呈线性关系，因此可能需要一段时间。此外，这种方法提出了一个问题：如果在您不重新平衡正在读取的树的时间间隔内它很快变得严重不平衡，并且所有后续读取都在 O(N) 而不是 O(logN) 中完成怎么办？ ？为了不锁定东西而损失数小时的性能是否可以？您确定会有性能胜利吗？
如果你能容忍缺乏线性化（即你写了一个值，但当你在找不到它后立即搜索它；它最终会在那里，但 100 毫秒到 10 秒可能会过去），你可以实现一个 "copy on write" tree：所有的写都是由一个线程完成的（有rebalancing），你周期性的把树克隆成一个只读的副本，供读线程使用，没有任何并发控制，你只需要原子地发布它。如果树是在可以作为一个整体和 freed/garbage-collected 作为一个整体复制的连续内存块之上实现的，那么可以特别快地完成。
另一种选择是使用并发 skip list: it gives logarithmic average case search/delete/insert time and is more easily parallelizable. There is a standard lock-free implementation for Java if you happen to use it. You can find more information about concurrent skip lists and balanced search trees here. Particularly, you can find there mentions of a chromatic tree，一种针对并发重新平衡进行了优化的二叉搜索树。
情况是这样的：有一棵平衡的二叉搜索树，可能被几十个线程访问。所以当我需要插入或删除一个节点时，我不想因为并发性而锁定整棵树。随着时间的流逝，它再次变得不平衡。当树不那么忙的时候，我终于有机会锁定它并重新平衡它。我该怎么做？
或者我可以使用更好的数据结构吗？
您实际上可以使用 Day-Stout-Warren algorithm 重新平衡它。它与节点数量呈线性关系，因此可能需要一段时间。此外，这种方法提出了一个问题：如果在您不重新平衡正在读取的树的时间间隔内它很快变得严重不平衡，并且所有后续读取都在 O(N) 而不是 O(logN) 中完成怎么办？ ？为了不锁定东西而损失数小时的性能是否可以？您确定会有性能胜利吗？
如果你能容忍缺乏线性化（即你写了一个值，但当你在找不到它后立即搜索它；它最终会在那里，但 100 毫秒到 10 秒可能会过去），你可以实现一个 "copy on write" tree：所有的写都是由一个线程完成的（有rebalancing），你周期性的把树克隆成一个只读的副本，供读线程使用，没有任何并发控制，你只需要原子地发布它。如果树是在可以作为一个整体和 freed/garbage-collected 作为一个整体复制的连续内存块之上实现的，那么可以特别快地完成。
另一种选择是使用并发 skip list: it gives logarithmic average case search/delete/insert time and is more easily parallelizable. There is a standard lock-free implementation for Java if you happen to use it. You can find more information about concurrent skip lists and balanced search trees here. Particularly, you can find there mentions of a chromatic tree，一种针对并发重新平衡进行了优化的二叉搜索树。