n個のAVLツリーをマージする

Question

私は、サイズn_1、n_2、...、n_nのn個のAVLツリーを持つので、合計（n_i）= nになります。 2つのAVLを、より大きなものの線形時間でマージすることができます。 これらのn個のツリーをどのくらいの時間マージできますか？ 任意の手助けのためのThx

Answer 1

あなたがk個のツリーを持っているならば、それらをまとめて一つのツリーに集めるために合計（k - 1）マージを行う必要があります。ですから、それぞれのマージがどのくらいの時間かかるのでしょうか。

いつでも2つの最小のツリーをマージするという戦略を採用するとします。これを行うときにm個のツリーがある場合、2番目に小さいツリーのサイズがマージのランタイムを支配します。このサイズは最大で（n-1）/（k-1）です。これは、最小のツリーにただ1つの要素があり、他のすべてのツリーにすべての要素がある場合に発生します。これは、マージをk個行う場合、コストは

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

になることを意味する。しかし、これは（N - 1）である（K - 1）H、Hは（K-1）は（K-1）番目ですharmonic number。この全体の表現はO（n log k）なので、マージの間に行われた総仕事はO（n log k）です。

しかし、その上に各ポイントで2つの小さな木を見つける簡単な方法が必要です。これは、ツリーをサイズの降順で格納する優先度キューを使用して行うことができます。ツリーから2つのデキューを実行してから1つのエンキューを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 log n）です。これはis known to be impossibleです。

希望すると便利です。