→ ken52011219: 平衡後的高度為log n 10/13 00:03
→ ken52011219: T(n) <= c*log n 所以 T(n) = big oh(long) 10/13 00:04
→ kkk22805385: 可是搜尋不是要搜尋n個點 一樣一個一個搜尋 怎麼會從 10/13 00:53
→ kkk22805385: 高度去看 10/13 00:53
推 boy00114: 二元搜尋樹不是跑全部的點吧...比parent大往右;比pare 10/13 01:20
→ boy00114: nt小往左,這樣平衡後最差的情況就是logn（樹高） 10/13 01:20
推 w181496: 可是這題是binary tree 不是BST欸 XD 10/13 02:02
推 w181496: BT的話不管平衡還skewed都是O(N)吧 10/13 02:24
→ chernjason: 我的想法是，題目有說是平均時間下的time complexity 10/13 08:03
→ chernjason: ，所以搜尋時間應該是跟tree高有關係，左斜或右斜才會 10/13 08:03
→ chernjason: 是O(n) 10/13 08:03
推 aa06697: 我也覺得是O(n)耶.... BT不像BST 他沒有規則的 要全部點 10/13 10:06
→ aa06697: 都跑過吧？ 10/13 10:06
→ aa06697: 若照樓上講法這樣sequential array平均不就也是log n 惹 10/13 10:08
→ aa06697: bt用array存 基本上就跟seq areay 沒兩樣 用linked list 10/13 10:09
→ aa06697: 存...怎麼看都不是log n @@ 10/13 10:10
推 ken52011219: XD 可是 這題的大大單純問的是平衡的搜尋時間 10/13 10:26
→ ken52011219: QQ發現我一直看成下面畫線的BST 10/13 10:29
→ ken52011219: 討論一下 因為以link list 來說 binary tree 若 wors 10/13 10:40
→ ken52011219: t case 為O(N) 我比較能接受 average 我想應該不會 10/13 10:40
→ ken52011219: 到O(N)吧@@ 10/13 10:40
→ ken52011219: 哦 好像是big oh(N)沒錯 T(n)<=N 10/13 10:53
→ kkk22805385: 我覺得這老師也看成BST 10/13 11:38