我有 n 个大小为 n_1,n_2,...,n_n 的 AVL 树,因此 sum(n_i)=n 。我可以在较大的一个大小的线性时间内合并两个 AVL。我可以在多长时间内合并这 n 棵树?感谢任何帮助
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) 更好的排序时间,已知这是不可能的。
希望这可以帮助!