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

繼續閱讀