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

看板Grad-ProbAsk作者TNC (code)時間14年前 (2011/12/20 19:47)推噓2(2推 0噓 4→)

留言6則, 4人參與討論串1/1

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

12/20 20:15, , 1^F

12/20 20:15, 1^F

→

louis719

12/20 20:15, , 2^F

12/20 20:15, 2^F

→

Byzantin

12/20 20:18, , 3^F

12/20 20:18, 3^F