我有一个问题，它说“计算将n个数字插入二叉搜索树的过程的时间复杂度”。它不表示这是否是平衡树。那么，对这个问题可以给出什么答案呢？如果这是一棵平衡的树，则高度为logn，插入n个数字需要O（nlogn）时间。但这是不平衡的，在最坏的情况下甚至可能需要O（n2）时间。找到将n个数字插入bst 的紧凑时间复杂性意味着什么？我想念什么吗？谢谢
即使树是平衡的，也可能是O（n ^ 2）。
假设您要添加一个排序的数字列表，这些列表均大于树中的最大数字。在这种情况下，所有数字将被添加到树中最右边的叶子的右边子元素，因此为O（n ^ 2）。
这些数字将作为一条长链添加，每个节点都有一个右手子节点。对于列表的第i个元素，您必须遍历〜i个 节点，这将产生O（n ^ 2）。
通常，如果您希望将插入和检索保持在O（nlogn），则需要使用 Self Balancing trees.
