Самый эффективный способ распечатать AVL дерево строк?

Question

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

O(n) последнее, что мы могли бы сделать здесь?

Answer 1

Преобразование и расширение комментария @CB в ответ:

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

Мы можем быть еще точнее здесь. Предположим, что общая длина всех строк в дереве равна L. Время, необходимое для распечатки всех строк в дереве, должно быть не менее Θ(L), поскольку для вывода каждого отдельного символа требуются некоторые вычислительные усилия. Следовательно, мы можем сказать, что нам нужно выполнить как минимум Θ(n + L) работу, чтобы распечатать все строки в дереве.

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

Теперь одна область, где вы можете искать экономию, это сложность пространства. Для обхода дерева по порядку уровней может потребоваться Ω(n) общего пространства, если дерево идеально сбалансировано (поскольку в нем содержится целый слой дерева в памяти, а в самом нижнем слое может быть Θ(n) узлов), в то время как обход по порядку, по предзаказу или по порядку требует только O(log n) памяти, потому что вам нужно только сохранить текущий путь доступа, который имеет логарифмическую высоту в дереве AVL.