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 个数字。

现在考虑：有多少种方式可以发生？

  • 1种方式先选10，再选7，再选15；和12！其余的选择方法。
  • 1种方式先选10，再选15，再选7；又是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/15 的概率，那么，对于 7 和 15 成为第一个孩子，概率是 2/14*1/13

总计：1/15*2/14*2/13

于 2012-11-04T01:29:32.993 回答