Re: [理工] 102 台大電機丙 資結 對答案

[jjjjj4445 (村)]

想問一下第4題 這題我寫A

balance binary tree 左右子樹最多只差一個node
搜尋某個元素 不就更剛好是O(logn)了嗎?



: ※ 引述《olderbrother (大蜘蛛)》之銘言：
: : 題目
: : http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/102/102409.pdf
: : 我寫的答案
: : (A:True, B:False, 考卷上是這樣標的...)
: :  1. B
: :  2. B
: :  3. A
: :  4. B
: :  5. A
: :  6. B  (感謝 A4P8T6X9 大大)
: :  7. B
: :  8. B
: :  9. B
: : 10. A
: : 11. A
: : 12. A
: : 13. B
: : 14. A
: : 15. B
: : 16. A
: : 17. B
: : 18. B  (感謝 a5120265 大大)
: : 19. A  (感謝 A4T8T6X9 大大)
: : 20. B  (感謝 A4T8T6X9 大大)
: : 21. B
: : 22. A
: : 23. B
: : 24. A
: : 25. B
: : 6 19 20 要麻煩大家幫忙湊答案了...

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 211.79.198.240
推 vagrantw:Balance BT喔 並不一定是BST 既然沒有規則，最慘是O(n)
推 vagrantw:如果是balance bst 那就O(lgn)
→ kiki86151:BT每一個node都要找 所以是最差O(n)
→ jjjjj4445:原來如此!!DS(B)考的滿心機的,題目要看很清楚XD
→ w781204:這一題錯的點應該是左右子樹是高度差1而不是node數差1吧@@
→ w781204:不知道我自己定義有沒有記錯@@