java – 从树中选择随机节点

前端之家收集整理的这篇文章主要介绍了java – 从树中选择随机节点前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

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

最佳答案
这是一个可能有用的观察:假设您以某种方式对树中的所有节点进行编号,这样就可以有效地查找某个任意n的第n个树节点.如果您可以这样做,那么您可以通过选择随机节点编号,然后转到该节点来有效地选择随机节点.

一种非常简单的方法是执行树的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基于油藏采样的出色解决方案.

希望这可以帮助!

原文链接:https://www.f2er.com/java/438298.html

猜你在找的Java相关文章