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

Question

Что такое вычислительная сложность (временная и пространственная сложность) построения сбалансированного дерева двоичного поиска?

Answer 1

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

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

Answer 2

Сложность времени для построения BST с n узлами составляет O(n*log(n)).

Почему? Вам нужно go через каждый из n узлов, чтобы вставить его в дерево. Теперь для вставки одного узла потребуется log(n) сравнений.

Таким образом, общая сложность времени для вставки n узлов в двоичное дерево поиска будет O(n*log(n))