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

Это может выдать java .lang.IndexOutOfBoundsException, если при выполнении trv.get(0) arraylist trv размер равен 0.

Во избежание этого вы можете проверить, что если размер trv равен не 0, тогда вы можете вернуть первый элемент этого списка, иначе вернуть нулевое значение внутри findMin function

Вот обновленный код:

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

As, улучшение вместо возврата 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 (tmp != null) return tmp; Используется для печати возвращаемое значение, поскольку мы не используем структуру данных типа arraylist в исходном коде для хранения результата, поэтому, как только мы получим результат из findMin рекурсивного вызова, который не равен нулю, мы возвращаем it.

if (!t.deleted) return t; Это используется по той же причине, что и ваш код, как if(!t.deleted) {trv.add(t)}, т.е. мы проверяем, вернул ли findMin (слева) null и не является ли его узел root удалите, затем верните этот узел, так как он будет меньше, чем этот root правый дочерний узел, и, следовательно, нет необходимости проверять его дальше.

Но, if (tmp != null) return tmp; не используется, так как в любом случае каждый раз мы будем go на if (!t.deleted) return t; и оттуда также может быть возвращен результат. Так что first if можно удалить.