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

案例二：

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

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