[理工] 資演 Tree Unbalanced Rotation

看板Grad-ProbAsk作者newpuma (還很新)時間7年前 (2017/01/23 07:40)推噓7(7推 0噓 13→)

留言20則, 5人參與討論串1/1

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

想請問第二題跟第三題 rotation的complexity是指中間鍵值往上的調整動作吧？那麽時間複雜度是O(log n) 還是更大？我的想法是調整動到的node數不會大於樹高...不知道有沒有錯第三題問說union三個排序資料，然後保持平衡，假設不平衡點一定小於n個我的想法是最多只會有n個不平衡點，實際上應該更少所以是n*O(log n)嗎但還是不明白 rotation的複雜度跟union後的平衡調整，時間複雜度應該是什麽，翻了翻筆記不知道自己是不是有漏抄 ... 謝謝大家 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.200.66 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485128428.A.E06.html ※ 編輯: newpuma (223.137.200.66), 01/23/2017 07:51:50

推

gary19941208

01/23 07:53, , 1^F

01/23 07:53, 1^F

→

gary19941208

01/23 07:53, , 2^F

01/23 07:53, 2^F

merge花O(n) 剩下的只要遞迴建樹就好原來如此那第二題呢？ ※ 編輯: newpuma (223.137.200.66), 01/23/2017 08:05:34

推

yupog2003

01/23 08:29, , 3^F