algorithm - 合并 n 个 AVL 树

Question

我有 n 个大小为 n_1,n_2,...,n_n 的 AVL 树，因此 sum(n_i)=n 。我可以在较大的一个大小的线性时间内合并两个 AVL。我可以在多长时间内合并这 n 棵树？感谢任何帮助

Answer 1

如果你有 k 棵不同的树，那么你需要总共进行 (k - 1) 次合并以将它们收集到一棵树中。所以问题是每次合并需要多长时间。

假设您采用始终在任何时间点将两个最小的树合并在一起的策略。如果您在执行此操作时有 m 棵树可用，那么第二小的树的大小将支配合并的运行时间。这个大小最多为 (n - 1) / (k - 1)，当最小的树只有一个元素而所有其他树都包含所有元素时，就会发生这种情况。这意味着如果您进行 k 次合并，成本将为

N - 1   N - 1   N - 1         N - 1
----- + ----- + ----- + ... + -----
K - 1   K - 2   K - 3           1

但这是 (n - 1)H(k - 1)，其中 H(k-1) 是 (k-1)次谐波数。整个表达式为 O(n log k)，因此合并时完成的总工作为 O(n log k)。

但是，最重要的是，您必须有一些简单的方法来找到每个点的两棵最小的树。这可以通过按大小降序存储树的优先级队列来完成。您将有 k - 1 轮从树中执行两个出队，然后是一个入队，因此所有优先级队列操作的总时间为 O(k log k)。这也是 O(n log k)，所以算法的总运行时间是 O(n log k)。

我很确定你不能做得比这更好，因为你可以从它们自己的 AVL 树 (k = n) 中的 n 个节点中的每一个开始。如果您可以比 Ω(n log n) 更快地进行合并，那么您可以通过构建通过合并所有较小的树形成的 AVL 树进行比较，然后在 O( n) 比 Ω(n log n) 更好的排序时间，已知这是不可能的。

希望这可以帮助！