Одинаковы ли временная сложность предварительного заказа и DFS в сбалансированном бинарном дереве?

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

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

Таким образом, в этом смысле, лучший ответ на ваш вопрос, вероятно, «DFS, обходы по порядку, обходы по предварительному заказу и обходы по порядку BST всегда занимают одинаковое количество времени (Θ (n)), а сложность пространства зависит от высоты дерева, которое может варьироваться от Θ (log n) до Θ (n). «