[理工] [資結] - 紅黑樹 - 看板 Grad-ProbAsk

作者stevenwin (袋哥)

看板Grad-ProbAsk

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

時間Fri Feb 26 01:12:44 2010

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

推 quts:A 因為不能有連續紅結點存在所以如果有子點一定是黑的 02/26 01:14

→ quts:然後NULL也是為是黑色 02/26 01:15

→ stevenwin:如果red node是leaf不一定成立 02/26 01:19

→ stevenwin:感謝了解 02/26 01:20

推 quts:如果紅點是樹葉...那麼子樹為空也就是NULL那還是可以是為黑色 02/26 01:22

→ quts:所以這個選項是成立的 02/26 01:22

→ quts:剛好今天也有寫到這一題XDD印象特別深刻XDD 02/26 01:23

推 lightergogo:D.我是用"外部節點=內部節點+1"去推的 02/26 01:27

→ lightergogo:E.你可以舉3個node的紅黑樹來看,紅黑比例要最高的話 02/26 01:30

→ lightergogo:就是父點為黑 2個子點為紅所以就是2 02/26 01:31

→ EntHeEnd:外部節點=內部節點+1 是什麼定理 ? 02/26 01:52

→ EntHeEnd:他 external node 指的是 null ? 02/26 02:15

推 lightergogo:外部節點個數=內部節點個數+1 02/26 02:16

→ EntHeEnd:那那個外部節點指的是 null link 吧... 02/26 02:17

→ EntHeEnd:我剛剛看還以為是leaf XD 02/26 02:17

→ EntHeEnd:那這樣A也可以解釋了 red black tree 規定 null link 要 02/26 02:19

→ EntHeEnd:是 black 02/26 02:19

→ lightergogo:嗯嗯是null link 02/26 02:19

→ EntHeEnd:那就ok了... 有時候external node 是 leaf還是null很難分 02/26 02:20

推 polomoss:這哪間學校的阿~? 02/26 09:31

→ lightergogo:98台大電機資結 02/26 10:37

→ stevenwin:還是不懂 B. 外部節點=內部節點+1要除以2 02/26 11:08

→ lightergogo:E=I+1 =>(等號兩邊同+I) E+I=I+I+1=>(E+I=n) n=2I+1 02/26 11:27

→ lightergogo:=>(I=E-1代入) n=2(E-1)+1 => E=(n+1)/2 02/26 11:29

推 polomoss:對喔~~你要考台大電機~~超威XD 02/26 11:46

→ polomoss:聽說台大電機考古題出很多...不過錄取分數要240 02/26 11:46

→ lightergogo:你說我嗎??我沒有考= = 02/26 11:49

→ stevenwin:終於懂了，非常感謝 02/26 12:05