Сложность времени создания двоичного дерева

Question

Я пытаюсь создать дерево из источника, который обеспечивает: 2 узла, которые будут добавлены в дерево, и узел, к которому следует добавить эти 2 узла новостей.Чтобы найти, где этот узел находится в дереве, я использовал обход по порядку, который принимает O (n).Таким образом, если в дереве было добавлено n узлов, будет ли создание всего дерева O (n ^ 2).Мое ограничение заключается в том, что для создания дерева требуется только O (n).

Answer 1

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

Answer 2

Вы можете хранить ссылки на каждый узел дерева в HashMap [1], чтобы получить O(1) доступ к каждому узлу вместо O(log(n)), что типично для деревьев.Это позволило бы построить дерево за O(n) время, потому что этот HashMap позволяет переходить непосредственно к узлу, а не проходить туда из корневого узла дерева.

[1] Ключ будет любымисточник использует для уникальной идентификации узлов (я предполагаю, что это целое число или строка).Значение будет ссылкой на узел в дереве.Обратите внимание, что реализация дерева должна сделать все его узлы общедоступными, поэтому вам, вероятно, придется написать дерево самостоятельно или найти подходящую библиотеку (деревья JDK, такие как TreeMap, сохраняют свою внутреннюю структуру частной, поэтому они не будут ее обрезать).

Answer 3

для дерева времени двоичного поиска сложность будет O (nlogn), когда элементы не отсортированы и не отсортированы, это займет O (n ^ 2).Это связано с тем, что для вставки одного элемента в отсортированный список в BST требуется O (n), поэтому для n элементов O (n ^ 2) и для сбалансированного или почти сбалансированного бинарного дерева поиска максимальное время для вставки записывается так, чтобыn элементов это nlogn