看電機丙的幾個考古希望確認
[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..