временная сложность построения бинарного дерева - PullRequest
Новая
       17

временная сложность построения бинарного дерева

0 голосов
/ 19 июня 2020

Существует метод, который строит двоичное дерево, в котором N полных уровней и на каждом уровне I есть два узла, информационные части которых равны I. Какова временная сложность в зависимости от количества уровней дерева построено? 

private SimpleTreeNode fromNDigitToNode(int x,int k) throws Exception {
        IndexWrapper iw = new IndexWrapper();
        T parentValue = readValue((k-x+1)+"",iw);
        SimpleTreeNode parentNode = new SimpleTreeNode(parentValue);
        SimpleTreeNode leftNode = new SimpleTreeNode(parentValue);
        SimpleTreeNode rightNode = new SimpleTreeNode(parentValue);
        if(x<=1)return parentNode;
        int z = --x;
            parentNode.left = fromNDigitToNode(z,k);
            parentNode.right = fromNDigitToNode(z,k);

        return parentNode;
    }

public void fromNDigit(String Ndigit) throws Exception{
        int digit = Integer.parseInt(Ndigit);

        IndexWrapper iw = new IndexWrapper();
        SimpleTreeNode root = fromNDigitToNode(digit,digit);

        this.root = root;
    }
}

1 Ответ

0 голосов
/ 19 июня 2020

Я думаю, что ваш код ошибочен. Вы создаете leftNode и rightNode, но не используете их. Кроме того, как parentNode.left, так и parentNode.right создаются с одинаковыми параметрами. Это правильно?

Я понятия не имею, для чего предназначен ваш IndexWrapper и что делает readValue ().

И самая большая проблема: это никогда не прекращается. Вы не проверяете (например), если x <0. Поэтому вы вызываете это с x = 1. Затем вы дважды выполняете рекурсию, вызывая его с x = 0, затем x = -1, и повторяете до бесконечности. </p>

Итак, я бы сказал, что это Order (навсегда).

Могу я предложить вам на самом деле заставьте ваш код работать, протестируйте его, а ЗАТЕМ определите сложность.

...