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

gq9099 发表于 2020-6-4 00:08
终于搞明白楼下问的是这些操作为什么是O(log(n))。建议楼主先去看一下big O notation的数学定义。

补充内 ...

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

建议楼主先去看一下big O notation的数学定义

Why please?
事实上我看过一些他们的数学定义，过了一遍Cracking the Coding Interview里的一些; Wikipedia里的一些（譬如time complexity，Average (case) time complexity, big o notation)也简单翻了翻。wondering if it's enough that you would say adequate

025ebaacad 发表于 2020-6-8 16:31
------------------------------------------(the 引用 above is auto-generated; the 引用s following i ...

1.balance国内外定义不一样，但这些定义上的差别对复杂度的影响是常数级别的，可以不考虑。
2.正常情况，理解成 tree 是 balance tree 的情况吧，此时所有非叶子结点都有两个孩子的情况。
3.最坏情况，如果考虑到tree 是 链状，用 n 表示就是 O(n)。如果不考虑tree 是链状，复杂度是O(logn).
4.通常分析tree时候，会假设tree 是 balance tree，不考虑链状。
5. 根据time big O 的定义

O(h)......

很好奇不能用google和baidu的设备是什么。。。

另外看楼主意思，是看过crack the code interview和wiki，所以从来没有系统学习过data structure和algorithm？如果楼主想刷题并从事相关职业，推荐先修个data structure和algorithm的课，没条件的各大视频网站都有教学，起码把基础打好。你问的这问题都是课上必然涉及的基础问题。

hh821758 发表于 2020-6-9 03:43
很好奇不能用google和baidu的设备是什么。。。

另外看楼主意思，是看过crack the code interview和wiki ...

我对网络不太自律
如果有google和baidu的话 我可能会用他们来搜新闻、图片 “闲看”，这样会让本该学习的时间减少
所以我的几乎所有设备都不能google和baidu（我自己限制的、我没有解锁密码我朋友帮我保管）
你也许猜到了，google和baidu不是我不让自己上的“唯二”网站，事实上我除了几十个学习工作用的网站外，所有其他网站我都禁止设备访问了——But that's quite enough

我上过data structure，但是没上过algorithm。你一说好像是，这门课的知识很有可能是我缺少的。I will have a check. Thanks a lot!

不过我这个帖子问的问题，似乎并不基础，这里的回复到目前为止并没有帮到我找到答案很多；相信回复的人里多少有experienced/advanced learner/practicer

025ebaacad 发表于 2020-6-11 20:25
我对网络不太自律
如果有google和baidu的话 我可能会用他们来搜新闻、图片 “闲看”，这样会让本该学习 ...

感谢楼主的认真回复。
我说这个问题基础，举个例子，youtube上的随便看的MIT 6.006 Introduction to Algorithm课程，第五节课就把你想知道的全讲了，总共有48节课。

你这个问题简单来说，就是不管insertion还是deletion，都要先找到需要insert或者delete的位置，BST就是不停的跟左右子节点比大小向下找，h一般代表tree height，所以你要向下找h层，h在BST里面等价于logn。找到位置后的insertion/deletion操作是常数时间，所以time complexity是O(logn)。树的均衡问题也有人提到了，best/worst case都是big O的上下边界，你要讨论其他各种边界就要用o, Ω, ω, and Θ（也是算法基础章节要讲的）

祝楼主能早日走上不依靠外力的内心强大型自律，不然感觉你现在有学习的动力却无力施展也挺憋屈。