推 FRAXIS: RB和AVL的cost都是O(lg n)，但是旋轉次數不同。01/29 23:08
→ FRAXIS: 插入都只要O(1)旋轉 (你可以自己算出裡面的constant是多少01/29 23:09
→ FRAXIS: AVL在刪除的時候需要O(lg n)旋轉，但是RB Tree只需要O(1)01/29 23:09
推 HiltonCool: AVL/R-B insert：[DS]1 Rotation [Algo]2 Rotation 01/30 00:08
→ HiltonCool: AVL/R-B delete：[DS]2 Rotation [Algo]3 Rotation01/30 00:09
→ HiltonCool: 因為上課的時候R-B tree是用[Algo]的定義，所以感覺用01/30 00:10
→ HiltonCool: [Algo]的答案可能會好一點(我猜的XD)
[NCU 101 II 3(c)]
已知 G = (V,E) , 及其MST T , 如果現在新增一個點x構成 G'=(V∪x,E∪E(x)) , 得到
G'之MST的演算法能多快? (note:E(x)包含x與G相鄰的邊)?
E(x)中可能不只一條edge可以取代T中的edge,所以必須整個G'再重跑一次MST Algo?
有辦法再linear time完成嗎?
http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/103/103418.pdf
[NTUEE 103 DS]
1.用link list實做一個sort list,另外需額外兩個變數協助median()運作
分別為mid element的指標,與目前list的element個數 num
如此 insert() / delete() 皆須O(n)
median僅需O(1):用num判斷mid指標如何調整即可
是否有更快的方法 ?
→ FRAXIS: NTUEE 103 DS 用 兩個priority queue01/29 23:10
3(a)(b)
只想到用 圓心距離-半徑和 判斷是否屬於同一個 colsed region
用Disjoint Set的表示法將屬於同一個 closed region的circle指向同個區塊的某個circle
不過在題幹要求的兩個動作
op1: 回報目前colsed region數量
op2: 加入新的circle並更新colsed region數量
都需要花O(n)才能完成 //n為circle的個數
是否有更好的想法?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.115.82.209
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1422540457.A.C2A.html
→ killerw74: NCU 101 II 3(c) 感覺加進T中做Mst就可以 01/29 22:40
→ killerw74: 不過應該也無法變成線性頂多VlogV 01/29 22:40
推 FRAXIS: RB和AVL的cost都是O(lg n)，但是旋轉次數不同。 01/29 23:08
→ FRAXIS: 插入都只要O(1)旋轉 (你可以自己算出裡面的constant是多少 01/29 23:09
→ FRAXIS: AVL在刪除的時候需要O(lg n)旋轉，但是RB Tree只需要O(1) 01/29 23:09
→ FRAXIS: NCU 101 II 3(c) 可以在O(|V|)時間內完成 但是有點複雜.. 01/29 23:10
→ FRAXIS: 雖然技巧不難 但是要把這些都combine起來不容易.. 01/29 23:10
→ FRAXIS: NTUEE 103 DS 用 兩個priority queue 01/29 23:10
→ FRAXIS: 3(a)(b) 用disjoint set應該可以在O(lg*n)完成.. 01/29 23:11
推 HiltonCool: AVL/R-B insert：[DS]1 Rotation [Algo]2 Rotation 01/30 00:08
→ HiltonCool: AVL/R-B delete：[DS]2 Rotation [Algo]3 Rotation 01/30 00:09
→ HiltonCool: 因為上課的時候R-B tree是用[Algo]的定義，所以感覺用 01/30 00:10
→ HiltonCool: [Algo]的答案可能會好一點(我猜的XD) 01/30 00:11
謝謝大家回覆
想補問F大 , MST那題你的想法是用到MST證明的觀念嗎?
因為如果只有一根non MST edge確實可以丟到T裡面
->檢查cycle
->捨去最大邊 , 因為MST cycle至長|V|-1 , 故複雜度是O(|V|)
不過這個方式再不只一邊的時候似乎會有問題 , 不確定你提到的O(|V|)是否和
這個想法相似 ?
NTUEE 103 3(a)(b)
這邊我的問題是
即使使用 Disjoint Set , 新加入的circle仍要一一去比對同一個set中的所有circle
(因為是取相交的circle屬於同一個set , 若A,B屬於相同set , 和A相交未必和B相交),
如果不幸地每次都恰巧和檢查到的最後一個circle才發生相交,或是input都是不相交的
circle,這樣仍無法避免worst case會需要O(n) ?
※ 編輯: qoojordon (59.115.64.42), 01/30/2015 08:52:10
推 winnie48: 那上面97 11(d) 說AVL insert 最多需兩次rotation是錯 01/30 08:10
→ winnie48: 的耶？ 01/30 08:10
推 galapous: 想問一下為什麼插入的複雜度是O(1),不是有可能調到很上 01/30 10:29
→ galapous: 面的父點嗎？還是這是平均後的複雜度 01/30 10:29
推 galapous: 101 3（c）我的想法把原來每個點都設值，值是連到他的 01/30 10:42
→ galapous: 邊中cost最小的，插入x後先選最小的邊跟原圖相連，再檢 01/30 10:42
→ galapous: 查每個點連到x的cost是否小於點上記錄的值，若是就換掉 01/30 10:42
→ galapous: 。不過設值的步驟好像不是linear… 01/30 10:42
→ killerw74: 圓的那題 想法跟原po一樣 頂多設set的最大最小xy 可以 01/30 11:18
→ killerw74: 減少一些搜尋但仍為O(n) 01/30 11:18
推 kather: 為什麼圓形那堤(a)可以O(n)? 就算用set還是每次都要跟每個 01/30 12:43
→ kather: 圓形檢查是否交集不是嗎@@? 01/30 12:44
謝謝w大提醒,已修證
回覆galapous:
請問你指得調整父點是?? 如果是AVL tree我做過的case都是 constant
如果是RB tree , 會往上調整的只有叔叔為R的case , 往上只會牽涉變色 ,
一但某次需要靠旋轉做調整 , 即調整完成不會在往上了 , 所以還是constant次旋轉
至於刪除考古題中出現的次數太少,我自己也不是很有把握,看回文的話 AVL tree的部分
F大和H大的回覆有些出入 , WIKI的說法比較接近F大的
http://zh.wikipedia.org/zh-tw/AVL%E6%A0%91
回覆kather:
這邊的O(n)是指在Disjoint Set已經建好的情況下去討論的 , 如果是只給 n筆circle
資料要建出滿足相交關係的 Disjoint Set以我的方法需要O(n^2)
※ 編輯: qoojordon (59.115.64.42), 01/30/2015 19:29:41
推 galapous: 我好像了解了,我想成插入之後要往上搜尋從哪個父點開始 01/30 20:13
→ galapous: 不平衡,rotation好像沒指這段過程? 01/30 20:13
→ qoojordon: 嗯 我感覺它是要考這個 01/30 20:36
推 FRAXIS: NTUEE 103 3(a)(b) 應該不用判斷都交集吧 只要有一個交集 01/30 20:58
→ FRAXIS: 就可以union不是嗎？ 01/30 20:59
A C
|---------| |----|
|-----|
B
Disjoint Set:
A
↑
B
這樣的話當C加入時需要判斷要不要和A做Union , 如果C只和A做是否相交的判斷會出錯
※ 編輯: qoojordon (59.115.64.42), 01/30/2015 21:16:49
推 FRAXIS: 我搞笑了.. 01/30 21:26
推 FRAXIS: NTUEE 103 3(a) 可以用plane sweep 類似線段相交的方法 01/30 21:30
推 FRAXIS: NTUEE 103 3(b) 要先把circle建資料結構 像是kd-tree.. 01/30 22:00
→ FRAXIS: [NCU 101 II 3(c)] 是基於Boruvka's algorithm.. 01/30 22:02
→ killerw74: 線段樹....而且還二維...加上disjoint..這也太難...已 01/30 22:26
→ killerw74: 經是比賽題了 01/30 22:26
推 HiltonCool: 因為之前寫題目的時候也有遇到最多rotation次數的問題 01/30 22:55
→ HiltonCool: 所以我就跑去問洪逸說AVL跟R-B的插入跟刪除最多會有幾 01/30 22:56
→ HiltonCool: 次rotation，結果他就跟我說是那樣，AVL插入上課有講 01/30 22:57
→ HiltonCool: [DS]跟[Algo]跟別是1跟2，但其他因為都沒講過，所以我 01/30 22:59
→ HiltonCool: 就硬背了@@ 01/30 22:59
推 HiltonCool: 不過cost應該是O(logn)沒問題 01/30 23:02
推 FRAXIS: AVL刪除會有 O(lg n) rotation 01/31 00:54
→ FRAXIS: 你要先建立起一個n個node 最高高度的AVL tree 然後刪除 01/31 00:54
→ FRAXIS: 你就會發現你需要O(lg n)次旋轉才可以rebalance.. 01/31 00:55
推 hyc1227: 可以順便問一下 NTUEE 103 2(b)(c)嗎? 01/31 20:56
推 winnie48: 樓上c小題可以參考這份投影片第32頁之後 02/01 08:58
推 hyc1227: 感謝樓上 來研究一下 02/01 15:19
推 NTPU5566Kobe: 推 02/03 03:02
推 FRAXIS: NTUEE 103 3(b) 我發現其實就是計算 power diagram.. 02/12 23:33