各ノードが複数の子を持つことができるツリー データ構造があります。したがって、左と右だけでなく、それよりも少ないか、またははるかに多くなります。ここで、このツリーからランダムにノードを選択したいと思います。すべてのノードについて、それに接続されている子の数を知っています。しかし、どうすればそれらをランダムに選ぶことができますか? 一様に素晴らしいでしょう. 何か案は？左と右の子供だけの場合の解決策を見つけましたが、前述したように、ここでは実際には当てはまりません。
質問する
1138 次
2 に答える
3
有用な観察結果を次に示します。任意の n に対して n 番目のツリー ノードを効率的に検索できるような方法で、ツリー内のすべてのノードに番号を付けるとします。これができれば、ランダムなノード番号を選択してからそのノードに移動することで、ランダムなノードを効率的に選択できます。
これを行う非常に簡単な方法の 1 つは、DFS またはその他のツリーのトラバーサルを実行し、すべてのノードを動的配列に格納することです。次に、配列にインデックスを付けるだけで、O(1) 回のランダム サンプリングを実行できます。ただし、これには O(n) のメモリ オーバーヘッドがあり、ツリーが絶えず変化している場合は適切ではありません。
ツリーが急速に変化している場合、インデックスの再計算に必要な時間を短縮するノードに番号を付ける別の方法は次のとおりです。ルート ノード 0 に番号を付けることから始めます。次に、最初のサブツリーのノードに再帰的に番号を付け、次に 2 番目のサブツリーに番号を付けます。この番号付けを明示的に保存するのではなく、各ツリー ノードにノードの総数をそのノードをルートとするサブツリー。そのようにして、ツリーの n 番目のノードを検索するには、次の操作を実行できます。
- n = 0 の場合、ルート ノードを返します。
- それ以外の場合は、n = n - 1 に設定し、次のように現在のノードの子を左から右に一度に 1 つずつループします。
- サブツリーのノード数を k とします。
- n < k の場合、このサブツリーで n 番目のノードを再帰的に見つけます。
- それ以外の場合は、n = n - k に設定します。
n 番目の要素を含まないツリーの部分をすばやく破棄できるため、合理的な分岐係数を持つ比較的バランスの取れたツリーがある場合、このアプローチは非常に迅速に実行されます。
このアプローチを使用すると、ツリーから n 番目の要素を選択するための非常に高速な方法 (O(1) ではありません) が得られます。ランダムなインデックスを選択し、そのインデックスのノードを返します。さらに、これはノードがツリーに追加またはツリーから削除された場合でも機能します。ノードが挿入されるたびに、ルートからそのノードまでのパスにあるすべてのノードの数を増やすだけです。ノードが削除されるたびに、ルートから削除されたノードまでのパスにあるすべてのノードの数を減らします。
ただし、このアプローチでも O(n) オーバーヘッドを使用してカウントを格納します。線形時間で実行される O(1) オーバーヘッド アルゴリズムについては、リザーバー サンプリングに基づく @NPE の優れたソリューションを参照してください。
お役に立てれば！
于 2013-01-20T18:59:21.030 に答える
1
均一な分布が重要な場合は、ツリーをトラバースして、リザーバー サンプリングを使用できます。
ただし、これの時間の複雑さは、ノードの数に比例します。
于 2013-01-20T12:32:06.457 に答える