findMin惰性删除二叉树

Question

我在二叉树的懒惰删除中找到了findMIn方法的代码。首先，这个方法正确吗？如果是的话，有人能给我解释一下吗？

private BinaryNode<AnyType> findMin( BinaryNode<AnyType> t )
{
if (t == null) return null;

BinaryNode<E> tmp= findMin(t.left); // get minimum from the left node

if (tmp != null) return tmp; // if mimimum is not null return minimmum

if (!t.deleted) return t; // if minimum is null in left node and t is not deleted
// return t then

return findMin(t.right); // if t is deleted and minimum of left node of t is null, then search in right side

}

我重写了它以包含以下内容，但它不起作用。

 private BinaryNode<AnyType> findMin( BinaryNode<AnyType> t)

      {
      ArrayList<BinaryNode<AnyType>> trv = new ArrayList<BinaryNode<AnyType>>();

         return findMinVal(t, trv);
      }
private BinaryNode<AnyType> findMin( BinaryNode<AnyType> t, ArrayList<BinaryNode<AnyType>> trv )

     {
             if(t == null) {
                 return t;
             } else {
                 BinaryNode<AnyType> left= findMin(t.left);
                 if(!t.deleted) {
                     trv.add(t);
                 }
                 BinaryNode<AnyType> right= findMin(t.right);

                 return trv.get(0);
             }

Answer 1

如果在执行trv.get(0)数组列表时trv大小为0，则可能抛出java.lang.IndexOutOfBoundsException。

为了避免它，你可以检查如果trv的大小不是0，那么你可以返回这个列表的第一个元素，否则在findMin函数中返回null

以下是更新后的代码：

private BinaryNode<AnyType> findMin( BinaryNode<AnyType> t, ArrayList<BinaryNode<AnyType>> trv )

     {
             if(t == null) {
                 return t;
             } else {
                 BinaryNode<AnyType> left= findMin(t.left);
                 if(!t.deleted) {
                     trv.add(t);
                 }
                 BinaryNode<AnyType> right= findMin(t.right);

                 return trv.size()==0 ? null :trv.get(0);
             }
     }

作为一个改进，你可以返回BinaryNode<AnyType>，而不是从findMin函数返回BinaryNode<AnyType>，因为你的结果被存储在trv数组列表中，而不是每次在findMin函数中检查return trv.size()==0 ? null :trv.get(0); (这将在每个递归调用中检查)，你只能在helper函数中检查一次。

以下是更新后的优化代码：

  private BinaryNode<AnyType> findMin( BinaryNode<AnyType> t)

      {
      ArrayList<BinaryNode<AnyType>> trv = new ArrayList<BinaryNode<AnyType>>();

         findMinVal(t, trv);
         return trv.size()==0 ? null :trv.get(0);
      }

private BinaryNode<AnyType> findMin( BinaryNode<AnyType> t, ArrayList<BinaryNode<AnyType>> trv )

     {
             if(t!=null) {
                 findMin(t.left);
                 if(!t.deleted) {
                     trv.add(t);
                 }
                 findMin(t.right);
             }
}

在上面的原始代码中，有两个if条件：

它用于打印返回值，因为我们在原始代码中没有使用数组列表这种数据结构来存储结果，所以只要我们从非if (tmp != null) return tmp;的findMin递归调用中获得结果，我们就返回它。

if (!t.deleted) return t;使用它的原因与您的代码使用if(!t.deleted) {trv.add(t)}的原因相同，即我们检查findMin(左)是否返回null，如果它的根节点没有被删除，则返回该节点，因为它将比这个根节点小右子节点，因此不需要进一步检查。

但是，没有使用if (tmp != null) return tmp;，因为我们每次都会转到if (!t.deleted) return t;，并且从那里也可以返回结果。因此可以删除此first if。