2

各ノードに保存されている値に従って順序付けられるように、通常の方法でバイナリツリーに多くのノードを保存しています。つまり、ツリーを左から右に再帰して、ソートされた順序で合計セットを取得できます。

ただし、ツリー内にあるノードのサブセットへのポインターの大きな個別の配列があり、この配列の順序はランダムです。

この配列をすばやくソートできるようにしたいと思います。これを高速化するために二分木構造を参照する方法はありますか? 必要に応じて、任意のノードにメンバーを追加できます。

ありがとう！

4

1 に答える 1

1

ノードにフラグを追加することで、ランタイムを取得できますO(t+a)(t はツリーのサイズで、a は配列のサイズです)。これは、最初に配列にフラグを設定してから、ツリーを走査し、フラグが設定された値を選択することによって行われます。

log aこれは、ツリーが配列の数倍しかない場合にのみ有利です。t>> の場合、ランタイムがO(a * log a).

于 2013-02-26T23:32:36.203 に答える