[資工] 97-103電機丙數題(RB,AVL),中央101 MST

看板Grad-ProbAsk作者 (穎川琦)時間11年前 (2015/01/29 22:07), 11年前編輯推噓19(19推 0噓 32→)
留言51則, 9人參與, 最新討論串1/1
看電機丙的幾個考古希望確認 [NTUEE 100 10(a)] F The number of rotations per insert/delete operation in a Red-Black tree is O(logn). [NTUEE 97 11(d)] T 1/30修正,謝謝FRAXIS,HiltonCool After inserting a new node to an AVL tree, at most two rotation are needed to re-balanced the tree. [NTUEE 97 15(e)] T After inserting a new node to an Red-Black tree, at most two rotation are needed to re-balanced the tree. ---------------------------- AVL 和 Red-Black 兩者應該都是至多花2次rotation? 至於為什麼兩種資料結構的insert/delete都是複雜度logn , 是因為找到插入(or刪除)位置 的cost(因為balanced tree不會走太深,至多logn)?
推
01/29 23:08,
RB和AVL的cost都是O(lg n)，但是旋轉次數不同。
01/29 23:08
→
01/29 23:09,
插入都只要O(1)旋轉 (你可以自己算出裡面的constant是多少
01/29 23:09
→
01/29 23:09,
AVL在刪除的時候需要O(lg n)旋轉，但是RB Tree只需要O(1)
01/29 23:09
推
01/30 00:08,
AVL/R-B insert：[DS]1 Rotation [Algo]2 Rotation
01/30 00:08
→
01/30 00:09,
AVL/R-B delete：[DS]2 Rotation [Algo]3 Rotation
01/30 00:09
→
01/30 00:10,
因為上課的時候R-B tree是用[Algo]的定義，所以感覺用
01/30 00:10
→
,
[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指標如何調整即可 是否有更快的方法 ?
→
01/29 23:10,
NTUEE 103 DS 用 兩個priority queue
01/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
→
01/29 22:40, , 1F
NCU 101 II 3(c) 感覺加進T中做Mst就可以
01/29 22:40, 1F
→
01/29 22:40, , 2F
不過應該也無法變成線性頂多VlogV
01/29 22:40, 2F
推
01/29 23:08, , 3F
RB和AVL的cost都是O(lg n)，但是旋轉次數不同。
01/29 23:08, 3F
→
01/29 23:09, , 4F
插入都只要O(1)旋轉 (你可以自己算出裡面的constant是多少
01/29 23:09, 4F
→
01/29 23:09, , 5F
AVL在刪除的時候需要O(lg n)旋轉，但是RB Tree只需要O(1)
01/29 23:09, 5F
→
01/29 23:10, , 6F
NCU 101 II 3(c) 可以在O(|V|)時間內完成 但是有點複雜..
01/29 23:10, 6F
→
01/29 23:10, , 7F
雖然技巧不難 但是要把這些都combine起來不容易..
01/29 23:10, 7F
→
01/29 23:10, , 8F
NTUEE 103 DS 用 兩個priority queue
01/29 23:10, 8F
→
01/29 23:11, , 9F
3(a)(b) 用disjoint set應該可以在O(lg*n)完成..
01/29 23:11, 9F
推
01/30 00:08, , 10F
AVL/R-B insert：[DS]1 Rotation [Algo]2 Rotation
01/30 00:08, 10F
→
01/30 00:09, , 11F
AVL/R-B delete：[DS]2 Rotation [Algo]3 Rotation
01/30 00:09, 11F
→
01/30 00:10, , 12F
因為上課的時候R-B tree是用[Algo]的定義，所以感覺用
01/30 00:10, 12F
→
01/30 00:11, , 13F
[Algo]的答案可能會好一點(我猜的XD)
01/30 00:11, 13F
謝謝大家回覆 想補問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
推
01/30 08:10, , 14F
那上面97 11(d) 說AVL insert 最多需兩次rotation是錯
01/30 08:10, 14F
→
01/30 08:10, , 15F
的耶？
01/30 08:10, 15F
推
01/30 10:29, , 16F
想問一下為什麼插入的複雜度是O(1),不是有可能調到很上
01/30 10:29, 16F
→
01/30 10:29, , 17F
面的父點嗎？還是這是平均後的複雜度
01/30 10:29, 17F
推
01/30 10:42, , 18F
101 3（c）我的想法把原來每個點都設值，值是連到他的
01/30 10:42, 18F
→
01/30 10:42, , 19F
邊中cost最小的，插入x後先選最小的邊跟原圖相連，再檢
01/30 10:42, 19F
→
01/30 10:42, , 20F
查每個點連到x的cost是否小於點上記錄的值，若是就換掉
01/30 10:42, 20F
→
01/30 10:42, , 21F
。不過設值的步驟好像不是linear…
01/30 10:42, 21F
→
01/30 11:18, , 22F
圓的那題 想法跟原po一樣 頂多設set的最大最小xy 可以
01/30 11:18, 22F
→
01/30 11:18, , 23F
減少一些搜尋但仍為O(n)
01/30 11:18, 23F
推
01/30 12:43, , 24F
為什麼圓形那堤(a)可以O(n)? 就算用set還是每次都要跟每個
01/30 12:43, 24F
→
01/30 12:44, , 25F
圓形檢查是否交集不是嗎@@?
01/30 12:44, 25F
謝謝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
推
01/30 20:13, , 26F
我好像了解了,我想成插入之後要往上搜尋從哪個父點開始
01/30 20:13, 26F
→
01/30 20:13, , 27F
不平衡,rotation好像沒指這段過程?
01/30 20:13, 27F
→
01/30 20:36, , 28F
嗯 我感覺它是要考這個
01/30 20:36, 28F
推
01/30 20:58, , 29F
NTUEE 103 3(a)(b) 應該不用判斷都交集吧 只要有一個交集
01/30 20:58, 29F
→
01/30 20:59, , 30F
就可以union不是嗎？
01/30 20:59, 30F
A C |---------| |----| |-----| B Disjoint Set: A ↑ B 這樣的話當C加入時需要判斷要不要和A做Union , 如果C只和A做是否相交的判斷會出錯 ※ 編輯: qoojordon (59.115.64.42), 01/30/2015 21:16:49
推
01/30 21:26, , 31F
我搞笑了..
01/30 21:26, 31F
推
01/30 21:30, , 32F
NTUEE 103 3(a) 可以用plane sweep 類似線段相交的方法
01/30 21:30, 32F
推
01/30 22:00, , 33F
NTUEE 103 3(b) 要先把circle建資料結構 像是kd-tree..
01/30 22:00, 33F
→
01/30 22:02, , 34F
[NCU 101 II 3(c)] 是基於Boruvka's algorithm..
01/30 22:02, 34F
→
01/30 22:26, , 35F
線段樹....而且還二維...加上disjoint..這也太難...已
01/30 22:26, 35F
→
01/30 22:26, , 36F
經是比賽題了
01/30 22:26, 36F
推
01/30 22:55, , 37F
因為之前寫題目的時候也有遇到最多rotation次數的問題
01/30 22:55, 37F
→
01/30 22:56, , 38F
所以我就跑去問洪逸說AVL跟R-B的插入跟刪除最多會有幾
01/30 22:56, 38F
→
01/30 22:57, , 39F
次rotation，結果他就跟我說是那樣，AVL插入上課有講
01/30 22:57, 39F
→
01/30 22:59, , 40F
[DS]跟[Algo]跟別是1跟2，但其他因為都沒講過，所以我
01/30 22:59, 40F
→
01/30 22:59, , 41F
就硬背了@@
01/30 22:59, 41F
推
01/30 23:02, , 42F
不過cost應該是O(logn)沒問題
01/30 23:02, 42F
推
01/31 00:54, , 43F
AVL刪除會有 O(lg n) rotation
01/31 00:54, 43F
→
01/31 00:54, , 44F
你要先建立起一個n個node 最高高度的AVL tree 然後刪除
01/31 00:54, 44F
→
01/31 00:55, , 45F
你就會發現你需要O(lg n)次旋轉才可以rebalance..
01/31 00:55, 45F
推
01/31 20:56, , 46F
可以順便問一下 NTUEE 103 2(b)(c)嗎?
01/31 20:56, 46F
推
02/01 08:58, , 47F
樓上c小題可以參考這份投影片第32頁之後
02/01 08:58, 47F
→
02/01 08:58, , 48F
02/01 08:58, 48F
推
02/01 15:19, , 49F
感謝樓上 來研究一下
02/01 15:19, 49F
推
02/03 03:02, , 50F
推
02/03 03:02, 50F
推
02/12 23:33, , 51F
NTUEE 103 3(b) 我發現其實就是計算 power diagram..
02/12 23:33, 51F
‣ 更多 qoojordon 的文章
文章代碼(AID): #1KoZwfmg (Grad-ProbAsk)