我有一个问题，它说：计算紧迫的时间复杂度为插入n个数为二进制搜索树的过程。它并不表示这是否是一个平衡的树或没有。那么，什么答案可以给这样的问题？如果这是一个平衡树，那么高度LOGN，并插入n个数需要O（nlogn）的时间。但是，这是不平衡的，它可能需要甚至为O（n 2 ）在最坏情况下的时间。这是什么意思找到插入n个数为BST的紧迫的时间复杂度？我失去了一些东西？谢谢

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）。

Suppose you're adding a sorted list of numbers, all larger than the largest number in the tree. In that case, all numbers will be added to the right child of the rightmost leaf in the tree, Hence O(n^2).

例如，假设你加号[15..115]下面的树：

For example, suppose that you add the numbers [15..115] to the following tree:

中的数字将被添加为长链，具有单一的右手子的每个节点。对于列表的第i个元素，你就必须遍历〜我的节点，这将产生为O（n ^ 2）。

The numbers will be added as a long chain, each node having a single right hand child. For the i-th element of the list, you'll have to traverse ~i nodes, which yields O(n^2).

在一般情况下，如果你想保持插入和检索在O（nlogn），您需要使用自平衡树的。

In general, if you'd like to keep the insertion and retrieval at O(nlogn), you need to use Self Balancing trees.