合併n個AVL樹

我有n個大小爲n_1，n_2，...，n_n的AVL樹，所以sum（n_i）= n。我可以合併兩個AVL的大小線性時間的大。我可以在多少時間內合併這n棵樹？ Thx任何幫助合併n個AVL樹

2012-02-27 Mugen

這功課嗎？ – stakx 2012-02-27 20:01:34

不，我工作的算法在平均線性時間排序數組 – Mugen 2012-02-27 20:08:46

@ Mugen-你知道，對於基於比較的排序，有沒有可能的方法來平均O（n）時間？除非您知道有關存儲的元素的分佈或元素的類型，否則最好做的是O（n log n）。 – templatetypedef 2012-02-27 20:10:47

如果你有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。

希望這會有所幫助！

來源

2012-02-27 20:09:35 templatetypedef

我知道我不能比nlogn更好地合併，但我認爲也許給定的AVL可以幫助我。謝謝:) – Mugen 2012-02-27 20:24:00

回答

相關問題