合并n个AVL树

Question

我有n个大小为n_1，n_2，...，n_n的AVL树，所以sum（n_i）= n。 我可以合并两个AVL的大小线性时间的大。 我可以在多少时间内合并这n棵树？ Thx任何帮助

Answer 1

如果你有k个不同的树，那么你需要做（k - 1）合并将它们一起收集到一棵树中。所以问题是每次合并需要多长时间。

假设您采用的策略是在任何时间点总是将两棵最小的树合并在一起。如果在执行此操作时有m棵树可用，则第二小树的大小将主宰合并的运行时。这个大小至多是（n-1）/（k-1），当最小的树只有一个元素而所有其他树都具有它们中的所有元素时发生。这意味着，如果你这样做ķ合并，成本将

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） harmonic number。这个整个表达式就是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树来排序得比Ω（n log n）更快，然后在O（ n）排序的时间优于Ω（n日志n），其中is known to be impossible。

希望这会有所帮助！