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

Question

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

data-structurestreebinary-search-treeavl-tree

4

这是情况：有一棵平衡的二叉搜索树，可能被十几个线程访问。因此，当我需要插入或删除一个节点时，我不想由于并发性而锁定整棵树。随着时间的推移，它变得不再平衡。当树没有被频繁使用时，我最终有机会锁定并重新平衡它。我该如何做到这一点？
或者，我可以使用更好的数据结构吗？

- Knova Chan

你是如何遇到这种情况的？仅当我们了解使用情况时，才能决定更好的数据结构。树仅被读取还是经常更新？ - displayName

当您删除节点时，只需将其标记为已删除，但保留在树中。当您有时间锁定和重新平衡时，请对旧树进行中序遍历，并从未标记为已删除的所有节点构建新树。 - Jim Mischel

@displayName 大部分时间，该树以高并发方式进行读取，同时频繁更新。但每隔几个小时，读取并发性会降低，此时锁定将是可行的。 - Knova Chan

我有一个解决方案，但可能不是很好 - 使用两个树的副本。允许从两个树中读取。但在更新时，锁定一棵树并对其进行更新，同时让读取转到另一棵树。然后更新第二个树并让读取转到第一个树。 - displayName

1

@displayName 每个创意点子：） - Knova Chan

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- starikoff · Accepted Answer

你可以使用Day-Stout-Warren算法重新平衡它。这个算法的时间复杂度与节点数成线性关系，所以可能需要一些时间。此外，这种方法也会引发一个问题：如果在不重新平衡正在被读取的树的时间间隔内，它快速地变得严重失衡，那么所有后续的读取操作都将花费O(N)的时间而不是O(logN)，为了不锁定事物而导致性能损失长达数小时是否可行？您确定这样做会带来性能提升吗？

如果您可以容忍缺乏线性化（即您写入一个值，但在立即搜索时找不到它；它最终会出现，但可能需要100毫秒至10秒的时间），您可以实现“写时复制”树：所有写入都由一个线程完成（同时进行重新平衡），然后您定期将树克隆到只读副本中，读线程可以无需任何并发控制使用该副本，您只需要以原子方式发布它即可。如果树是基于连续内存块实现的，则可以特别快速地完成此操作，并将整个内存块作为一个整体进行复制和释放/垃圾回收。

另一种选择是使用并发跳表：它提供对数平均搜索/删除/插入时间，并且更容易并行化。如果您正好在使用Java，则有一个标准的无锁实现。您可以在这里找到有关并发跳表和平衡搜索树的更多信息。特别地，您可以在那里找到有关色彩树的提及，它是一种针对并发重新平衡进行了优化的二叉搜索树。