[理工] 資演 Tree Unbalanced Rotation

[newpuma (還很新)]

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: 3.已經sorting了，把三個merge花O(n)，中位數當root
→ gary19941208: ，左右半部遞迴去做，總共是O(n)
merge花O(n)
剩下的只要遞迴建樹就好 原來如此
那第二題呢？
※ 編輯: newpuma (223.137.200.66), 01/23/2017 08:05:34
推 yupog2003: 第二題我是舉一個skew-binary tree，然後多做幾次觀察
→ yupog2003: 確實是O(logn)
推 FRAXIS: 如果是一個 binary tree 每個 node 只有右子樹 也可以在
→ FRAXIS: O(lg n) 時間內 rotate 到 balance ?
推 Transfat: 對每個點從unbalanced到balanced要花O(1),總共要做O(log
→ Transfat: )次,是嘛（?)
→ ken52011219: 它不是問幾次rotations嗎 ，無關時間複雜度吧
推 FRAXIS: 我是這樣想 每次 rotation 頂多只能把樹高減少一層
→ FRAXIS: 如果 unbalnaced tree height 是O(n)
→ ken52011219: 我認為是O(n/2)
→ FRAXIS: 要怎麼用 O(lg n) rotations 把它 balance?
推 yupog2003: 我剛剛發現我rotation的方式錯了，應該是O(n/2)沒錯
→ yupog2003: 每次rotation，左邊-1，右邊+1
→ yupog2003: 剛剛想成用折的，所以錯了
→ ken52011219: 每個binary search tree n個點共有n-1種 rotation
→ ken52011219: 目前可知在O(n-1) rotations內一定可以完成balance
→ ken52011219: F 大的所說的方式應該是最保險的
推 yupog2003: 感謝k大和F大的糾正QQ