java - 从树中选择随机节点

Question

我有一个树数据结构，其中每个节点可以有多个子节点。所以不仅有左和右，还有更少或更多。 现在我想从这棵树中随机选择一个节点。对于每个节点，我知道有多少 child 连接到它。但是我怎么能以随机的方式挑选它们，统一会很棒。有任何想法吗？我找到了针对只有左 child 和右 child 的情况的解决方案，但正如我所说，这在这里并不适用。

Answer 1

这里有一个可能有用的观察结果:假设您以某种方式对树中的所有节点进行编号，从而可以高效地查找第 n 个树节点以获得任意 n。如果你能做到这一点，那么你就可以通过选择一个随机节点号然后转到该节点来有效地选择一个随机节点。

执行此操作的一种非常简单的方法是执行 DFS 或其他树遍历并将所有节点存储在动态数组中。然后，您只需对数组进行索引即可进行 O(1) 次随机采样。然而，这有 O(n) 的内存开销，如果树不断变化则不好。

如果树正在快速变化，另一种对节点进行编号的方法可以减少重新计算索引所需的时间，如下所示。从根节点编号 0 开始。然后，递归地为第一个子树中的节点编号，然后是第二个子树，等等。而不是显式存储此编号，您可以通过让每个树节点存储节点总数来隐式存储它以该节点为根的子树。这样，要查找树中的第 n 个节点，您可以执行以下操作:

1. 如果 n = 0，返回根节点。
2. 否则，设置 n = n - 1，然后从左到右一次一个地循环当前节点的子节点，如下所示:
   1. 令 k 为子树中的节点数。
   2. 如果 n < k，递归地找到此子树中的第 n 个节点。
   3. 否则，设 n = n - k。

如果您有一个具有合理分支因子的相对平衡的树，这种方法运行得非常快，因为您可以快速丢弃不包含第 n 个元素的树的部分。

使用这种方法，您将获得一种从树中选取第 n 个元素的非常快速的方法(虽然不是 O(1)):选择一个随机索引，然后返回该索引处的节点。此外，即使在树中添加或删除节点，这也有效。每当插入一个节点时，只需增加从根到该节点的路径上所有节点的计数。每当删除一个节点时，递减从根到删除节点的路径上所有节点的计数。

不过，这种方法仍然使用 O(n) 开销来存储计数。对于以线性时间运行的 O(1) 开销算法，请查看@NPE 基于水库采样的出色解决方案。

希望这对您有所帮助!