我有一个树数据结构,每个节点可以有多个子节点.所以不仅有左边和右边,还有更少甚至更多.
现在我想随机从这棵树中选择一个节点.对于每个节点,我知道有多少个孩子连接到它.但是我怎么能以随机的方式选择它们,统一会很棒.有任何想法吗？我找到了只有左右孩子的解决方案,但正如我所说,这在这里并不适用.
一种非常简单的方法是执行树的DFS或其他遍历,并将所有节点存储在动态数组中.然后,您可以通过索引到数组中进行O(1)时间随机采样.但是,这有O(n)内存开销,如果树不断变化则不好.
如果树正在快速变化,则对节点进行编号的另一种方法是减少重新计算索引所需的时间,如下所示.首先对根节点0进行编号.然后,递归编号第一个子树中的节点,然后是第二个,等等.不是明确地存储这个编号,而是通过让每个树节点存储节点的总数来隐式存储它.以该节点为根的子树.这样,要查找树中的第n个节点,您可以执行以下操作：
>如果n = 0,则返回根节点.
>否则,设置n = n – 1,然后从左到右依次循环当前节点的子节点,如下所示：
>设k是子树中的节点数.
>如果n< k,递归地找到该子树中的第n个节点.
>否则,设置n = n – k.
如果您有一个具有合理分支因子的相对平衡的树,则此方法运行得非常快,因为您可以快速丢弃不包含第n个元素的树的部分.
使用这种方法,您可以获得一个非常快速的方法(尽管不是O(1))从树中选择第n个元素：选择一个随机索引,然后返回该索引处的节点.此外,即使在树中添加或删除节点,这仍然有效.无论何时插入节点,只需增加从根到该节点的路径上所有节点的计数.每当删除节点时,减少路径上从根到删除节点的所有节点的计数.
但是,这种方法仍然使用O(n)开销来存储计数.对于以线性时间运行的O(1)-overhead算法,请查看@ NPE基于油藏采样的出色解决方案.
希望这可以帮助！
