0

我很难找出平均和最坏情况的时间复杂度。所以我用以下逻辑删除了这个 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)**

那么如何计算总体平均时间复杂度和最差时间复杂度？

4

2 回答 2

0

在这种情况下，我相信最坏情况的复杂性足以描述这种情况。

为了找到最坏情况的复杂性，只需从您提到的三个可能的情况中找出最坏的情况（O（n）情况）。因此，最坏情况的复杂度为 O(n)。

在一些罕见的情况下（例如快速排序），人们选择描述平均情况复杂性和最坏情况复杂性。在快速排序的情况下，这是因为快速排序几乎在所有情况下都是 O(n*log(n))，而在一些非常罕见的情况下只会减少到 O(n^2)。因此，人们既描述了平均情况，也描述了最坏情况的复杂性。

然而，在从二叉搜索树中删除节点的情况下，删除叶节点（没有子节点和最佳情况）不会比删除有两个子节点的节点更频繁或更少（除非您正在为特殊情况进行开发）。

因此，从二叉搜索树中移除节点的复杂度为 O(n)。

于 2012-08-16T16:39:29.840 回答
0

平均情况复杂度为 O(log(n) 在删除的情况下为查找节点需要 O(log(n) 并再次删除 O(log(n)) 因此平均值为 O(log(n))+ O(log(n))=O(log(n)) 最坏的情况显然是 O(n) 更多细节 - http://en.wikipedia.org/wiki/Binary_search_tree#Deletion

于 2014-04-17T13:49:25.943 回答