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

Question

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

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

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

如果您需要任何澄清，请告诉我。

一个例子是如果你有树

     1
    / \
   2   5
       /
      3

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

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

Answer 1

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

如果你知道树中元素的数量，生成一个介于 1 和 N 之间的数字 k，并得到树中第 k 个最大的元素。有关平衡树的 O(logn) 方法，请参见此处。