Пространственная сложность печати всех путей от корня до листа

Какова пространственная сложность хранения пути т.е. узлы двоичного дерева от корня до определенного листа в массиве?

В основном я ищу пространственную сложность следующего алгоритма:

public void printPath () {
    doPrint(root, new ArrayList<TreeNode>());
}


private void doPrint(TreeNode node, List<TreeNode> path) {
    if (node == null) return;

    path.add(node);

    if (node.left == null && node.right == null) {
        System.out.println("Path from root: " + root.item + " to leaf: " + node.item + " - ");
        for (TreeNode treeNode : path) {
            System.out.print(treeNode.item + " ");
        }
        System.out.println();
    }

    doPrint(node.left , path);
    doPrint(node.right, path);

    path.remove(path.size() - 1);
}

java algorithm binary-tree complexity-theory space-complexity
person JavaDeveloper    schedule 03.02.2015    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Вы сохраняете все узлы, которые лежат на пути от корня к конкретному листу в Списке.

Если двоичное дерево сбалансировано по высоте или является полным / полным двоичным деревом, наихудшая временная и пространственная сложность составляет O (log n), где n - количество узлов в двоичном дереве.

Если у нас нет никакой предварительной информации о типе двоичного дерева, тогда наихудшая временная и пространственная сложность составляет O (n), поскольку дерево может иметь форму, в которой присутствует только левый дочерний элемент или присутствует только правый дочерний элемент. .

person Samprit    schedule 03.02.2015

arrow_upward
2
arrow_downward

Если ваше дерево сбалансировано, оно будет O(log n). Это связано с тем, что сбалансированное двоичное дерево имеет в два раза больше узлов на каждом последующем уровне, поэтому, если вы удвоите количество узлов в дереве, оно добавит только один дополнительный слой.

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

Если ваше дерево полностью несбалансированно (т.е. каждый узел имеет только одного дочернего элемента или меньше), то в конечном итоге вы будете удерживать все дерево в списке, так как вы должны пройти каждый узел в дереве, чтобы достичь единственного листа. В этом случае это будет O(n).

person Matthew Franglen    schedule 03.02.2015

arrow_upward
1
arrow_downward

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

person Lawrence Aiello    schedule 03.02.2015