BST节点移除的时间复杂度计算

Question

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

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

Answer 1

平均复杂度为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

Answer 2

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

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

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

然而，在从二元搜索树中删除节点的情况下，删除叶节点（无子节点和最佳情况）的频率不会比删除一个有两个子节点的节点的频率高很多，也不会比删除一个有两个子节点的节点的频率低很多（除非您针对特殊情况进行开发）。

因此，从二叉搜索树中删除节点的复杂性为O（n）。