I have got a question, and it says "calculate the tight time complexity for the process of inserting n numbers into a binary search tree". It does not denote whether this is a balanced tree or not. So, what answer can be given to such a question? If this is a balanced tree, then height is logn, and inserting n numbers take O(nlogn) time. But this is unbalanced, it may take even O(n2) time in the worst case. What does it mean to find the tight time complexity of inserting n numbers to a bst? Am i missing something? Thanks
即使树是平衡的，它也可能是 O(n^2)。
假设您要添加一个已排序的数字列表，所有数字都大于树中的最大数字。在这种情况下，所有数字都将添加到树中最右边叶子的右孩子中，因此 O(n^2)。
例如，假设您将数字 [15..115] 添加到以下树中：
这些数字将作为一条长链添加，每个节点都有一个右侧子节点。对于列表中的第 i 个元素，您必须遍历 ~i 个节点，这会产生 O(n^2)。
一般来说，如果你想保持插入和检索的时间复杂度为 O(nlogn)，你需要使用自平衡树.
