在O（log n）时间从二叉树获取随机数 [英] Getting a random number from a binary tree in O(log n) time

问题描述

是否有可能在O（log n）时间从平衡的二进制搜索树中获得均匀分布的随机值（调用该函数意味着它同样有可能在树中获得任何值）？

Is it possible to get a uniformly distributed random value (calling the function means it's equally likely to get any value in the tree) from a balanced binary search tree in O(log n) time?

我最初的想法是生成一个随机数0、1或2。如果为0，则取当前节点的左路径；如果为1，则取右路径，否则为该节点的值。是随机值。如果您命中一个叶节点，则取该节点的值。我不认为这会是随机分布的。

My initial idea was to generate a random number 0, 1, or 2. If 0, take the left path from the current node, if 1, take the right path, otherwise the value of the node is the random value. If you hit a leaf node, take the value of that node. I don't think this would be randomly distributed though.

这是出于好奇，不是针对特定的应用程序。

This is out of curiosity, not for a specific application.

让我知道您是否需要任何澄清。

Let me know if you need any clarifications.

例如，您是否有树

     1
    / \
   2   5
       /
      3

在调用 int get_random_number（）时，数字1、2、3和5将统一返回。

说明：所有其他常规BST操作都应保持O（log n），例如insert（），delete（）等。

Clarification: All other normal BST operations should remain O(log n), like insert(), delete(), etc.

推荐答案

您的想法不会创建随机分布。不论树的大小如何，根部都有1/3的机会被拾取。

Your idea will not create a random distribution. The root has a 1/3 chance of being picked no matter the size of the tree.

如果您知道树中元素的数量，则在1和N，得到树的第k个最大元素。请参见此处为平衡树在O（logn）中执行此操作的方法。

If you know the number of elements in the tree, generate a number k between 1 and N, and get the kth largest element of the tree. See here for a way to do that in O(logn) for balanced trees.

这篇关于在O（log n）时间从二叉树获取随机数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！