[理工] 資結 red black tree數題
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
→
01/20 12:28, , 1F
01/20 12:28, 1F
→
01/20 12:28, , 2F
01/20 12:28, 2F
→
01/20 12:29, , 3F
01/20 12:29, 3F
→
01/20 12:31, , 4F
01/20 12:31, 4F
→
01/20 12:32, , 5F
01/20 12:32, 5F
→
01/20 12:33, , 6F
01/20 12:33, 6F
→
01/20 12:34, , 7F
01/20 12:34, 7F
→
01/20 18:16, , 8F
01/20 18:16, 8F