如何从树中随机选择一个元素？是否需要事先知道树的深度/大小？
3个回答
14
这并不难。为了均匀地随机选择节点，只需按任何顺序遍历树。让第n个检查的节点以1 / n的概率成为所选节点。也就是说，将要返回的节点记录在一个变量中，并且在查看第n个节点时，用1 / n的概率将当前节点替换为第n个节点。可以通过归纳法证明，无需事先知道有多少个节点，即可均匀地随机返回节点。
- Jeffrey
1
5给它一个名字：这是一个众所周知的算法，被称为蓄水池抽样。 - Joey
2
如果你的叶子已经被结构化为可在可索引数据类型（例如数组）中存储，那么你可以轻松地执行以下伪代码：
random_leaf = leaf_pile[ random( size of leaf pile ) ]
很好，令人耳目一新的 O(1) :-)
当然，可能会有漏洞，所以您可能需要从那里进行迭代。如果它存储为链表，则可以通过迭代进行遍历。
这只是提供一种显而易见的替代方案。它确实取决于您的数据结构和最常用的用例。
- eruciform
-1
只需对每个节点进行0到（子节点数量-1）范围内的随机调用，并选择该编号之后的下一个子节点。
重复此过程，直到到达叶节点为止。
- Quonux
2
这将偏向于树的上层节点。例如，选择根节点的概率为1/3（假设最多有2个子节点）。选择最左侧的叶节点的概率为(1/3)^k，其中k为叶节点的深度。 - Menezes Sousa
这是正确的，然而在某些情况下这并不重要，但感谢您指出。 - Quonux
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接