一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
指尖新闻
Offer多多
Salarytics
Learn
Who's Hiring?
疫情动态
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 1290|回复: 25
收起左侧

[树/链表/图] Binary serach tree的insert deletion为什么时间 O(n) = log(n)

[复制链接] |试试Instant~ |树/链表/图, 刷题
我的人缘0

分享帖子到朋友圈
本楼: 👍   0% (0)
 
 
100% (1)   👎
全局: 👍   94% (37)
 
 
5% (2)    👎
我想了会,没想明白为啥
有木有小伙伴给解释解释
或帮我搜一搜、截个图的?(我设备有问题,谷歌百度这些搜索引擎用不了)



补充内容 (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):
从上一个补充内容来看,这个帖子包含太多子问题,会不会分成三个帖子每个帖子各问一个更合适

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册账号

x

评分

参与人数 1大米 +2 收起 理由
14417335 + 2

查看全部评分


上一篇:内存不够这种follow up,要怎么回答呢
下一篇:寻找一起刷题的战友, 同时寻求建议
我的人缘0
wareag1e 2020-6-3 19:58:06 | 显示全部楼层
本楼: 👍   100% (4)
 
 
0% (0)   👎
全局: 👍   75% (329)
 
 
24% (107)    👎
平均情况是 O(logn),因为bst是一个接近平衡的bst,这时候你要删除的结点要么在左面,要么在右面。
最坏情况下,bst就是退化成一个linked list,所有删除一个结点的时间退化成O(n)。
回复

使用道具 举报

我的人缘0
AChris 2020-6-3 23:11:19 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   90% (9)
 
 
10% (1)    👎
一般分析有关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)。



回复

使用道具 举报

我的人缘0
amgfan 2020-6-3 19:17:53 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   94% (625)
 
 
5% (34)    👎
"delete的O(n) 是 log n"

懵了  lz这话我根本看不懂
回复

使用道具 举报

我的人缘0
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   96% (60)
 
 
3% (2)    👎
bst delete是o(1)吧。你是说平衡bst么
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (60)
 
 
3% (2)    👎
yyljolin 发表于 2020/06/03 15:28:17
bst delete是o(1)吧。你是说平衡bst么
说错了,bst是logn,比如就接到左子树,然后搜左子树到底,接上右子树不就行了
回复

使用道具 举报

我的人缘0
 楼主| 025ebaacad 2020-6-3 18:32:50 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (37)
 
 
5% (2)    👎
本帖最后由 025ebaacad 于 2020-6-3 18:54 编辑
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)




本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
回复

使用道具 举报

我的人缘0
 楼主| 025ebaacad 2020-6-3 18:55:38 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (37)
 
 
5% (2)    👎
本帖最后由 025ebaacad 于 2020-6-3 19:15 编辑
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



回复

使用道具 举报

我的人缘0
 楼主| 025ebaacad 2020-6-3 19:49:13 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (37)
 
 
5% (2)    👎
本帖最后由 025ebaacad 于 2020-6-3 19:55 编辑
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"





回复

使用道具 举报

我的人缘0
MacJordan 2020-6-3 22:43:02 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (103)
 
 
5% (6)    👎
025ebaacad 发表于 2020-6-3 18:55

我才看见你还有一楼(就是我现在回复的这楼) 我看看

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

使用道具 举报

我的人缘0
Mr.Brain 2020-6-3 22:50:29 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   89% (506)
 
 
10% (61)    👎
1.查找是logN
2. 插入类似于查找,所以也是logN
3.删除, 需要先定位到需要删除的节点,然后有三种情况:
  1)要删除的节点没有右child,那么就选择它的左child来代替原来的节点
  2)要删除的节点的右child没有左child,那么用这个右child替换要删除的节点
  3)要删除的节点的右child如果有左child,就要找到右child的左子树中的最下面的节点来替换它,又等有一次向下查找,logN


回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-7-12 10:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表