algorithm - 使用平衡树进行批量操作

Question

我使用自平衡二叉搜索树（目前它是一棵 AVL 树，但可以用另一棵树代替）。我注意到有一些不同的时期只执行某些操作：很少执行大量删除或插入批处理，而大部分时间它是不可变的搜索树。如果我将重新平衡推迟到批次结束，会有任何性能提升吗？

Answer 1

对于批量插入，将新项目插入到单独的 AVL 树中，然后按照http://www.geeksforgeeks.org/merge-two-balanced-binary-search-trees/中所述合并两棵树。合并树是一个 O(m+n) 操作，其中 m 和 n 是两棵树的大小。当新项目的数量与现有树中的项目数量相比较少时，这种方法应该快得多。

对于批量删除，将 AVL 树中的项目标记为已删除。然后，对树进行中序遍历，从未删除的节点构建一个新的 AVL 树。有关示例，请参见http://www.geeksforgeeks.org/sorted-array-to-balanced-bst/ 。从排序的节点列表构建新树是 O(n) 操作。

Answer 2

说 AVL 树的渐近复杂度是 O(log(N))。但是真正的计算显然是在运行时决定的。

延迟再平衡可以让它看起来很快，但也存在风险。仅当树平衡时，插入的平均时间为 O(logN)。如果批量插入使树高度倾斜，我们可能会得到 O(N) 的插入时间。

无论如何，插入将花费 O(logN)，因此重新平衡不会产生太大影响，因为它也是 O(logN)。

为了获得实际的好处，您需要考虑插入的批量大小，并在插入/删除期间进行搜索以及插入的键的值。