在 O(logn) 中打印二叉树中的随机元素

Question

给定一个二叉树 TreeNode 比如：

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
    int size;
}

其中size为（左子树+右子树+1）的节点数。

Print a random element from the tree in O(logn) running time.

注意：这个post不同于this，因为它清楚地提到我们有一个size与每个此问题中的节点。

PS：post 的灵感来自 this。

Answer 1

有一种简单的方法，复杂度为 O(n)。

生成1到root.size范围内的随机数
进行BFS or DFS遍历
在 random numbered 元素处停止迭代并打印它。

为了提高复杂性，我们需要在每次迭代时创建自己的分支顺序，而不是像 BFS 和 DFS 那样按顺序进行。我们可以通过每个节点的size属性来决定是遍历左sub-tree还是右sub-tree。方法如下：

生成1到root.size范围内的随机数（比如r）
从根节点开始遍历，决定是向左sub-tree、right-subtree还是打印root：
- 如果r <= root.left.size，向左遍历sub-tree
- 如果r == root.left.size + 1，打印根（我们已经找到要打印的随机节点）
- 如果r > root.left.size + 1，向右遍历sub-tree
本质上，我们定义了一个顺序，其中当前节点的排序为（当前左子树的大小）+ 1。
由于我们在每次迭代时消除了向左或向右遍历sub-tree，因此其运行时间为O(logn)。

pseudo-code 看起来像这样：

traverse(root, random)
  if r == root.left.size + 1
    print root        
  else if r > root.left.size + 1
    traverse(root.right, random - root.left.size - 1)
  else
    traverse(root.left, random)

以下是 java 中的实现：

public static void printRandom(TreeNode n, int randomNum) {
    int leftSize = n.left == null ? 0 : n.left.size;
    if (randomNum == leftSize + 1)
        System.out.println(n.data);
    else if (randomNum > leftSize + 1)
        printRandom(n.right, randomNum - (leftSize + 1));
    else
        printRandom(n.left, randomNum);
}

Answer 2

使用尺寸！

在 0 和 n 之间选择一个随机数 q。从根开始。如果left->size == q return 当前节点值。如果 left->size < q 向右走，否则你向左走。如果你向右减去 q -= left->size + 1。重复直到输出一个节点。

这给你o（树的高度）。如果树是平衡的，你会得到 O(LogN)。

如果树不平衡但你仍然想保持 O(logN) 你可以做同样的事情但限制最大迭代次数。请注意，在这种情况下，并非所有节点都具有相同的 returned 概率。

Answer 3

是的，使用尺寸！

正如索林所说，在0和n - 1之间选择一个随机数i（不是n）

然后执行以下指令：

Treenode rand_node = select(root, i);

其中 select 可以如下所示：

TreeNode select_rec(TreeNode r, int i) noexcept
{ 
  if (i == r.left.size) 
    return r;

  if (i < r.left.size) 
    return select_rec(r.left, i);

  return select_rec(r.right, i - r.left.size - 1);
}

现在一个非常重要的技巧：空节点必须是大小设置为 0 的哨兵节点，这是有意义的，因为空树有零个节点。您可以避免使用哨兵，但是 select() 操作稍微复杂一些。

如果树是平衡的，那么select()是O(log n)

在 O(logn) 中打印二叉树中的随机元素

Print random element from binary tree in O(logn)

java

random

algorithm

binary-tree