看电机丙的几个考古希望确认
[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.

NCU 101 II 3(c) 感觉加进T中做Mst就可以不过应该也无法变成线性顶多VlogV

RB和AVL的cost都是O(lg n)，但是旋转次数不同。插入都只要O(1)旋转 (你可以自己算出里面的constant是多少AVL在删除的时候需要O(lg n)旋转，但是RB Tree只需要O(1)NCU 101 II 3(c) 可以在O(|V|)时间内完成 但是有点复杂..虽然技巧不难 但是要把这些都combine起来不容易..NTUEE 103 DS 用 两个priority queue3(a)(b) 用disjoint set应该可以在O(lg*n)完成..

AVL/R-B insert：[DS]1 Ratation [Algo]2 RotationAVL/R-B delete：[DS]2 Ratation [Algo]3 Rotation因为上课的时候R-B tree是用[Algo]的定义，所以感觉用[Algo]的答案可能会好一点(我猜的XD)

那上面97 11(d) 说AVL insert 最多需两次rotation是错的耶？

想问一下为什么插入的复杂度是O(1),不是有可能调到很上面的父点吗？还是这是平均后的复杂度101 3（c）我的想法把原来每个点都设值，值是连到他的边中cost最小的，插入x后先选最小的边跟原图相连，再检查每个点连到x的cost是否小于点上记录的值，若是就换掉。不过设值的步骤好像不是linear…

圆的那题 想法跟原po一样 顶多设set的最大最小xy 可以减少一些搜寻但仍为O(n)

为什么圆形那堤(a)可以O(n)? 就算用set还是每次都要跟每个圆形检查是否交集不是吗@@?

我好像了解了,我想成插入之后要往上搜寻从哪个父点开始不平衡,rotation好像没指这段过程?

嗯 我感觉它是要考这个

NTUEE 103 3(a)(b) 应该不用判断都交集吧 只要有一个交集就可以union不是吗？我搞笑了..NTUEE 103 3(a) 可以用plane sweep 类似线段相交的方法NTUEE 103 3(b) 要先把circle建资料结构 像是kd-tree..[NCU 101 II 3(c)] 是基于Boruvka's algorithm..

线段树....而且还二维...加上disjoint..这也太难...已经是比赛题了

因为之前写题目的时候也有遇到最多rotation次数的问题所以我就跑去问洪逸说AVL跟R-B的插入跟删除最多会有几次rotation，结果他就跟我说是那样，AVL插入上课有讲[DS]跟[Algo]跟别是1跟2，但其他因为都没讲过，所以我就硬背了@@不过cost应该是O(logn)没问题

AVL删除会有 O(lg n) rotation你要先建立起一个n个node 最高高度的AVL tree 然后删除你就会发现你需要O(lg n)次旋转才可以rebalance..

可以顺便问一下 NTUEE 103 2(b)(c)吗?

楼上c小题可以参考这份投影片第32页之后http://goo.gl/D8SoAz

感谢楼上 来研究一下

推

NTUEE 103 3(b) 我发现其实就是计算 power diagram..