將n個數字插入二叉搜索樹的複雜性

我有一個問題，它說「計算將n個數字插入二叉搜索樹的過程的緊時間複雜度」。它並不表示這是否是一棵平衡的樹。那麼，對這樣一個問題可以給出什麼答案呢？如果這是一棵平衡樹，那麼高度是logn，並且插入n個數字需要O（nlogn）時間。但是這是不平衡的，在最壞的情況下，甚至可能需要O（0時32分0秒）。找到插入n個數字到bst的緊湊時間複雜度意味着什麼？我錯過了什麼嗎？謝謝將n個數字插入二叉搜索樹的複雜性

來源

2013-03-10 yrazlik

即使樹是平衡的，它可能是O（n^2）。

假設您正在添加一個排序的數字列表，它們都大於樹中最大的數字。在這種情況下，所有的數字都會被添加到樹中最右邊的葉子的右邊，因此O（n^2）。

例如，假設要添加的數字[15..115]將下面的樹：

enter image description here

的數字將被添加爲長鏈，具有單個右手每個節點兒童。對於列表的第i個元素，必須遍歷〜i個節點，這會產生O（n^2）。

一般來說，如果你想保持O（nlogn）的插入和檢索，你需要使用Self Balancing trees。

來源

2013-03-10 12:53:17

我明白了，但我不明白爲什麼它是O（n^2） – yrazlik 2013-03-10 12:57:25

我的意思是，這仍然是一個最壞的情況，緊密的時間複雜度是否意味着？那麼，Θ（n^2）？ – yrazlik 2013-03-10 13:00:46

是的，這是最糟糕的情況。你可以用O（nlogn）找到一個特定的場景。 – 2013-03-10 13:02:48

Wiki說的是正確的。由於給定的樹是一個BST，所以不需要搜索整個樹，只需比較要插入的元素與樹/子樹的根就可以得到適當的節點。這需要O（log2n）。一旦我們有了這樣一個節點，我們可以在那裏插入密鑰，之後它需要將右邊的aub-tree中的所有元素向右推，以便BST的搜索屬性不會被違反。如果要插入的地方是最後一個，我們需要擔心第二個過程。如果注意這個過程可能需要O（n），最壞的情況！因此，在BST中插入元素的總體最壞情況複雜度爲O（n）。謝謝！

來源

2017-01-04 08:55:49 Jiten

將n個數字插入二叉搜索樹的複雜性

回答

相關問題