建設BST的

Question

http://www.geeksforgeeks.org/group-multiple-occurrence-of-array-elements-ordered-by-first-occurrence/

請檢查這個問題。

如何做BST方法這個問題。

他們提到總時間複雜度將是O（NLogN）。

樹的時間複雜度是如何遍歷LogN的？

請幫

Answer 1

搜索，刪除和插入運行時間都依賴於樹的高度，或爲O(h) BST。退化樹幾乎看起來像一個鏈表可以產生O(N)的運行時間。

。另一方面，考慮一個自我平衡的樹，如AVL樹中，查找運行時間低了O(logN)界定，因爲像二進制搜索，我們通過各一半時間在左，右子樹劃分搜索空間高度幾乎相同。