Рекурсивный метод toString () в бинарном дереве поиска.Какова сложность времени для этого?

Question

Я новичок в Java и ищу некоторую помощь.

Итак, я создал это двоичное дерево в Java и должен реализовать метод, который сортирует все элементы по порядку и конвертируетих в строку.Он должен выглядеть как бывший.«[1, 2, 3, 4]».Для этого я использовал StringBuilder.

Мой код для метода выглядит следующим образом:

/**
 * Converts all nodes in current tree to a string. The string consists of
 * all elements, in order.
 * Complexity: ?
 * 
 * @return string
 */
public String toString() {
    StringBuilder string = new StringBuilder("[");
    helpToString(root, string);
    string.append("]");
    return string.toString();
}

/**
 * Recursive help method for toString. 
 * 
 * @param node
 * @param string
 */
private void helpToString(Node<T> node, StringBuilder string) {
    if (node == null)
        return; // Tree is empty, so leave.

    if (node.left != null) {
        helpToString(node.left, string);
        string.append(", ");
    }

    string.append(node.data);

    if (node.right != null) {
        string.append(", ");
        helpToString(node.right, string);
    }
}

Итак, мой вопрос, как рассчитать сложность времени для этого?Кроме того, если есть какие-либо предложения о том, как сделать этот метод лучше, я с радостью это оценил бы.

Answer 1

Самый простой ответ: O(n). Вы посещаете каждый узел один раз и выполняете один (а) объем работы. Расчет будет выглядеть как

O(a*n)

и поскольку мы игнорируем постоянные факторы, простой ответ будет

O(n)

Но . Можно также утверждать, что вы делаете немного больше: вы возвращаете null каждый раз, когда посещаете место, где нет листьев. Это опять-таки один (б) объем работы, который нужно сделать.

Давайте на минутку назовем эти невидимые листья . Следуя этой идее, каждое значение в дереве - это узел , который имеет один или два невидимых листа .

Итак, теперь у нас есть следующее (для каждого узла):

a       | if a node has two child nodes
a + b   | if a node has one child node
a + 2b  | if a node has no child node.

для двоичного дерева наихудшего случая (полностью несбалансированного) у нас есть (n-1) узлов с одним дочерним узлом и одним узлом без дочерних узлов:

  "1"
    \
    "2"
      \
      "3"
        \
        "4"

Итак, расчет

     (n-1)*(a+b) + b
 <=> an + bn - a - b + b
 <=> n(a+b) + b

  => O(an + bn)  // we ignore `+ b` because we always look at really big n's

К счастью, даже в худшем случае сложность все еще линейна. Только константа выше, чем в простом ответе. В большинстве случаев - обычно, когда Big-O необходим для сравнения алгоритмов - мы даже игнорируем фактор, и мы рады сказать, что временная сложность алгоритмов линейна (O (n)).

Answer 2

Сложность по времени составляет O (n), поскольку вы посещаете каждый узел один раз. Вы не можете сделать что-то лучше, чем ходить по дереву.

Answer 3

Сложность по времени линейна по количеству узлов в дереве: вы посещаете каждый узел ровно один раз.