Binary serach tree的insert deletion为什么时间 O(n) = log(n)

025ebaacad 发表于 2020-6-3 19:49
这句话写得随意
如果对binary search tree （bst）熟悉有限的话 这句话理解起来费劲也许是fact
楼楼对b ...

LZ你在说什么。。你理解big O time complexity 的含义吗？ O(n)就是时间复杂度为 n， O(logn)就是logn
我猜你是想说big O time = logn 吧, average case下，找到一个在bst的位置不是左就是右，所以就是logn啊

一般分析有关Tree的算法的时间复杂度的时候，可以定义两个变量 n = number of nodes, h = height of the tree。

对于BST的 insert 和 delete，时间复杂度都是 O(h)。我觉得这是最好的回答。

对于您的问题，如果要用 n 来表示的话，首先我们要找 h 和 n的关系。
最差的情况下，tree 是链状的，比如除了叶子节点外，所有节点都只有左孩子，没有右孩子，此时 h = n。insert 和 delete的时间复杂度是 最差是O(n)。
但是，正常的情况下，如果可以假设树是 balance的，那么 h = logn，那么就可以认为insert 和 delete的时间复杂度是 最差是O(logn)。

终于搞明白楼下问的是这些操作为什么是O(log(n))。建议楼主先去看一下big O notation的数学定义。

补充内容 (2020-6-3 09:11):
楼主*

忘了这一楼吧

BST查找是O(lgN) 所以insert就是先查找node然后O(1) insert。同理delete

wareag1e 发表于 2020-6-3 19:58
平均情况是 O(logn)，因为bst是一个接近平衡的bst，这时候你要删除的结点要么在左面，要么在右面。
最坏情 ...

你是想说“平均情况是 O(logn)，【如果】bst是一个接近平衡的bst……”吗？

如果是的话: 是这样的。我问的是general的bst为什么Average Time O是log n？

MacJordan 发表于 2020-6-3 22:43
找到要delete的node的predecessor或者successor都可以，就是BST序列化后这个node的前一个值或后一个值， ...

找到要delete的node的predecessor或者successor都可以，就是BST序列化后这个node的前一个值或后一个值，用这个值比如successorVal来替换当前node的val，然后再recursion去删除这个successorVal

Cool solution！仅替换Val不更改node之间的link的idea很棒，它remove了 the need of 搜索parent node。

时间复杂度是log(n)因为这个方法跟在BST中去查找一个val的时间复杂度是一样的

Thinking 1: 这个方法和BST查找一个val的Time O一样吗？🤔

• 在你的solution里，Time O 决定于Val值的复制黏贴被执行的次数（或者recursion的次数），我思考了下，这个次数是被delete的node的子树的height（设为h_substree），也就是O=h_substree。
• bst里search一个node的Time O = log n
• 这俩相等吗
  

Thinking 2: bst里search 一个node的Time O为什么是log n呢？

• 我感觉这是回答这个帖子的问题的必要信息之一
  

Mr.Brain 发表于 2020-6-3 22:50
1.查找是logN
2. 插入类似于查找，所以也是logN
3.删除， 需要先定位到需要删除的节点，然后有三种情况： ...

1 查找为什么是log N呢？
2 插入为什么类似于查找

• 插入的总是变成一个new leaf node of the tree （那样总是在tree最底部的skyline附近，如下图中的红线），查找可以查找any node in the tree（如下图中的任意蓝node）. 这俩的Time O 类似吗🤔
  

3 这个Solution很有趣诶！我喜欢

zqyzdsjdy 发表于 2020-6-3 22:54
LZ你在说什么。。你理解big O time complexity 的含义吗？ O(n)就是时间复杂度为 n， O(logn)就是logn
...

是你猜的意思，当时写的过于随意了

average case下，找到一个在bst的位置不是左就是右，所以就是logn啊

Average case？

• 你说的是某一个average case？哪个？
• 还是你的意思是分析每个case的Probability和Time O？随后计算Expection作为Average的Time O？
  

不在左就是右？

• 你说的是balance程度较高的bst？
• 还是general地讲？包括每个parent node只有一个child的、实际变成linked list的worst case？
  

Sorry，I tried, but cannot understand you much...

AChris 发表于 2020-6-3 23:11
一般分析有关Tree的算法的时间复杂度的时候，可以定义两个变量 n = number of nodes, h = height of the tr ...

------------------------------------------(the 引用 above is auto-generated; the 引用s following is manually put by 楼楼)

……正常的情况下，如果可以假设树是 balance的……

1 balance：

• 我没有见过"树是balanced的"严密定义，我assume你的definition和Cracking the Coding Interview和AVL tree的（如下截图）一样，并基于同样的definition作如下discussion
  

2 正常的情况？

• 是指除去链状这种worst case的所有其他情况？分析这样的情况对于得到所有情况的Average Time O的帮助是？
• 除去链表这种worst case的所有其他情况里包含树是balanced的情况，也包含树不那么balanced的情况？
  

3 另外

• Overall，your comments discuss two subgroups of all possible bst 情况，讨论这样两种subgroup对于分析所有情况下的Average/Expected Time O 帮助有限？
• 即便把其余情况也考虑：对于分别考虑Time O的上述几种情况，他们的probability distribution怎么计算？没有这个distribution的话就得不出Time O的Average或Expectation？
  

...假设树是 balance的...insert 和 delete的时间复杂度是 最差是O(logn)。

4 balanced bst的deletion的worst case的Time O是log n？Why？
5 为什么要分析worst case而不分析balanced bst的所有case？分析这个worst case的Time O对楼主的问题会不会帮助有限？