二叉搜索樹的時間複雜度

Question

如果我爲我的bst使用insert（）函數，則時間複雜度可能與O（n）一樣差，並且與O（log n）一樣好。我假設如果我有一個完美平衡的樹，時間複雜度就是log n，因爲每次我走下一個「分支」時我都能忽略樹的一半。如果我的樹完全不平衡，它將是O（n）。我想這是否正確？

Answer 1

是的，這是正確的，參見例如。維基百科，http://en.wikipedia.org/wiki/Binary_search_tree#Searching。

如果您使用例如C++ STL std :: map或std :: set，你會得到一個紅黑平衡的樹。另外值得注意的是，通過這些STL數據結構，你可以在100％的時間內獲得這種性能，這在例如數據結構中非常重要。硬實時系統。哈希表甚至更快，但像紅黑樹一樣，速度並不快。