将n个数字插入二叉搜索树的复杂性

Question

我有一个问题,它说"计算将n个数字插入二叉搜索树的过程的紧迫时间复杂度".它并不表示这是否是一棵平衡的树.那么,对这样的问题可以给出什么答案？如果这是一个平衡树,则高度为logn,插入n个数字需要O(nlogn)时间.但这是不平衡的,在最坏的情况下可能需要O(n ²)时间.找到将n个数字插入bst的时间复杂度是什么意思？我错过了什么吗？谢谢

Answer 1

即使树是平衡的,它也可以是O(n ^ 2).

假设您要添加一个排序的数字列表,这些数字都大于树中的最大数字.在这种情况下,所有数字都将被添加到树中最右边的叶子的右子节点,因此O(n ^ 2).

例如,假设您将数字[15..115]添加到以下树中:

这些数字将作为长链添加,每个节点都有一个右手孩子.对于列表的第i个元素,您将必须遍历~i个节点,这会产生O(n ^ 2).

通常,如果您希望在O(nlogn)处保留插入和检索,则需要使用自平衡树.