PhD*_*PhD 2 algorithm traversal probability binary-search-tree
给定一个 BST（可能平衡也可能不平衡），如何随机均匀地返回“任何”节点？一个限制是您不能使用外部索引数据结构。您必须以每个节点被访问的机会均等的方式遍历树。
这个问题让我困惑了好久。如果我们确实可以使用外部哈希表/指针，我们可以对它们进行随机化并返回相应的节点。但是，我的同事提出了一个相当复杂的问题变体，其中不能使用额外的数据结构。
d并遍历大多数d节点以返回节点（如果它是叶子则停止）也不会生成均匀分布。更新：您也不能进行中序遍历并将结果存储在数组中。
如何实现这样的遍历？
以任何顺序遍历树，保持以下值：
N：看到的节点数
selected: 当前选中的节点。
最初，N是 0 并且selected是None。访问节点包括以下内容：
增量 N
生成范围内的随机整数[0, N)。
如果选择的随机整数为 0，则设置selected为当前节点。
请注意，值N和selected需要在步行过程中进行修改。这意味着它们都是访问者函数的输入和输出值。
在步行结束时，N将是树中的节点数，并将selected是以均匀概率选择的随机节点（假设您有一个好的随机数生成器）。
该算法不限于 BST。它适用于任何形状的任何树。特别是，将工作在一个简单的线性未知长度的对象的序列，对应于公知的随机选择算法，该算法是迭代的对象，与所述新的被访问一个与概率替换所选择的随机对象1/N，其中N是数迄今为止看到的对象。
如果您跟踪访问过的节点，它也适用于任何连接图。
如果您有一个非常大的树（或图），可能分布在许多服务器和/或存储设备上，您可以使用此算法的不同表示，它提供一定程度的并行性（并且还防止需要保持全局步行结构或将值传递到步行中）。
我们假设每个节点服务器都可以直接访问k对象并间接访问一些已知数量的子服务器。该算法允许冗余子节点，但假设网络通信（几乎）完美；处理网络分裂超出了本答案的范围。我们还假设每个查询都有一个关联的唯一查询编号，这允许我们处理一些网络工件。查询没有其他信息（除了要响应的服务器），并期望返回一个由计数和随机选择的节点组成的元组。
当节点服务器收到带有 id 的查询时q，它会执行以下操作：
如果它以前响应过查询q，则立即返回<0, null>
设置count到k和selected到随机选择的对象从k对象它具有直接访问。
对于每个子服务器，发送查询（使用相同的查询 ID）
对于返回的每个响应（响应的顺序无关紧要）：
一种。添加response.count到count
湾 随着概率response.count / count，替换selected为response.selected
当所有子服务器都响应后，返回 <count, selected>