algorithm - rBST の確率の計算

Question

こんにちは、A、B、C を rBST (二分探索木) のランダムな順序で挿入するとします。5 つの結果があります。

 B   
A C 

A
  B
    C

   C
 B
A

  C
A
 B

A
  C
 B

a) これらの木を手に入れる確率は? b)「D」を追加した場合の確率は次のようになります。

A
 B 
  C 
   D

最悪の確率？御時間ありがとうございます！

Answer 1

最初に気付くのは、最初は 3 つの要素があることです。

BST を再帰プロセスとして構築することができます。最初にルートを選択し、再帰的に左と右のサブツリーを構築します。どちらもルートによって決定されます。

アイテムがある場合n、そのうちの 1 つをツリーのルートとして選択する確率は明らかです1/n(ランダムとは、一様にランダムで、以前の選択とは無関係であることを意味すると思います)。

もちろん、要素が 1 つまたは 0 の場合、考えられるツリーは 1 つだけなので、そのツリーを構築する確率は に等しくなり1ます。

ケース 1:

 B   
A C 

Pr = Pr(select B as a root of a whole tree) 
     * Pr(tree consisting of 1 element because only A is less than B) 
     * Pr(tree consisting of 1 element because only C is greater than B) 
   = 1/3 * 1 * 1 = 1/3

ケース 2:

A
  B
    C

Pr = Pr(select A as a root of a whole tree) 
     * Pr(tree of 0 elements because none of elements is less than A)
     * Pr(select B as a root of tree of elements greater than A) 
     * Pr(tree of 0 elements because none of remaining elements is less than B)
     * Pr(tree of 1 element because C is greater than B) 
   = 1/3 * 1 * 1/2 * 1 * 1 = 1/6

ケース 3、4、5:

これらのツリーの構築は、同じ構造を共有しているため、ケース 2に似ています。確率を計算して確認できます。

概要

もちろん、3 つの要素で可能なすべての BST が上にリストされているため、これらのツリーの確率は合計で 1 になるはずです。確認してみましょう。

Pr(Case 1) + 4 * Pr(Case 2) = 1/3 + 4 * 1/6 = 1/3 + 4/6 = 1

上記の方法を調べることで、2 番目の質問に対する答えを見つけることができます。