OutOfMemoryError: пространство кучи Java Добавление отсортированных элементов в массив двоичного дерева поиска - PullRequest
Новая
       3

OutOfMemoryError: пространство кучи Java Добавление отсортированных элементов в массив двоичного дерева поиска

0 голосов
/ 05 декабря 2011

Я получаю OutOfMemoryError: пространство кучи Java, добавляющее массив отсортированных элементов к реализации массива двоичного дерева поиска.Я могу добавить массивы случайных целых чисел, но когда я пытаюсь добавить отсортированный массив, я сталкиваюсь с этой проблемой.Корень дерева устанавливается на самый маленький или самый большой элемент отсортированного массива, поэтому, когда вы добавляете остальные элементы, я получаю чрезвычайно несбалансированное дерево, которое пожирает мою память.Любая помощь в этом очень ценится.

Исключение в потоке "main" java.lang.OutOfMemoryError: Пространство кучи Java в bst.ArrayBinarySearchTree.resize (ArrayBinarySearchTree.java:386) в bst.ArrayBinarySearchTree.addEjear:Tech.reedinaryj (26) ArrayBinaryв bst.Experiment.main (Experiment.java:90) 

    public void addElement(T element) {
    if(isEmpty()){
    count++;
    array[1] = element;
    }else{

         int current = 1;
         boolean added = false;

         while (!added) {
             if(current > (array.length-(array.length*.9))){
                    resize();
                }
            if (element.compareTo(array[current]) < 0){
               if (array[current*2] == null) {
                  array[current*2]=element;
                  added = true;
               } else
                  current = current*2;
            } else{
               if (array[current*2+1] == null) {
                  array[current*2+1]=element;
                  added = true;
               } else
                  current = current*2+1;
            }
         } //while
    }
    count++;
}

    private void resize(){
    T[] temp = (T[])(new Comparable[2*array.length-(array.length/4)]);
    for(int i=0; i<array.length; i++)
        temp[i] = array[i];
    array = temp;
}

1 Ответ

0 голосов
/ 05 декабря 2011

хорошо, вы получите несбалансированное дерево, если у вас нет балансировки в вашем дереве, например AVL или красных черных деревьев. Если вы просто строите бинарное дерево поиска без балансировки, возможно, вы получите исключение нехватки памяти.

Я бы порекомендовал вам попробовать это с меньшим массивом, чтобы увидеть, если вы все еще получаете исключение вне памяти. если да, у вас есть недостаток в вашем коде.

У меня есть дерево двоичного поиска в c # , взгляните на него. Обычно вы хотите использовать узлы вместо массива для представления двоичного дерева поиска. Насколько я вижу, вы используете метод, который обычно используется для структуры данных кучи для сортировки кучи .

...