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

Question

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

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

这是出于好奇，并非针对特定应用。

如果您需要任何说明，请告诉我。

一个例子是如果你有树

     1
    / \
   2   5
       /
      3

调用int get_random_number()时统一返回1、2、3、5数

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

Answer 1

您的想法不会产生随机分布。无论树的大小，根都有 1/3 的机会被采摘。

如果知道树中元素的个数，生成一个1到N之间的数k，得到树中第k大的元素。参见 here寻找一种在 O(logn) 中为平衡树做到这一点的方法。