再平衡算法

再平衡算法可以通过以下方式执行：

Day-Stout-Warren 算法

我们可以使用 Day-Stout-Warren 算法实现实际的再平衡方法。它的时间复杂度与节点数量线性相关。

以下是 DSW 算法的基本伪代码表示。

  • 分配一个名为“伪根”的节点，并将树的实际根节点作为伪根的右子节点。
  • 调用 tree-to-vine 函数，将树转换为以伪根为参数的有序链表。
  • 调用 vine-to-tree 函数，将有序链表再次转换为树，以伪根和树的大小（元素数量）作为参数。
  • 应构建树的实际根节点等于伪根的右子节点。
  • 最后应释放伪根。

“写时复制”树

如果我们可以承受线性化不足（即，我们写入一个值，但当我们立即搜索它时找不到它；它最终会被找到，但在 100ms-10s 后），则可以应用“写时复制”树：所有写入操作都由一个线程（带有再平衡）执行，并且我们定期将树复制到一个只读副本中，该副本可以由读取线程在没有任何并发控制的情况下实现，我们需要以原子方式发布它。

并发跳表

另一个选择是实现一个并发跳表：它提供对数平均情况下的搜索/删除/插入时间，并且更容易并行化。如果您碰巧使用 Java 实现它，则有一个标准的无锁实现。我们可以在这里获得有关并发跳表和平衡搜索树的更多信息。特别是，我们可以在这里找到对色度树的提及，它被表示为针对并发再平衡进行了优化的二叉搜索树。

更新于：2020年1月3日

637 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告