1

これは私の大学のデータ構造コースからの質問でした。質問の意味がわかりません。誰かが質問とその答えについて私に詳しく説明してもらえますか？

最初は空の二分探索木に1から15までのすべての数字を挿入するとします。これらのキーのすべての順列は、同じように挿入順序である可能性があります。結果のツリーがルートとして10、ルートの左の子として7、ルートの右の子として15を持つ確率を計算します。

4

2 に答える 2

2

「10 as its root, 7 as the left child of the root and 15 as the right child of the root.」が発生するためには、ツリーの挿入順序は次のいずれかである必要があります。

  • 10最初に、次に7、15次に、他の12個の番号を順番に並べます。
  • 10最初に、次に15、7次に、他の12個の番号を順番に並べます。

ここで考えてみましょう：起こり得る方法はいくつありますか？

  • 最初に10を選択し、次に7を選択し、次に15を選択する1つの方法。と12！残りを選択する方法。
  • 最初に10を選択し、次に15を選択し、次に7を選択する1つの方法。そして再び12！残りを選択する方法。

だから、それ(12! * 2)はその特定の取り決めで終わる方法です。

現在、可能なすべての挿入順序のセットは、15個の数値の順列です。これは15!（階乗）です。

質問には「all permutations of these keys are equally likely to be the insertion order」と書かれているので、ツリーを構築するための可能な方法の数に関係していることに注意してください。実際の結果のツリーの数ではありません（挿入順序が異なると同じツリーを構築する可能性があるため、違いがあります（例：上記の2つのケースから他の12の数字を引いたものは、挿入順序が異なっていても同じツリーを構築します）

確率は次のとおりです:(質問で指定された配置を構築する方法の数）を（ツリーを構築するための可能な方法の総数）で割ったもの：

だから(12! * 2) / (15!)あなたが望む確率です。

于 2012-11-04T01:21:46.633 に答える
1

自己平衡ツリーを作成しない限り、取得するツリーは要素の挿入順序によって異なります。ルートを10にするには、最初に挿入する数値を10にする必要があります。これは15のうち1または1/15の確率であり、7と15が最初の子になる場合、確率は2/14*1/13です。

合計：1/15 * 2/14 * 2/13

于 2012-11-04T01:29:32.993 に答える