Chi-Square測試算法

Question

我從二叉樹中隨機選擇節點，我必須構建一個黑盒測試，證明所有節點的選擇概率幾乎相同。

我正在適應基於這篇文章的卡方測試算法http://en.wikibooks.org/wiki/Algorithm_Implementation/Pseudorandom_Numbers/Chi-Square_Test 但我對「r」應該是什麼感到困惑。

就像一個側面問題，你認爲這是一個合適的算法來證明一組結果中的隨機性嗎？

謝謝 迪奧戈

Answer 1

答案是正確的，在引文。向下滾動到的javadoc：

* @param r   upper bound for the random range 

這聽起來好像r應該是樹中的節點的數量。你同意嗎？

我隨機選擇從 二叉樹的節點，我必須建立一個 黑箱測試，證明 有幾乎相同的概率被選中的 所有節點。

我不明白這一點。你做？它似乎不是對樹數據結構的測試，而更多是關於您用來選擇要選擇的節點的隨機算法。這個結果證明了什麼？

請告訴我你在做什麼，請。這是我想象的：

1. 你有你的樹中的節點列表。
2. 您可以使用隨機算法以某種方式選擇要從樹中選擇的節點。
3. 您遍歷您的樹來找到該節點。

如果樹中有r個節點，每個節點應該有1/r的選擇概率。這是一個多維的，右側的硬幣或死亡。對？

這棵樹可能會帶來另一個元素：如果被選中的機會取決於你在樹中的位置以及你是否被允許回溯，概率將被改變。如果是這種情況，每個節點選擇的機會都不相同。從根開始意味着您可以訪問所有子節點。處於第一級並且不能夠回溯消除了根和所有其他第一級節點的考慮，等等。

你試圖解決哪個問題？