[理工] 100 台大電機 資結

看板Grad-ProbAsk作者 (最強弱者)時間5年前 (2018/09/11 18:07), 5年前編輯推噓1(1推 0噓 1→)
留言2則, 1人參與, 5年前最新討論串1/1
https://i.imgur.com/jhukrZm.jpg
請問題目說隨意binary tree 那我假設為BST (1.)考慮left skewed BST (worst case) 插入新節點，必須插入在最後一個節點的左邊 在利用in order 追蹤 可得到時間複雜度為O(n) 所以選項選（A) (2.)考慮 complete BST 假設best case 插入新節點，可得時間複雜度為O(logn) 這時後選項選(B) 最後解答給（A) 請問為什麼（B)選項不能選呢？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 115.82.178.189 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1536660444.A.D06.html
推
09/11 19:12, 5年前 , 1F
我覺得有可能會到O(h)的可能性
09/11 19:12, 1F
→
09/11 19:12, 5年前 , 2F
所以選B不夠嚴謹
09/11 19:12, 2F
原來如此，我沒考慮到嚴謹的問題，感謝！ ※ 編輯: YOAOY (115.82.178.189), 09/11/2018 19:23:33
‣ 更多 YOAOY 的文章
文章代碼(AID): #1RbvFSq6 (Grad-ProbAsk)