[理工] 95中正 資結

[TampaBayRays (光芒今年拿冠軍)]

http://i.imgur.com/joHuaMF.jpg

binary tree的search 感覺應該是(1+2+...+n)/n=O(n)?

解答的說法應該是binary search tree?

感謝各位大大回答！
-----
Sent from JPTT on my iPhone

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.127.199.39
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1500818813.A.EC3.html
推 brilliantl: http://i.imgur.com/lXeYWiO.jpg
→ brilliantl: http://i.imgur.com/lXeYWiO.jpg
→ brilliantl: 抱歉，多傳一次
→ TampaBayRays: 感謝樓上，不過這個是binaray search tree，題目說s
→ TampaBayRays: earch in a binary tree應該是指在binary tree搜尋
→ TampaBayRays: 而不是在binary search tree搜尋？
推 sarsman: 感覺是少打Search
→ TampaBayRays: 不過我剛剛有去查考古題，真的是寫binary tree，所
→ TampaBayRays: 以是中正教授打錯嗎XD
→ hodo: 高度平衡下就等於在算2T(n/2)+1吧？
→ TampaBayRays: 樓上你說的是binary search tree 吧？
→ brilliantl: Binary tree 有分好幾種，search最慢的情況是每個node
→ brilliantl: 都找過一次，最快的是complete BT那種只要O(lgn)就可
→ brilliantl: 以找到
→ TampaBayRays: http://i.imgur.com/pMObMQq.jpg
→ TampaBayRays: XD