StackOverflowError - добавление значения в кучу

Question

В настоящее время я работаю над апплетом, который отображает кучу при добавлении и удалении значений.Я реализую кучи в виде дерева целых чисел - IntTrees.Я пишу код для перекосов, а метод add доставляет мне некоторые проблемы.Метод add обычно работает, но время от времени он вызывает ошибку переполнения стека при добавлении значения, и я не могу понять, почему.

Вот код, который я написал для метода add

't' - это переменная экземпляра - сама куча.

 // adds value to heap
 public void add(int value) {

IntTree smallTree = new IntTree(value, empty(), empty());

 if (t == null) {
  t = smallTree;
 } else {
  t = merge(t, smallTree);
  }
}

public IntTree merge(IntTree left, IntTree right) {

if (isEmpty(left)) return right;
if (isEmpty(right)) return left;

int leftVal = left.value();
int rightVal = right.value();
IntTree result;

if (rightVal <= leftVal) {
  result = merge(right,left);
} else {
  result = left;

  if (result.isEmpty(left)) {
    result.setLeft(right);
  } else {
    IntTree temp = result.right();
    result.setRight(result.left());
    result.setLeft(merge(temp,right));
  }
}

    return result;
  } 

Есть ли в этом коде что-то, что могло бы вызвать ошибку переполнения стека, или это проблема, возможно, в другом месте программы?Спасибо!

Answer 1

@ Адам нашел проблему для вас.Это поможет вам самостоятельно найти подобные проблемы.

Когда вы получаете непредвиденную ошибку или исключение, важно тщательно изучить трассировку стека.Часто много информации в трассировке стека ... если вы знаете, как ее прочитать.

В этом случае вы бы увидели, что было много, много кадров стекадля метода merge.Если бы вы внимательно посмотрели на них, вы бы заметили, что merge звонит merge из одной и той же строки кода, снова и снова.Это классический признак цикла рекурсии.

Учитывая эти подсказки (и особенно номер строки, в которой происходила рекурсия), было бы просто выяснить, почему у вас был цикл рекурсии.

Answer 2

Взгляните на этот фрагмент

if (rightVal <= leftVal) {
  result = merge(right,left);

Что происходит, когда rightVal == leftVal?