[理工] 95中正資結 TampaBayRays PTT批踢踢實業坊

作者: TampaBayRays (光芒今年拿冠軍) 2017-07-23 22:06:48

http://i.imgur.com/joHuaMF.jpg
binary tree的search 感覺應該是(1+2+...+n)/n=O(n)?
解答的說法應該是binary search tree?
感謝各位大大回答！

作者: brilliantl (brilliant) 2017-07-23 22:43:00

作者: TampaBayRays (光芒今年拿冠軍) 2017-07-23 22:46:00

感謝樓上，不過這個是binaray search tree，題目說search in a binary tree應該是指在binary tree搜尋而不是在binary search tree搜尋？

作者: sarsman (DeNT15T♠) 2017-07-23 22:54:00

感覺是少打Search

作者: TampaBayRays (光芒今年拿冠軍) 2017-07-23 23:22:00

不過我剛剛有去查考古題，真的是寫binary tree，所以是中正教授打錯嗎XD

作者: hodo (hodo) 2017-07-24 09:26:00

高度平衡下就等於在算2T(n/2)+1吧？

作者: TampaBayRays (光芒今年拿冠軍) 2017-07-24 20:58:00

樓上你說的是binary search tree 吧？

作者: brilliantl (brilliant) 2017-07-25 10:50:00

Binary tree 有分好幾種，search最慢的情況是每個node都找過一次，最快的是complete BT那種只要O(lgn)就可以找到

作者: TampaBayRays (光芒今年拿冠軍) 2017-07-25 12:08:00

繼續閱讀