从二叉树中随机选择节点
我的树类:
public class BT<E>{
E value;
BT<E> left, right;
public BT(E value)
{
this.value=value;
}
public BT (E value, BT left, BT right)
{
this.value = value;
this.left = left;
this.right = right;
}
在生成树之后,我将如何从树返回随机节点?我知道我生成的每个树的深度和节点数。
解决方案
丹尼斯和杰伦的算法很容易实现,但是O(n)
。我相信我的O(log n)
算法稍微复杂一些。
每个节点都需要平等的被选中机会。因此,在某些树T
中,设LN(T)
为左树中的节点数,RN(T)
为右树中的节点数,N(T)
为总节点数,包括此节点(因此N(T) = 1 + LN(T) + RN(T)
)。从0 to N(T) - 1
中选择一个随机数R
。如果R == 0
,则返回此节点。如果1 <= R <= LT(N)
,则在左子树上递归此方法。否则,在右子树上递归此方法。
未经测试的代码(假设BT
有一个.size()
方法可以在O(1)
中使用):
public BT randomNode() {
int r = new Random().nextInt(this.size());
if (r == 0) {
return this;
} else if (left != null && 1 <= r && r <= left.size()) {
return left.randomNode();
} else {
return right.randomNode();
}
}
当然,您也可以将new Random()
从方法中提升出来,但算法是相同的。
编辑:修复了左子树为空时出现空指针异常的问题。
相关文章