java - 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) 时，这可能会抛出 java.lang.IndexOutOfBoundsException数组列表trv大小为 0。

为了避免这种情况，您可以检查大小是否为 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 中arrylist 而不是每次都检查 return trv.size()==0 ? null :trv.get(0);里面findMin函数(每个递归调用都会检查一次)，您只能在辅助函数内检查一次。

这里是更新的优化代码:

  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 获得结果，递归调用不为空，我们将返回它。

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

但是，if (tmp != null) return tmp; 没有任何用处。因为无论如何每次我们都会去 if (!t.deleted) return t;也可以从那里返回结果。所以这个first if可以删除。