java – 从树中选择随机节点

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

希望这可以帮助！