我有一个问题，它说"calculate the tight time complexity for the process of inserting n numbers into a binary search tree" . 它并不表示这是否是一棵 balancer 的树 . 那么，对这样的问题可以给出什么答案？如果这是一个 balancer 树，则高度为logn，插入n个数字需要O（nlogn）时间 . 但这是不 balancer 的，在最坏的情况下可能需要O（n2）时间 . 找到将n个数字插入bst的时间复杂度是什么意思？我错过了什么吗？谢谢
2 回答
It could be O(n^2) even if the tree is balanced.
假设您要添加一个排序的数字列表，这些数字都大于树中的最大数字 . 在这种情况下，所有数字都将被添加到树中最右边的叶子的右子节点，因此O（n ^ 2） .
例如，假设您将数字[15..115]添加到以下树中：
这些数字将作为长链添加，每个节点都有一个右手孩子 . 对于列表的第i个元素，您将必须遍历~i个节点，这会产生O（n ^ 2） .
通常，如果您希望将插入和检索保留在O（nlogn），则需要使用Self Balancing trees .
维基说的是对的 . 由于给定的树是BST，因此不需要搜索整个树，只需将要插入的元素与树/子树的根进行比较，就可以得到第n个元素的相应节点 . 这需要O（log2n） . 一旦我们有了这样一个节点，我们可以在那之后插入密钥，之后需要将右边的aub-tree中的所有元素推到右边，这样就不会违反BST的搜索属性 . 如果要插入的位置是最后一个，我们需要担心第二个过程 . 如果注意这个程序可能需要O（n），最坏的情况！因此，在BST中插入元素的总体最坏情况复杂度将是O（n） . 谢谢！