計算概率

Question

大家好讓說，我們將插入A，B，C中的rBST的（二叉搜索樹）隨機的順序，將有5個結果

B 
A C 

A 
    B 
    C 

    C 
B 
A 

    C 
A 
B 

A 
    C 
B 

一）什麼是概率得到這些樹？ B）會是什麼，如果我們增加了一個「d」，它看起來像這樣的可能性：

A 
B 
    C 
    D 

最壞情況的概率？謝謝你的時間！

Answer 1

首先要注意的是，您最初有3個元素。

您可以將BST構建爲遞歸過程。首先，您選擇根，然後遞歸地構建左側和右側子樹 - 它們都由根確定。

如果你有n項目，你選擇其中一個作爲樹根的概率很明顯是1/n（我假設隨機意思是一致隨機的並且獨立於以前的選擇）。

當然，如果您有1個元素或0個元素，則只有一棵樹可能，因此構建該樹的概率等於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 

你能弄清楚第二個問題的答案是檢查上述方法。