計算樹中值的概率

Question

這是我大學數據結構課程中的一個問題。我不明白這個問題的含義。有沒有人可以在這個問題上詳細說明我的問題，以及答案。

假設我們將1到15之間的所有數字插入到最初的 空二叉搜索樹中;這些密鑰的所有排列同樣可能是插入順序 。計算產生的樹的根的概率爲10，作爲其根的7，作爲根的左子孩子 和15作爲根的右孩子。

Answer 1

爲了「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」，所以它關心的可能的方式來構建數字樹，而不是實際數目不同的結果樹（有差異，因爲不同的插入順序可能最終構建相同的樹（例如，儘管不同的插入順序，減去12個其他數字之後的2個樹會構建相同的樹）

概率是:(構建由問題指定的排列方式的數量）除以（th構建樹的可能方式的總數）：

因此(12! * 2)/(15!)是您想要的概率。

Answer 2

除非您創建自平衡樹，否則您獲得的樹根據元素插入的順序而不同。對於root來說，10必須是插入的第一個數字。這有概率1/15或1/15 然後，對於7和15是第一個孩子的概率是2/14 * 1/13

總數：1/15 * 2/14 * 2/13