algorithm - n AVL ツリーのマージ

Question

sum(n_i)=n となるように、サイズ n_1、n_2、...、n_n の n 個の AVL ツリーがあります。大きい方のサイズの線形時間で 2 つの AVL をマージできます。これらの n 個の木をどれくらいの時間でマージできますか? 助けてくれてありがとう

Answer 1

k 個の異なるツリーがある場合、合計 (k - 1) 回のマージを実行して、それらを 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)H(k - 1) です。ここで、H(k-1) は (k-1) 次の高調波数です。この式全体は 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 ツリーを構築し、O( n)不可能であることが知られているΩ(n log n) よりも優れたソート時間。

お役に立てれば！