java - 从树中选择随机节点

Question

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

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 个元素的部分。

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

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

希望这可以帮助！

Answer 2

如果均匀分布很重要，您可以遍历树并使用水库采样。

但是，其时间复杂度与节点数量呈线性关系。