java - findMin惰性删除二进制搜索树

我在针对二进制搜索树的延迟删除中找到了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);
             }

最佳答案

如果执行trv.get(0) arraylist 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，您可以返回void，因为无论如何您的结果都存储在trv列表中，而不是每次都在return trv.size()==0 ? null :trv.get(0);函数中检查findMin（将针对每个递归调用），则您只能在he​​lper函数中检查一次。

这是更新的优化代码：

  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;这用于打印返回的值，因为我们没有在原始代码中使用arraylist类型的数据结构来存储结果，因此只要我们从findMin递归调用（不为null）获得结果，就将其返回。

if (!t.deleted) return t;出于与代码在if(!t.deleted) {trv.add(t)}中所使用的原因相同的原因使用。我们正在检查findMin（left）是否返回了null，并且如果其根节点未被删除，则返回该节点，因为它将小于此根节点right的子节点，因此无需进一步检查。

但是，由于每次我们都会去if (tmp != null) return tmp;
if (!t.deleted) return t;，从那里也可以返回结果。因此可以删除此first if。