二叉搜索树中删除的时间复杂度
假设BST的高度是h。如果我们要删除一个有两个子节点的节点，那么该过程的时间复杂度是多少。
我知道在普通的二叉树中，删除的时间复杂度是O（h）；O（n）最坏情况和O（logn）最好情况。但是由于我们用它的右子树的最小节点替换删除节点的键，因此需要更多时间来找到最小键。
那么，有人知道如何解释这种情况下的时间复杂性吗？
共有1个答案
来源维基百科：
有三种可能的情况需要考虑：
>
删除具有一个子节点的节点：删除该节点并将其替换为其子节点。
对于两个子案例的每个实例，一致地使用顺序继承者或顺序前置者可能会导致树不平衡，因此一些实现会在不同的时间选择一个或另一个。
尽管此操作并不总是遍历树到叶子，但这始终是可能的；因此，在最坏的情况下，它需要与树的高度成比例的时间。即使节点有两个子节点，它也不需要更多，因为它仍然遵循一条路径并且不会两次访问任何节点。因此，所有三种情况下的指针调整都需要恒定的时间。
有用的链接：
- http://en.wikipedia.org/wiki/Binary_search_tree#Deletion
- http://cse.iitkgp.ac.in/~pb/algo-1-pb-10.pdf
-
在二元搜索树的情况下，为什么我们不能简单地在一个节点有两个子节点的情况下，将一个节点的前一个节点替换为后一个节点？
-
如果二叉树是平衡的，那么二叉搜索的最佳运行时间是O（log（n））。最坏的情况是，如果二叉树非常不平衡，它基本上表示一个链表。在这种情况下，二进制搜索的运行时间将为O（n）。 但是，如果树只是稍微不平衡，就像这棵树的情况一样： 如果我没记错的话，最好的情况仍然是O（log n）。但是最坏的情况是什么？
-
我已经知道，如果您尝试查找具有特定键的项目，最坏情况下的运行时间是O（n），。如果您试图搜索特定的数据项（您不知道该键），那么最坏情况下的运行时间是O（n）。然而，如果键和数据都是整数，输入项在插入之前被随机置乱，会怎么样。最糟糕的运行时间还会保持不变吗？
-
我正在尝试为我一直在研究的BST结构实现一个移除方法。以下是包含查找、插入和删除方法的代码： 我被告知可以使用insert方法来帮助我使用remove方法，但我只是不知道如何获取最小/最大的元素，然后用该值替换我正在删除的元素，然后递归地删除我获取替换值的节点，同时仍然保持O（logn）的复杂性。有人有什么想法或明显的漏洞我错过了，或任何其他有帮助的，因为我撞我的头在这个问题上？ 编辑：我用答案的
-
二叉树上广度优先搜索的空间复杂度是多少？因为它一次只存储一个级别，我不认为它会是O（n）。
-
我在做作业，实现自己的二叉查找树。问题是，我们有自己的节点实现，它的父节点是不可直接访问的。 我一直在寻找答案，但我不想完全照搬解决方案，尽管如此，我似乎仍然没有得到正确的答案。我错过了一些元素没有被删除的情况。 你能帮帮我吗？我做错了什么？ 这是删除方法： 节点使用通用接口 只有比较的方法。它看起来像这样 我在remove中使用了另一种方法，它设置节点的父节点的子节点，具体取决于它的左子节点还是