[理工] [資結]-紅黑樹

看板Grad-ProbAsk作者 (袋哥)時間14年前 (2010/02/26 01:12), 編輯推噓6(6推 0噓 22→)
留言28則, 5人參與, 最新討論串4/4 (看更多)
Which of the following statements about red-black tree is true? A. In a red black tree, every red node must have two black children. D. A red black tree with n nodes(including external) contain exactly (n+1)/2 external nodes E. The highest ratio of the number of red internal nodes to the number of black internal nodes is 2. 為什麼以上三個選項都是對的? 感謝~ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 219.85.86.89
推
02/26 01:14, , 1F
A 因為不能有連續紅結點存在所以如果有子點一定是黑的
02/26 01:14, 1F
→
02/26 01:15, , 2F
然後NULL也是為是黑色
02/26 01:15, 2F
→
02/26 01:19, , 3F
如果red node是leaf不一定成立
02/26 01:19, 3F
→
02/26 01:20, , 4F
感謝了解
02/26 01:20, 4F
推
02/26 01:22, , 5F
如果紅點是樹葉...那麼子樹為空也就是NULL那還是可以是為黑色
02/26 01:22, 5F
→
02/26 01:22, , 6F
所以這個選項是成立的
02/26 01:22, 6F
→
02/26 01:23, , 7F
剛好今天也有寫到這一題XDD印象特別深刻XDD
02/26 01:23, 7F
推
02/26 01:27, , 8F
D.我是用"外部節點=內部節點+1"去推的
02/26 01:27, 8F
→
02/26 01:30, , 9F
E.你可以舉3個node的紅黑樹來看,紅黑比例要最高的話
02/26 01:30, 9F
→
02/26 01:31, , 10F
就是父點為黑 2個子點為紅 所以就是2
02/26 01:31, 10F
→
02/26 01:52, , 11F
外部節點=內部節點+1 是什麼定理 ?
02/26 01:52, 11F
→
02/26 02:15, , 12F
他 external node 指的是 null ?
02/26 02:15, 12F
推
02/26 02:16, , 13F
外部節點個數=內部節點個數+1
02/26 02:16, 13F
→
02/26 02:17, , 14F
那那個外部節點指的是 null link 吧...
02/26 02:17, 14F
→
02/26 02:17, , 15F
我剛剛看還以為是leaf XD
02/26 02:17, 15F
→
02/26 02:19, , 16F
那這樣A也可以解釋了 red black tree 規定 null link 要
02/26 02:19, 16F
→
02/26 02:19, , 17F
是 black
02/26 02:19, 17F
→
02/26 02:19, , 18F
嗯嗯 是null link
02/26 02:19, 18F
→
02/26 02:20, , 19F
那就ok了... 有時候external node 是 leaf還是null很難分
02/26 02:20, 19F
推
02/26 09:31, , 20F
這哪間學校的阿~?
02/26 09:31, 20F
→
02/26 10:37, , 21F
98台大電機資結
02/26 10:37, 21F
→
02/26 11:08, , 22F
還是不懂 B. 外部節點=內部節點+1要除以2
02/26 11:08, 22F
→
02/26 11:27, , 23F
E=I+1 =>(等號兩邊同+I) E+I=I+I+1=>(E+I=n) n=2I+1
02/26 11:27, 23F
→
02/26 11:29, , 24F
=>(I=E-1代入) n=2(E-1)+1 => E=(n+1)/2
02/26 11:29, 24F
推
02/26 11:46, , 25F
對喔~~你要考台大電機~~超威XD
02/26 11:46, 25F
→
02/26 11:46, , 26F
聽說台大電機考古題出很多...不過錄取分數要240
02/26 11:46, 26F
→
02/26 11:49, , 27F
你說我嗎??我沒有考= =
02/26 11:49, 27F
→
02/26 12:05, , 28F
終於懂了，非常感謝
02/26 12:05, 28F
‣ 更多 stevenwin 的文章
文章代碼(AID): #1BXg-GFU (Grad-ProbAsk)
‣ 更多 stevenwin 的文章
文章代碼(AID): #1BXg-GFU (Grad-ProbAsk)