建立二叉搜索樹和AVL樹所需的時間複雜度之間的區別？

Question

雖然我是學二叉搜索樹（平衡和不平衡），我拿出我需要解決的問題：

1. 如果你建造一個二叉搜索樹（不必是平衡的），用正元素，那麼樹木建設的總時間複雜度是多少？

2. 如果一個AVL樹由n個元素構成，那麼構造AVL樹的時間複雜度是多少？

它應該超過nlog（n）嗎？因爲我們需要大量的AVL樹構建輪換。我知道在AVL樹中的插入和刪除操作將是log（n）順序（如果用隨機元素構建的二叉查找樹具有log（n）高度，則同樣如此）。

但我需要知道整體樹建設成本以及它如何變化，因爲我需要使用平衡搜索樹進行排序。

Answer 1

1. 可以證明，一個BST satisifies的預期高度E [XN] < = 3日誌N + O（1），所以在預期的時間爲O（n log n）的。最壞的情況仍然是O（n^2），例如，如果輸入是排序的。
2. O（n log n），因爲每個添加元素的旋轉量爲O（1）。

Answer 2

讓我們從構建一個AVL tree開始。要創建樹，您必須在其中插入n元素。要在平衡樹中插入元素，您需要log(n)。因此，您最終得到O(n*log(n))。

回到正常的BST。這是違反直覺的，但它取決於你如何構建這棵樹。如果您事先不知道BST的所有元素（online algorithm），則必須依次插入每個元素n。如果你非常不走運，插入的複雜性是O(n)，因此它惡化到O(n^2)。

請注意，這種情況極不可能，但仍有可能。

但是，如果您事先知道所有元素，仍然可以實現O(nlog(n))。您可以對它們進行排序O(nlog(n))，然後按以下順序插入元素。 Take the middle element and insert it as a root，然後對剩下的兩個部分遞歸執行相同的操作。您將最終創建均衡的BST，使用log(n)插入n元素。