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);
             }
     }

作为一种改进，您可以返回void，而不是从findMin函数返回BinaryNode<AnyType>，因为无论如何，您的结果都存储在trv arrylist中，而不是每次在findMin函数内检查return trv.size()==0 ? null :trv.get(0);(这将在每次递归调用中检查(，您只能在助手函数内检查一次。

这里是更新的优化代码：

  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 (tmp != null) return tmp;这是用于打印返回值的，因为我们在原始代码中没有使用arraylist类型的数据结构来存储结果，所以一旦我们从findMin递归调用中得到不为null的结果，我们就会返回它。

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

但是，if (tmp != null) return tmp;没有用，因为无论如何，每次我们都会去CCD_ 16，并由此返回结果。所以这个first if可以被移除。