删除二叉树中的节点的时间复杂度是多少 [英] What is the time complexity of deleting a node in a binary tree

问题描述

要删除二叉树中的节点，我们必须搜索该节点.最小值为O(log N)，最大值为O(N).根据节点，我们必须重新排列指针.我们如何计算时间的复杂度.

For deleting a node in the binary tree, we have to search the node. That is possible in minimum O(log N) and max O(N). Depending on the node, we have to rearrange the pointers. How do we calculate the time complexity of that.

推荐答案

这取决于您执行删除操作的方式.最常见的方法包括找到节点的后继节点，然后用该后继节点替换节点.可以在O(h)中完成，其中h是树的高度.最坏的情况是O(n)，但是在平衡树中，最坏的情况是O(lg n).

That depends on how you're doing the deletion. The most common way involves finding the successor of the node, then replacing the node with that successor. This can be done in O(h), where h is the height of the tree. In the worst case this is O(n), but in a balanced tree is worst-case O(lg n).

这篇关于删除二叉树中的节点的时间复杂度是多少的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！