我从二叉树中随机选择节点，我必须构建一个黑盒测试来证明所有节点被选中的概率几乎相同。
我正在根据这篇文章调整卡方检验算法 http://en.wikibooks.org/wiki/Algorithm_Implementation/Pseudorandom_Numbers/Chi-Square_Test 但我对“r”应该是什么感到有点困惑。
作为一个附带问题，您认为这是证明一组结果中随机性的适当算法吗？
谢谢， 迪奥戈
最佳答案
答案就在引文中。向下滚动到 javadocs:
* @param r upper bound for the random range
在我看来 r 应该是树中的节点数。你同意吗？
I'm randomly selecting nodes from a Binary Tree and I have to build a black-box test that proves all nodes have the nearly the same probability of being selected.
我不明白这个。你？它似乎不是对树数据结构的测试，而是更多关于用于选择要选择的节点的随机算法。这个结果证明了什么？
请告诉我你在做什么。这是我的想象:
- 您的树中有一个节点列表。
- 您使用随机算法以某种方式从您的树中选择一个节点。
- 您遍历树以找到该节点。
如果您的树中有 r 个节点，则每个节点都应有 1/r 的概率被选中。它是一个多维的 r 面硬币或骰子。对吧？
树可以将另一个元素加入组合:如果被选中的机会取决于您在树中的位置以及您是否被允许回溯，则概率会发生变化。如果是这样的话，每个节点被选中的机会是不同的。从根开始意味着您可以到达所有子节点。处于第一层且无法回溯会消除根节点和所有其他第一层节点的考虑，依此类推。
你想解决什么问题？
关于algorithm - 卡方检验算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4063578/