作者wanedcol (草化)
看板Grad-ProbAsk
標題[理工] 資結 red black tree數題
時間Wed Jan 20 12:14:01 2016
1. after inserting a new nide to a red black tree , at most two rotations are
needed to re-balance the tree.
怎麽判斷這一類的題目?如果把tree弄的很大，不就可能會超過兩次?
換成AVLtree也一樣嗎？
2. red black tree has n internal node, the height most 2*log(n+1)
是只有在black height=2時，成立是嗎？怎麼證明
3.red black tree 當node=7時，可以全黑。
是at most嗎？
4. we cann't use dijkstra's to get min-cost spanning tree on connected directe
d graph
怎麼想都可以啊～why?
5.怎麼劃分clique
拜託各位大，矯正一下小弟我的觀念，感謝幫忙
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.217.6.76
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1453263244.A.CD9.html
※ 編輯: wanedcol (180.217.6.76), 01/20/2016 12:17:00
→ jerry031181: RBtree只保證任一點左右子樹高度差不超過2倍 不像AVL 01/20 12:28
→ jerry031181: 一樣要求樹高 RB tree 的旋轉只有一次 而AVL可能有 01/20 12:28
→ jerry031181: 2次以上 01/20 12:29
→ jerry031181: 2.沒什麼想法..從234tree轉成RBtree確實樹高為2logn 01/20 12:31
→ jerry031181: CBT形式的RBtree7node可全黑 每條path都3個黑node 01/20 12:32
→ jerry031181: dijkstra是求SSSP的不是MST 求MST用Kruskal,prim 01/20 12:33
→ jerry031181: sollin； Clique為maximal complete subgraph 01/20 12:34
→ wanedcol: 萬分感謝j大 01/20 18:16