这是我大学的数据结构课程中的一个问题。我不明白这个问题是什么意思。任何人都可以详细说明这个问题，以及它的答案。
假设我们将 1 到 15 之间的所有数字插入到一棵最初为空的二叉搜索树中；这些键的所有排列都同样可能是插入顺序。计算生成的树以 10 作为其根、7 作为根的左孩子和 15 作为根的右孩子的概率。
问问题
155 次
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 回答