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

我想了会，没想明白为啥
有木有小伙伴给解释解释
或帮我搜一搜、截个图的？（我设备有问题，谷歌百度这些搜索引擎用不了）

补充内容 (2020-6-3 19:57):
标题写得太随意：I meant “…insertion和deletion…” by “…insert deletion…”

补充内容 (2020-6-4 06:36):
警告：标题中 “……时间 O(n) = log (n)” 有书写error，我的本意是“……时间 O = O (log n)” 写太随意了当时

补充内容 (2020-6-7 12:07):
从截止到目前为止的回复中抽出丝：楼主的问题准确地说包含三小问 即 1 Why bst 的search的Time O=O(log n)？2 Why insertion的也=O(log n)？3 Why deletion的也=O(log n)？.

补充内容 (2020-6-7 12:10):
从上一个补充内容来看，这个帖子包含太多子问题，会不会分成三个帖子每个帖子各问一个更合适

平均情况是 O(logn)，因为bst是一个接近平衡的bst，这时候你要删除的结点要么在左面，要么在右面。
最坏情况下，bst就是退化成一个linked list，所有删除一个结点的时间退化成O(n)。

一般分析有关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)。

"delete的O(n) 是 log n"

懵了  lz这话我根本看不懂

bst delete是o(1)吧。你是说平衡bst么

yyljolin 发表于 2020/06/03 15:28:17
bst delete是o(1)吧。你是说平衡bst么

说错了，bst是logn，比如就接到左子树，然后搜左子树到底，接上右子树不就行了

yyljolin 发表于 2020-6-3 15:28
bst delete是o(1)吧。你是说平衡bst么

Wikipedia- bst 里写的delete的O(n) 是 log n

我自己不知道delete的O(n)
我相关的想法：就算不考虑balance，假设被delete的node如果有两个孩子，这两个孩子就和tree的其他部分断开了，这种情形处理？处理的O(n)会是O(1)吗

即便被delete的node只有一个孩子，假设处理方式是将这个孩子顶替被delete的node的位置，那意味着要找到被delete的node的parent（这个找会是O(1)吗？），更改parent node的left（或right）

yyljolin 发表于 2020-6-3 15:30
说错了，bst是logn，比如就接到左子树，然后搜左子树到底，接上右子树不就行了

啊
我才看见你还有一楼（就是我现在回复的这楼） 我看看

是这个意思吗：

• 用被delete的node的左孩子替代被delete的node的位置（需要从root搜索找到parent node）（as a result, 你说的"接到左子树"发生）
• 再从这个左孩子一直往右到这个左子树的底（就是你说的"搜左子树到底"）、就找到了左子树value最大的node
• 这个node上"接上"被delete的node的"右子树"
  

好像这个solution可以解决重接的问题
我没能想明白这个solution的O(n)为什么是log n

matthew_z 发表于 2020-6-3 19:17
"delete的O(n) 是 log n"

懵了  lz这话我根本看不懂

这句话写得随意
如果对binary search tree （bst）熟悉有限的话 这句话理解起来费劲也许是fact
楼楼对bst熟悉吗
或者我写得TOO随意了？


anyway："node deletion的时间复杂度O(n)是 log n"

025ebaacad 发表于 2020-6-3 18:55
啊
我才看见你还有一楼（就是我现在回复的这楼） 我看看

找到要delete的node的predecessor或者successor都可以，就是BST序列化后这个node的前一个值或后一个值，用这个值比如successorVal来替换当前node的val，然后再recursion去删除这个successorVal, 时间复杂度是log(n)因为这个方法跟在BST中去查找一个val的时间复杂度是一样的，每次你只用搜索一个node的左子树或右子树，而不是两个子树都要搜索

1.查找是logN
2. 插入类似于查找，所以也是logN
3.删除， 需要先定位到需要删除的节点，然后有三种情况：
  1）要删除的节点没有右child，那么就选择它的左child来代替原来的节点
  2）要删除的节点的右child没有左child，那么用这个右child替换要删除的节点
  3）要删除的节点的右child如果有左child，就要找到右child的左子树中的最下面的节点来替换它，又等有一次向下查找，logN