在O(log n)时间内从二叉树中获取随机数

Question

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

我最初的想法是生成一个0,1或2的随机数.如果为0,则从当前节点取左路径,如果为1,则采用正确的路径,否则节点的值为随机值.如果您点击叶节点,请获取该节点的值.我不认为这会随机分发.

这是出于好奇,而不是针对特定的应用程序.

如果您需要任何澄清,请告诉我.

例如,如果你有树

     1
    / \
   2   5
       /
      3

调用时,数字1,2,3和5将统一返回 int get_random_number()

澄清:所有其他正常的BST操作应保持为O(log n),如insert(),delete()等.

Answer 1

您的想法不会创建随机分布.无论树的大小如何,根都有1/3的机会被挑选.

如果知道树中元素的数量,则生成1到N之间的数字k,并获得树的第k个最大元素.请参阅此处,了解在O(logn)中进行平衡树的方法.