Binary tree DS kkk22805385 PTT批踢踢实业坊

楼主: kkk22805385 (Butterlion) 2016-10-12 23:56:34

http://i.imgur.com/tcqVY7L.jpg
请问为什么平衡的平均搜寻时间会是O(log n)

楼主: kkk22805385 (Butterlion) 2016-10-13 11:38:00

我觉得这老师也看成BST

作者: ken52011219 (呱) 2016-10-13 10:26:00

XD 可是这题的大大单纯问的是平衡的搜寻时间QQ发现我一直看成下面画线的BST讨论一下因为以link list 来说 binary tree 若 worst case 为O(N) 我比较能接受 average 我想应该不会到O(N)吧@@哦好像是big oh(N)没错 T(n)<=N

作者: aa06697 (todo se andarà) 2016-10-13 10:06:00

我也觉得是O(n)耶.... BT不像BST 他没有规则的要全部点都跑过吧？若照楼上讲法这样sequential array平均不就也是log n 惹bt用array存基本上就跟seq areay 没两样用linked list存...怎么看都不是log n @@

作者: chernjason (chernjason) 2016-10-13 08:03:00

我的想法是，题目有说是平均时间下的time complexity，所以搜寻时间应该是跟tree高有关系，左斜或右斜才会是O(n)

作者: ken52011219 (呱) 2016-10-13 00:03:00

平衡后的高度为log nT(n) <= c*log n 所以 T(n) = big oh(long)

楼主: kkk22805385 (Butterlion) 2016-10-13 00:53:00

可是搜寻不是要搜寻n个点一样一个一个搜寻怎么会从高度去看

作者: boy00114 (ponny) 2016-10-13 01:20:00

二元搜寻树不是跑全部的点吧...比parent大往右;比parent小往左,这样平衡后最差的情况就是logn（树高）

作者: w181496 (Kaibro) 2016-10-13 02:02:00

可是这题是binary tree 不是BST欸 XD

继续阅读