给定一个 BST（可能平衡也可能不平衡），如何能够均匀地随机返回“任何”节点？一个限制是您不能使用外部索引数据结构。您必须以每个节点都有平等被访问的机会的方式遍历树。
这个问题让我困惑了好一阵子。如果我们确实可以使用外部哈希表/指针，我们可以对它们进行随机化并返回相应的节点。然而，我的同事提出了这个问题的一个相当复杂的变体，其中不能使用额外的数据结构。
- 具有 50-50 概率进入 L/R 的简单随机游走不起作用，因为返回靠近树底部的节点的概率要小得多（概率复合）
- 甚至随机生成深度
d并且最多遍历d节点返回节点（如果是叶子则停止）不会生成均匀分布。
Update：您也不能进行中序遍历并将结果存储在数组中。
如何才能实现这样的穿越呢？
以任意顺序遍历树，并保留以下值：
N：看到的节点数
selected：当前选择的节点。
最初，N是 0 并且selected is None。访问节点包括以下内容：
增量N
生成范围内的随机整数[0, N).
如果选择的随机整数为0，则设置selected到当前节点。
请注意这些值N and selected需要在行走过程中进行修改。这意味着它们都是访问者函数的输入值和输出值。
步行结束时，N将是树中的节点数，并且selected将是以均匀概率选择的随机节点（假设您有一个好的随机数生成器）。
该算法不限于 BST。它适用于任何形状的任何树。特别是，它将处理未知长度的简单线性对象序列，对应于众所周知的随机选择算法，即迭代对象，以概率用新访问的对象替换所选的随机对象1/N where N是迄今为止看到的物体数量。
如果您跟踪访问过的节点，它也适用于任何连通图。
如果您有一个非常大的树（或图），可能分布在许多服务器和/或存储设备上，您可以使用此算法的不同表示形式，这提供了一定程度的并行性（并且还避免了需要保持全局步行结构或将值传递到步行中）。
我们假设每个节点服务器都可以直接访问k对象和间接访问某些已知数量的子服务器。该算法允许冗余子节点，但假设网络通信（几乎）完美；处理网络分裂超出了本答案的范围。我们还假设每个查询都有一个关联的唯一查询号，这使我们能够处理一些网络工件。该查询没有其他信息（除了要响应的服务器之外），并且预计返回一个由计数和随机选择的节点组成的元组。
当节点服务器收到带有 id 的查询时q，它执行以下操作：
如果它之前已响应过查询q，立即返回<0, null>
Set count to k and selected到一个随机选择的对象k它可以直接访问的对象。
对于每个子服务器，发送查询（具有相同的查询 ID）
-
对于返回的每个响应（响应的顺序并不重要）：
a. Add response.count to count
b.有概率response.count / count， 代替selected with response.selected
当所有子服务器响应后，返回<count, selected>
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
