为什么在算法中使用子树大小来选择二叉树中的随机节点？

我偶然发现了从二叉树中选择随机节点的算法的几种实现，它们都使用子树大小属性。但是，我不明白为什么知道子树大小有帮助。这是实现A https://stackoverflow.com/a/32011526 and B https://www.geeksforgeeks.org/select-random-node-tree-equal-probability/.

总体思路可以用这个伪代码来描述：

Node getRandomNode() {
    Random seed = new Random;
    int random = random.nextInt(this.size);

    if (this.left.size == random)
        return this;
  
    if (this.left.size > random) {
        return this.left.getRandomNode();
    } else {
        return this.right.getRandomNode();
    }
}

我假设getRandomNode()方法总是在树的根部调用。

据我所知，选择节点的随机性仅取决于random整数。在某些情况下如果random然后重演getRandomNode()将返回相同的节点。

我也不明白该算法如何在完整的二叉树中工作。每个节点子树的大小始终是偶数。因此，如果random是一个偶数，算法将不会在这一行匹配：

if (this.left.size == random)
        return this;

并且只会产生一个随机数，如果random是偶数，这意味着该算法不是随机的。

我错过了什么吗？

如果我必须实现该算法，我只需存储一个附加链表，其中每个节点都有一个索引（例如ArrayList在Java中），然后从列表中返回其索引等于从返回的随机数的节点random.nextInt().

感谢您在这里概述了您的思维过程。让我们一步一步地回顾一下您在这里所说的内容。

我假设getRandomNode()方法总是在树的根部调用。

它总是在根上被调用some子树，但它不一定是整个树的根。例如，考虑这个简单的树：

                  A
                 / \
                B   C
                   / \
                  D   E

在这里，第一个电话将是A.getRandomNode()，它将从以 A 为根的子树中选择一个随机节点。之后，我们有 1/5 的机会从左子树中请求随机节点，有 3/5 的机会我们从左子树中请求随机节点右子树的，并且我们停止并返回 A 的机会为 1/5。为了论证，假设这里生成的随机数是 4，并且我们决定在右子树中查找。这意味着下一个电话是C.getRandomNode()，它要求从这棵树中随机选择一个节点：

             C
            / \
           D   E

在这里，我们将生成一个随机数，其中有 1/3 的机会从左子树请求随机节点，有 1/3 的机会从右子树请求随机节点，还有 1/3 的机会从左子树请求随机节点。以 C 停止。为了论证，假设我们生成随机数 0 并向左走。这叫D.getRandomNode()，它要求该子树中的一个随机节点：

               D

这个调用总会返回D，因为这是唯一的选择。

希望这能让您对算法的工作原理有更多的了解。在每个时间点，我们希望有平等的机会选择任何元素。因此，我们决定是停止、向左还是向右，根据每个选项中的节点数量来衡量我们的选择。

据我所知，选择节点的随机性仅取决于随机整数的随机性。在某些情况下，如果随机重复的话getRandomNode()将返回相同的节点。

你是对的，这里随机性的唯一来源是选择哪个随机整数。这是有道理的，因为树本身不是随机的。

话虽这么说，您在此处展示的实现会在沿着树向下走的每个步骤中进行单独的随机计算。因此，多个不同的随机选择都必须走同样的路，才能得到与结果相同的节点。

我也不明白该算法如何在完整的二叉树中工作。每个节点子树的大小始终是偶数。因此，如果 random 是偶数，则算法将不会在这一行匹配：

if (this.left.size == random)
     return this;

如果 random 是偶数，则只会产生随机数，这意味着该算法不是随机的。

你是对的，如果我们只是生成一个随机数并在整个过程中使用该数字，那么是的，你会遇到这样的麻烦。然而，这并不是算法的工作原理。相反，每次我们递归调用getRandomNode()，我们选择一个新的随机数并用它来进行路由。因此，无论我们选择的第一个数字是偶数还是奇数，我们最终都会到达唯一选择是返回当前节点的位置，此时我们将返回一些内容。

如果我必须实现该算法，我只需存储一个附加链表，其中每个节点都有一个索引（例如ArrayList在Java中），然后从列表中返回其索引等于从返回的随机数的节点random.nextInt().

这样你绝对可以解决问题。如果您正在使用的树永远不会改变 - 没有添加或删除任何内容 - 那么这是一个完全合理的策略。

标记子树大小的方法很有用的原因是，即使添加或删除节点，它也可以让您从树中随机采样。具体来说，您可以相当快速地调整存储在每个节点中的数字，以响应节点的插入或删除，这比必须在节点中重建或打乱元素要快得多。ArrayList是树改变形状。查看顺序统计树 https://en.wikipedia.org/wiki/Order_statistic_tree有关如何执行此操作的更多详细信息。