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

Question

我偶然发现了几种从二叉树中 select 随机节点的算法实现，它们都使用子树大小属性。但是，我不明白为什么知道子树的大小会有帮助。这是实现 and B.

大致的思路可以用这个伪代码来描述：

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() 将 return 相同的节点。

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

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

并且仅当 random 为偶数时才会产生随机数，这意味着该算法不是随机的。

我是不是漏掉了什么？

如果我必须实现该算法，我将只存储一个额外的链表，其中每个节点都有一个索引（如 Java 中的 ArrayList），然后 return 节点来自索引等于随机数的列表 return 来自 random.nextInt().

Answer 1

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

I assume that the getRandomNode() method is always called on the root of the tree.

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

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

             C
            / \
           D   E

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

此调用将始终 return D，因为这是唯一的选择。

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

As far as I see the randomality of choosing a node depends solely on the randomality of random integer. In certain cases if random repeats itself then getRandomNode() will return the same node.

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

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

Also I don't understand how the algorithm can work in a complete binary tree. The size of each node subtree will always be an even number. So if random is an even number the algorithm will not have a match on this line:
if (this.left.size == random)
     return this;
and will only produce a random number if random is an even number, which means that the algorithm is not random.

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

If I had to implement the algorithm I would just store an additional linked list where each node would have an index (like ArrayList in Java) and then return the node from the list whose index equals a random number returned from random.nextInt().

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

标记子树大小的方法之所以有用，是因为它允许您从树中随机采样，即使正在添加或删除节点也是如此。具体来说，您可以相当快速地调整存储在每个节点中的数字以响应节点的插入或删除，这比必须在 ArrayList 中重建或随机排列元素要快得多，因为树要改变形状。查看 order statistic tree 了解有关如何执行此操作的更多详细信息。

Answer 2

如果您愿意，可以将树转换为 array/linked 列表。生成一个随机数并获取存储在该索引处的元素。但是转换树也需要额外的 O(N) 步骤。
现在，来到子树大小方法。该算法也在递归地做同样的事情：将一个值映射到每个节点值（类似于数组中的索引）。映射基本变成了

0 -> root node
1 - left_subtree_size -> for all left subtree nodes
left_subtree_size+1 - right_subtree_size -> for all right subtree nodes

由于每个节点仅映射到一个值，因此每个节点被选中的机会均等（显然，假设所有值在 random() 函数下具有相同的概率）。

Answer 3

经过一些小的清理后，该算法巧妙而优雅地使用了条件概率。条件概率表示，如果某个事件 A 在另一个事件 B 的发生上是 contingent/conditional，那么 P{A} = P{A | B} * P{B} — 换句话说，A 的概率是等于 A 给定 B 发生的概率乘以 B 发生的概率。如果 B 本身取决于 C，这可以级联到 P{A} = P{A | B} * P{B} = P{A | B} * P{B | C} * P{C}，依此类推。你最终乘以所有条件的所有概率，使你达到最终状态。

问题中的算法给了我们一个阶段的条件概率，但是通过一个具体的例子跟踪它最容易看出它是如何选择等概率随机树节点的。我有一个具体的实现如下。由于您没有指定语言标签，我选择使用 Ruby。（注意：这并不是为了让 Ruby 纯粹主义者的心去拍拍，而是为了让非 Ruby 主义者可读，是独立的和可执行的，并说明条件概率的工作原理。）

首先，让我们介绍一个跟踪子树大小的二叉搜索树节点：

class BT_node
  # Make the following instance vars read-only accessible by name
  attr_reader :value, :left, :right, :size

  # Instantiate a new BT_node to hold the assigned value
  def initialize(value)
    @value = value
    # new values become leaves (see below), so both children are nil.
    @left = nil
    @right = nil
    # Assumption: size is the number of BT_node's in the subtree rooted
    # at, including, the current BT_node.  Starts at 1 since all newly
    # added nodes are leaves.
    @size = 1
  end

  def add_value(new_value)
    # Note: not checking, but this assumes all entries are unique.  In other
    # words, at each point a new_value belongs in either the left or right
    # subtree of the current node, it's never equal to an existing node's
    # value, so all new_value's become leaves in the tree when inserted.
    if new_value < @value
      if @left
        @left.add_value(new_value)
      else
        @left = BT_node.new(new_value)
      end
    else
      if @right
        @right.add_value(new_value)
      else
        @right = BT_node.new(new_value)
      end
    end
    @size += 1
  end

  # In-order traversal and printing of tree
  def treeprint
    @left.treeprint if @left
    puts "#{@value}, #{@size}"
    @right.treeprint if @right
  end

  # Working implementation of the random node picker.  Note how I carefully
  # prevented spell-check from changing that to nose.
  def random_pick
    rnd_value = rand(@size)
    lsize = @left ? @left.size : 0  # left.size if left exists, 0 otherwise
    return @value if rnd_value == lsize     # probability is 1/@size
    if rnd_value < lsize                    # probability is lsize/(@size-1)
      return @left.random_pick
    else                            # probability is right.size/(size-1)
      return @right.random_pick
    end
  end
end

我添加了评论来澄清我所做的假设。如果您了解二叉搜索树，我希望设置相当明显，所以让我们关注 random_pick。鉴于我们在树中的特定节点，通过构造 @size 将告诉您当前子树（包括它本身）中有多少个节点。然后，我们在 [0,...,@size-1] 范围内统一生成一个数字，包括端值，因此每个值都可以以 1/@size 的概率出现。现在是稍微奇怪但数学上正确的部分。（如果这部分让您感到困扰，请参阅最后的替代实现。）我们将生成的 rnd_value 与左子树的大小（如果存在）进行比较，如果没有左子树，则为零。无论哪种方式，都有 1/@size 匹配的机会，在这种情况下我们 return 当前节点的值。如果我们不匹配，我们最终会选择此子树中剩余的 @size - 1 个值之一。在[0,...,lsize-1]范围内有lsize个值，所以我们的命运在左子树的概率为lsize/(@size-1)，或者在右子树的剩余概率为(@size-1-lsize)/(@size-1)。

