从树中随机选择节点

Question

我有一颗树形数据结构，每个节点可以有多个子节点。因此不仅有左右两个孩子，还有更少或更多的子节点。 现在我想随机选择这个树的一个节点。对于每个节点，我知道它连接了多少个子节点。但是如何以随机方式选择它们，均匀地选择更好。有任何想法吗？我找到了针对只有左右子节点的情况的解决方案，但正如我所说的，那并不适用于这里。

- user1994555

---

你只对挑选“叶子”节点感兴趣吗？还是也想选择“分支”节点？ - Oliver Charlesworth

实际上，我对弧线很感兴趣，但当我有了节点后，我只会选择进入该节点的弧线。换句话说，不仅是叶子节点，任何节点都应该是可能的。 - user1994555

Answer 1

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

一种非常简单的方法是执行DFS或其他遍历树，并将所有节点存储在动态数组中。然后，您可以通过仅索引到数组来进行O(1)时间的随机抽样。但是，这具有O(n)的内存开销，并且如果树不断变化，则不好。

如果树正在快速更改，则减少重新计算索引所需的时间的另一种编号节点的方法如下。首先将根节点编号为0。然后，递归编号第一个子树的节点，然后是第二个子树等等。而不是显式存储此编号，您可以通过使每个树节点存储该节点根下的子树中节点总数来隐式存储它。因此，要查找树中的第n个节点，可以执行以下操作：

1. 如果n=0，则返回根节点。 2. 否则，设置n=n-1，然后按照从左到右的顺序循环遍历当前节点的每个子节点： 1. 让k成为子树中的节点数。 2. 如果n

如果您有一个相对平衡的树和一个合理的分支因子，则使用此方法可以快速运行，因为您可以快速丢弃不包含第n个元素的树的部分。

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

但是，这种方法仍然使用O(n)的开销来存储计数。要使用线性时间运行的O(1)开销算法，请查看@NPE基于蓄水池抽样的出色解决方案。

希望这有所帮助！

- templatetypedef

Answer 2

如果均匀分布很重要，您可以遍历树并使用蓄水池抽样。然而，这样做的时间复杂度与节点数成线性关系。

- NPE

---

好的，我现在已经阅读了蓄水池抽样算法，但是我不理解你的想法。假设我在我的树的根节点上，并且我可以看到它有4个子树。第一个子树包含四个节点，第二个子树包含三个节点，第三个子树包含两个节点，第四个子树再次包含四个节点。好的，那么现在怎么办？我猜我的n是节点的总数。但是k是什么？何时我会知道应该选择某个节点？ - user1994555

如果你只需要一个数字，k=1。如果你想要五个数字，你可以使用 k=5。 - NPE

好的，但我怎么知道我应该选择一个节点？你知道，它什么时候停止？ - user1994555

@user1994555：你需要遍历整个树。最终，你将在蓄水池中有k个元素，这就是你的随机样本。 - NPE