data-structures - 如何重新平衡随机二叉搜索树

Question

情况如下:有一个平衡的二叉搜索树，可以被数十个线程访问。所以当我需要插入或删除一个节点时，我不想因为并发而锁定整个树。随着时间的推移，它再次变得不平衡。当树不那么忙于使用时，我终于有机会锁定并重新平衡它。我怎样才能做到这一点？

还是我可以使用更好的数据结构？

Answer 1

您实际上可以使用 Day-Stout-Warren algorithm 重新平衡它。 .它在节点数量上是线性的，因此可能需要一段时间。此外，这种方法提出了一个问题:如果在不重新平衡正在读取的树的时间间隔内，它很快变得严重不平衡，并且所有后续读取都在 O(N) 而不是 O(logN) 中完成，该怎么办？ ?为了不锁定东西而让这种性能损失几个小时可以吗？你确定会有性能上的胜利吗？

如果你可以容忍缺乏线性化(即你写了一个值，但是当你没有找到它之后立即搜索它；它最终会在那里，但 100ms-10s 可能会过去)，你可以实现一个“写时复制”树:所有写入都由一个线程完成(具有重新平衡)，并且您定期将树克隆为只读副本，该副本可供读取线程使用而无需任何并发控制，您只需以原子方式发布它。如果树是在可以作为一个整体复制并作为一个整体进行释放/垃圾收集的连续内存块之上实现的，则可以特别快地完成。

另一种选择是使用并发 skip list :它提供对数平均案例搜索/删除/插入时间，并且更容易并行化。有标准无锁implementation for Java如果你碰巧使用它。您可以找到有关并发跳过列表和平衡搜索树的更多信息 here .特别是，您会发现那里提到了 chromatic tree ，一种针对并发再平衡进行了优化的二叉搜索树。