这是递归的单个级别的快照，但让我们使用条件概率来了解全貌。这是最容易通过具体示例进行跟踪的。考虑使用以下命令序列构造的特定二叉树：

root = BT_node.new(3)
root.add_value(1)
root.add_value(2)
root.add_value(7)
root.add_value(5)
root.add_value(4)
root.add_value(6)
root.add_value(8)

add_value 的序列生成以下树，其中条目的形式为“value:size”：

        3:8
      /     \
   1:2       7:5
     \      /   \
     2:1  5:3   8:1
         /   \
       4:1   6:1

让我们从简单开始，并询问 random_pick 如何产生 3。我们从根开始，并生成 [0,...,7] 范围内的 8 个值之一。如果它恰好是 2，即根的左子树的大小，我们就完成了。这种情况发生的概率为 1/8。如果您没有选择根，则还有 7 个节点需要考虑，其中 2 个在左子树中，5 个在右子树中。你以 2/7 的概率选择左边，以 5/7 的概率选择右边，给所有剩余的节点一个平等的机会。

现在让我们看一个更难的问题，我们将不得不调用条件概率。 random_pick 将如何产生 5？要选择一个 5，我们将从根开始，如果选择失败，转到它的右子树，选择 7 失败，转到它的左子树，然后选择 5。每个阶段的概率如下：

未能选择 3: 7/8
转到右子树：5/7
未能选择 7: 4/5
转到左子树：3/4
选5：1/3

条件概率告诉我们得到 5 的概率是沿着这条偶然路径的所有概率的乘积：(7/8)*(5/7)*(4/5)*(3/4)*(1/3) = 1/8。注意每一项的分子如何被下一项的分母抵消。

选择树中的任何其他节点，按照相同的条件逻辑，您会发现概率都是 1/8。如您所见，树不必是平衡的，条件概率保证树中的每个节点都有相同的机会被选中。

这是程序的其余部分，它确认采样在一百万次试验中是均匀的。

# # Confirmation of tree - uncomment to inspect tree structure
# p root
# root.treeprint

# # For analysis in a stats package
# 1_000_000.times { puts root.random_pick }

# For analysis by eye - Expected count for each value is 125000
h = Hash.new(0)  # default value set to zero for all keys
# Accumulate how many times we pick each value over 1 million picks
1_000_000.times { h[root.random_pick] += 1 }
p h  # inspect the hash

# Produces, e.g.:
#
# {4=>124824, 2=>125312, 8=>125298, 5=>124593, 6=>124562, 1=>125272, 7=>124857, 3=>125282}
#

我在结果可能性相同的原假设下计算了该样本的卡方统计量。具有 7 个自由度的卡方的预期值为 7，与预期的较大偏差将增加统计量并导致拒绝原假设。由于我的检验统计量是 5.9886，我们完全无法拒绝原假设，即该算法有相同的可能性生成树中的每个值。

如果实在不方便比较rnd_value和左子树的大小，可以在rnd_value == 0时选择当前节点。然后，您必须将比较调整为小于或等于而不是小于，以获得选择左子树的正确概率。如果您有兴趣，请看这里：

# Alternate version if you don't like basing choice of self on left.size
def random_pick
  rnd_value = rand(@size)
  return @value if rnd_value == 0
  lsize = @left ? @left.size : 0
  if rnd_value <= lsize
    return @left.random_pick
  else
    return @right.random_pick
  end
end

最后，如果您想要实际节点而不是存储的值，请在任一版本的 random_pick 中将 return @value 更改为 return self。

Answer 4

使水库采样（Knuths“算法 R”）适应树搜索。您不需要事先知道树的大小或子树的大小。（但是，不幸的是，您必须访问每个节点...）

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct node{
        struct node *left, *right;
        unsigned value;
        };

unsigned urand(unsigned lim)
{
unsigned rnd;

rnd = random();
rnd %= lim; // Biased!

return rnd;
}

struct node *tree_sample(struct node *tree, struct node *samp, unsigned *counter)
{
unsigned rnd;

if (!tree) return samp;

*counter += 1;
if (*counter== 1) { samp = tree; }
else    {
        rnd = urand(*counter);
        if (rnd==0) {samp=tree;}
        }

samp = tree_sample(tree->left, samp, counter);
samp = tree_sample(tree->right, samp, counter);

return samp;
}

struct node *node_new(unsigned value)
{
struct node *this;

this = malloc(sizeof *this);
this->left = NULL;
this->right = NULL;
this->value = value;

return this;
}

struct node **tree_find(struct node **tree, unsigned value)
{
while (*tree) {
        int cmp;
        cmp = value - (*tree)->value;
        if (!cmp) break;
        tree = (cmp < 0) ? &(*tree)->left : &(*tree)->right;
        }
return tree;
}

struct node *root = NULL;

int main(void)
{
unsigned count;
struct node *this;

        // Create some noise ...
for (count = 0; count < 10; count++) {
        struct node **pp;
        this = node_new(random());
        pp = tree_find(&root, this->value);
        *pp = this;
        }

srand(time(NULL));
count = 0;

        // pick a sample
this = tree_sample (root, NULL, &count);
printf("Count=%u\n", count);
if (this) printf("Val=%u\n", this->value);

return 0;
}

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

Why subtree size is used in algorithm to select random node in a binary tree?

random

algorithm

tree

binary-tree