с учетом упорядоченной последовательности целых чисел написать алгоритм для построения двоичного дерева поиска с идеальной топологией? - PullRequest
Новая
       16

с учетом упорядоченной последовательности целых чисел написать алгоритм для построения двоичного дерева поиска с идеальной топологией?

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

Хорошо, это выглядит лучше, но дает исключение нулевого указателя?

публичная статическая BST idealTop (Comparable [] C) {

        BST X = new BST();

        helperIdeal(C, X.root,(C.length/2));

        return X;
    }

    public static void helperIdeal(Comparable [] C, node R,int mid){


            if(mid<0||mid>C.length-1){
                R.left = null;
                            R.right = null;


        }

            else{
             R.data = C[mid];
             helperIdeal(C,R.left,mid/2);
             helperIdeal(C,R.right,(mid*2)-1);
        }
    }

Ответы [ 2 ]

2 голосов
/ 14 декабря 2011

Я собираюсь считать это домашним вопросом ...

Хитрость к лучшему алгоритму заключается в том, что список сортируется, и всегда читается BST при чтении внизу.

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

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

Двоичное дерево поиска с идеальными средствами топологии, сбалансированное дерево поиска.так что вы получите logn.

Для того, чтобы сделать это, вам нужно начать с начала, и возможно сохранить несколько указателей в вашем массиве, и перемещать ваши указатели в две половины вашего массива, пока вы не поместите все свои элементык дереву и дерево сбалансировано.

легко.

...