[理工] [DS]紅黑樹觀念問題

[TNC (code)]

http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/098/098398.pdf
98台大電機丙 15(e)
我認為這是錯的因為可以找到反例
          33
        /    \
       27     45
      /  \    / \
     15  30   39 47
              / \
             36  40
              \
              37
這樣一棵red black tree 紅黑點的比例就超過2了

http://www.lib.ntu.edu.tw/exam/graduate/96/96412.pdf
96台大電機丙 14(e)
手邊解答有選e 但我可以找到反例
因為red black tree，在rotation時是因為遇到連續兩個red
而不是因為balance factor的關係，所以應該不能選
反例也可以用上面那個

大家覺得呢?

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.58.22
※ 編輯: TNC             來自: 122.116.58.22        (12/20 19:47)
推 louis719:98那題你畫的是紅黑數沒錯  但實際上你用紅黑樹的方法去
→ louis719:insert是沒辦法畫出那種樹的...我猜他要問的是這個
→ Byzantin:它是問red/black
→ TNC:1F實際上是可以的，因為我有做到一個題目答案就是這樣
→ TNC:所以96那題是false嗎
推 whenisawu:第一題你題意搞錯了吧@@"