从二叉树中随机选择节点

2022-03-13 00:00:00 binary-tree java

我的树类:

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()从方法中提升出来,但算法是相同的。

编辑:修复了左子树为空时出现空指针异常的问题。

相关文章