二叉搜索树中删除的时间复杂度

Question

假设BST的高度为h。如果我们要删除一个有两个孩子的节点，那么过程的时间复杂度是多少。

我知道在正常的二叉树中，删除的时间复杂度为O（h）; O（n）最坏情况和O（logn）最佳情况。但是由于我们用删除节点的右子树的最小节点替换删除节点的密钥，因此将需要更多的时间来找到最小密钥。

那么，有人知道如何解释这种情况下的时间复杂度吗？

Answer 1

来源维基百科：

删除中

有三种可能的情况需要考虑：

• 删除叶子（没有子节点）：删除叶子很容易，因为我们可以简单地将其从树中删除。

• 删除带有一个子节点的节点：删除该节点并将其替换为其子节点。

• 删除具有两个子节点的节点：调用要删除的节点N。不要删除N。而是选择其有序后继节点或有序前任节点R。将R的值复制到N，然后递归在R上调用delete，直到达到前两种情况之一。如果您选择一个节点的有序后继者，因为右子树不是NIL（我们目前的情况是节点有2个子节点），那么它的有序继任者是其右子树中值最小的节点，它将在最多1个子树，因此删除它属于前两种情况之一。

从二叉搜索树中删除具有两个子节点的节点。首先，确定左子树中最右边的节点，即有序的前任节点6。将其值复制到要删除的节点中。然后可以轻松删除有序的前任，因为它最多有一个孩子。使用标记为9的有序后继对象，该方法对称地起作用。

对于两个孩子的情况的每个实例一致地使用有序后继者或有序前任者会导致树不平衡，因此某些实现在不同时间选择一个或另一个。

运行时分析：

尽管此操作并不总是将树遍历到一片叶子，但这始终是可能的；因此，在最坏的情况下，它需要的时间与树的高度成比例。即使节点有两个子节点，它也不需要更多，因为它仍然遵循一条路径并且不会两次访问任何节点。因此，所有三种情况下的指针调整都需要恒定的时间。

有用的链接：

• http://en.wikipedia.org/wiki/Binary_search_tree#Deletion
• http://cse.iitkgp.ac.in/~pb/algo-1-pb-10.pdf