什麼是使用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公司的。