作者want0417 (生活像隻貓)
看板Grad-ProbAsk
標題[理工] [資結]-紅黑樹與2-3-4樹問題
時間Fri Feb 12 21:18:24 2010
台北大學95年資結
有一題建置紅黑樹
樹列為
7 9 13 5 11 4 3 2 1 10 17
小弟的步驟
9 9 9 9 5
/ \ / \ / \ / \ / \
7R 13R 7 13 5R 13 5R 13 3 9
/ / / \ / / \ / --> / \ / \
5R 11R 4 7 11R 3R 7 11R 2 4 7 13
/ \ / /
2 4 1R 11R
5 5
/ \ / \
3 9 3 11
/ \ / \ / \ / \
2 4 7 11 2 4 9 13
/ / \ / / \ \
1R 10R 13R 1R 7R 10R 17R
請問一下這樣的步驟對嗎?
比較有問題是轉換那邊 3和9 是R還是直接變成黑就好?
另外可以用2-3-4樹來建立 這樣出來的樹應該不唯一吧?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.255.147.21
1F：→ ntust661:我還以為是紅樹林=..= 02/12 21:20
2F：推 taitin:3跟9都紅色 02/12 21:25
3F：→ taitin:rotation的時候，兩個子都是紅色 02/12 21:25
4F：→ want0417:所以大大 我只要注意轉的時候3和9都變成紅色 02/12 21:32
5F：→ want0417:那這步驟就沒錯? 02/12 21:32
6F：→ taitin:最後一步好像有影響，插入17那個 02/12 21:34
7F：→ want0417:請問大大 最後是變成? 能用水球或是其他方式交一下嗎? 02/12 21:40
8F：→ taitin:我回文喔，請稍候 02/12 21:44