algorithm - 使用 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

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

如果列表的长度为 n，则执行 n 插入和 n 删除，这意味着我们得到 O(n^ 2) 与 BST 和 O(nlog(n)) 与 AVL。