algorithm - rBST 的计算概率

Question

大家好，假设我们将以 rBST(二叉搜索树)随机顺序插入 A、B、C，将有 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/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

您可以通过检查上述方法找出第二个问题的答案。