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的选择概率。这是一个多维的，右侧的硬币或死亡。对？

这棵树可能会带来另一个元素：如果被选中的机会取决于你在树中的位置以及你是否被允许回溯，概率将被改变。如果是这种情况，每个节点选择的机会都不相同。从根开始意味着您可以访问所有子节点。处于第一级并且不能够回溯消除了根和所有其他第一级节点的考虑，等等。

你试图解决哪个问题？