使用 AVL 树和二叉树的该算法的时间复杂度是多少

Question

考虑以下使用二叉搜索树对 n 个元素的列表进行排序的算法：

initialise t to be an empty binary search tree
for each element x in the list,
  add x to t
while t is not empty,
  remove and print the smallest element of t

如果使用以下方法实现树，则该算法的最坏情况时间复杂度是多少：

a) 普通的二叉搜索树？
b) AVL 树？

我的解决方案：我认为解决方案是，对于 AVL 树：O(Log N) 而对于 BST，它将是 O(N)

Answer 1

这些树的插入/删除的最坏情况是O(n)BST 和O(log(n))AVL。

如果列表很长，n您会进行n插入和n删除操作，这意味着我们可以O(n^2)使用 BST 和O(nlog(n))AVL。