計算BST節點移除的時間複雜度

我在查找平均和最壞情況時間複雜度方面有點困難。所以我做了這個BST節點刪除與以下邏輯計算BST節點移除的時間複雜度

當您刪除在二叉搜索樹中的節點，有3種情況

1> The node to delete has no children. That's easy: just release its resources and you're done. Time complexity O(1) 

2> The node has a single child node. Release the node and replace it with its child, so the child holds the removed node's place in the tree. Time complexity O(1) 

3> The node has two children. Find the right-most child of node's left subtree. Assign its value to root, and delete this child. **Here time compexity can be maximum O(N)** 

To find the node to be deleted can be **maximum O(N)**

那麼，你如何計算總平均和最壞時間複雜度？？

來源

2012-08-10 Dilletante

這是一棵平衡樹嗎？節點是O（n）。 – 2012-08-10 12:16:12

在這種情況下，'N'是什麼？ – 2012-08-10 12:17:21

@KolyolyHorvath ...我錯過了一個點.....它不是一個平衡的樹......我只需進行必要的編輯... – Dilletante 2012-08-10 12:23:57

在這種情況下，我認爲最壞情況下的複雜性將足以描述這種情況。

爲了找到最壞情況下的複雜度，只需找出可能出現的三種情況（O（n）情況）中最糟糕的情況。因此，最壞的情況是O（n）。

在一些極少數情況下（如Quicksort），人們選擇描述平均情況複雜度和最壞情況複雜度。在Quicksort的情況下，這是因爲在幾乎所有情況下Quicksort都是O（n * log（n）），並且在一些非常罕見的情況下僅減少到O（n^2）。因此，人們描述了平均情況以及最壞情況的複雜性。

但是，在從二叉搜索樹中刪除一個節點的情況下，刪除一個葉節點（沒有子節點和最好情況）不會更頻繁地發生，也不會比刪除節點有兩個孩子（除非你正在開發一個特殊情況）。

因此，從二叉搜索樹中刪除節點的複雜度是O（n）。

來源

2012-08-16 16:39:29 cyndrus

平均情況下的複雜度是O（log（n）在刪除的情況下爲了找到節點它將花費O（log（n））和再次刪除O（log（n））因此平均值爲O （n））+ O（log（n））= O（log（n））最壞的情況顯然是O（n）有關更多詳細信息 - http://en.wikipedia.org/wiki/Binary_search_tree#Deletion

來源

2014-04-17 13:49:25

計算BST節點移除的時間複雜度

回答

相關問題