作者qoojordon (颖川琦)
看板Grad-ProbAsk
标题[资工] 97-103电机丙数题(RB,AVL),中央101 MST
时间Thu Jan 29 22:07:34 2015
看电机丙的几个考古希望确认
[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)?
1F：推 FRAXIS: RB和AVL的cost都是O(lg n)，但是旋转次数不同。01/29 23:08
2F：→ FRAXIS: 插入都只要O(1)旋转 (你可以自己算出里面的constant是多少01/29 23:09
3F：→ FRAXIS: AVL在删除的时候需要O(lg n)旋转，但是RB Tree只需要O(1)01/29 23:09
4F：推 HiltonCool: AVL/R-B insert：[DS]1 Rotation [Algo]2 Rotation 01/30 00:08
5F：→ HiltonCool: AVL/R-B delete：[DS]2 Rotation [Algo]3 Rotation01/30 00:09
6F：→ HiltonCool: 因为上课的时候R-B tree是用[Algo]的定义，所以感觉用01/30 00:10
7F：→ 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指标如何调整即可
是否有更快的方法 ?
8F：→ 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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1422540457.A.C2A.html
9F：→ killerw74: NCU 101 II 3(c) 感觉加进T中做Mst就可以 01/29 22:40
10F：→ killerw74: 不过应该也无法变成线性顶多VlogV 01/29 22:40
11F：推 FRAXIS: RB和AVL的cost都是O(lg n)，但是旋转次数不同。 01/29 23:08
12F：→ FRAXIS: 插入都只要O(1)旋转 (你可以自己算出里面的constant是多少 01/29 23:09
13F：→ FRAXIS: AVL在删除的时候需要O(lg n)旋转，但是RB Tree只需要O(1) 01/29 23:09
14F：→ FRAXIS: NCU 101 II 3(c) 可以在O(|V|)时间内完成 但是有点复杂.. 01/29 23:10
15F：→ FRAXIS: 虽然技巧不难 但是要把这些都combine起来不容易.. 01/29 23:10
16F：→ FRAXIS: NTUEE 103 DS 用 两个priority queue 01/29 23:10
17F：→ FRAXIS: 3(a)(b) 用disjoint set应该可以在O(lg*n)完成.. 01/29 23:11
18F：推 HiltonCool: AVL/R-B insert：[DS]1 Rotation [Algo]2 Rotation 01/30 00:08
19F：→ HiltonCool: AVL/R-B delete：[DS]2 Rotation [Algo]3 Rotation 01/30 00:09
20F：→ HiltonCool: 因为上课的时候R-B tree是用[Algo]的定义，所以感觉用 01/30 00:10
21F：→ 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
22F：推 winnie48: 那上面97 11(d) 说AVL insert 最多需两次rotation是错 01/30 08:10
23F：→ winnie48: 的耶？ 01/30 08:10
24F：推 galapous: 想问一下为什麽插入的复杂度是O(1),不是有可能调到很上 01/30 10:29
25F：→ galapous: 面的父点吗？还是这是平均後的复杂度 01/30 10:29
26F：推 galapous: 101 3（c）我的想法把原来每个点都设值，值是连到他的 01/30 10:42
27F：→ galapous: 边中cost最小的，插入x後先选最小的边跟原图相连，再检 01/30 10:42
28F：→ galapous: 查每个点连到x的cost是否小於点上记录的值，若是就换掉 01/30 10:42
29F：→ galapous: 。不过设值的步骤好像不是linear… 01/30 10:42
30F：→ killerw74: 圆的那题 想法跟原po一样 顶多设set的最大最小xy 可以 01/30 11:18
31F：→ killerw74: 减少一些搜寻但仍为O(n) 01/30 11:18
32F：推 kather: 为什麽圆形那堤(a)可以O(n)? 就算用set还是每次都要跟每个 01/30 12:43
33F：→ 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
34F：推 galapous: 我好像了解了,我想成插入之後要往上搜寻从哪个父点开始 01/30 20:13
35F：→ galapous: 不平衡,rotation好像没指这段过程? 01/30 20:13
36F：→ qoojordon: 嗯 我感觉它是要考这个 01/30 20:36
37F：推 FRAXIS: NTUEE 103 3(a)(b) 应该不用判断都交集吧 只要有一个交集 01/30 20:58
38F：→ 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
39F：推 FRAXIS: 我搞笑了.. 01/30 21:26
40F：推 FRAXIS: NTUEE 103 3(a) 可以用plane sweep 类似线段相交的方法 01/30 21:30
41F：推 FRAXIS: NTUEE 103 3(b) 要先把circle建资料结构 像是kd-tree.. 01/30 22:00
42F：→ FRAXIS: [NCU 101 II 3(c)] 是基於Boruvka's algorithm.. 01/30 22:02
43F：→ killerw74: 线段树....而且还二维...加上disjoint..这也太难...已 01/30 22:26
44F：→ killerw74: 经是比赛题了 01/30 22:26
45F：推 HiltonCool: 因为之前写题目的时候也有遇到最多rotation次数的问题 01/30 22:55
46F：→ HiltonCool: 所以我就跑去问洪逸说AVL跟R-B的插入跟删除最多会有几 01/30 22:56
47F：→ HiltonCool: 次rotation，结果他就跟我说是那样，AVL插入上课有讲 01/30 22:57
48F：→ HiltonCool: [DS]跟[Algo]跟别是1跟2，但其他因为都没讲过，所以我 01/30 22:59
49F：→ HiltonCool: 就硬背了@@ 01/30 22:59
50F：推 HiltonCool: 不过cost应该是O(logn)没问题 01/30 23:02
51F：推 FRAXIS: AVL删除会有 O(lg n) rotation 01/31 00:54
52F：→ FRAXIS: 你要先建立起一个n个node 最高高度的AVL tree 然後删除 01/31 00:54
53F：→ FRAXIS: 你就会发现你需要O(lg n)次旋转才可以rebalance.. 01/31 00:55
54F：推 hyc1227: 可以顺便问一下 NTUEE 103 2(b)(c)吗? 01/31 20:56
55F：推 winnie48: 楼上c小题可以参考这份投影片第32页之後 02/01 08:58
57F：推 hyc1227: 感谢楼上 来研究一下 02/01 15:19
58F：推 NTPU5566Kobe: 推 02/03 03:02
59F：推 FRAXIS: NTUEE 103 3(b) 我发现其实就是计算 power diagram.. 02/12 23:33