是否有可能在 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() 等。
你的想法不会产生随机分布。无论树的大小，根都有 1/3 的机会被采摘。
如果知道树中元素的数量，则生成一个介于 1 和 N 之间的数字 k，并获取树中第 k 个最大的元素。看here https://stackoverflow.com/questions/2329171/find-kth-smallest-element-in-a-binary-search-tree-in-optimum-way/2329236#2329236一种在 O(logn) 中实现平衡树的方法。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
