作者taitin (小南)
看板Grad-ProbAsk
標題Re: [理工] [資結]-紅黑樹與2-3-4樹問題
時間Fri Feb 12 21:51:49 2010
※ 引述《want0417 (生活像隻貓)》之銘言：
: 台北大學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 9
/ \ / \ / \ / \
2 4 7 11 2 4 7 11
/ / \ / / \
1R 10R 13R 1 10 13
\
17
5
5 >>>>再改為黑
/ \ / \
3 9 3 9
/ \ / \ / \ / \
2 4 7
11 2 4 7
11
/ / \ / / \
1 10 13
1 10 13
\ \
17 17
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.216.170.130
1F：推 want0417:不是從9開始轉換? 是把10丟過去7那邊? 02/12 21:55
2F：→ taitin:還沒打完等下喔 02/12 21:56
※ 編輯: taitin 來自: 61.216.170.130 (02/12 22:03)
3F：推 want0417:OKOK 不好意思 麻煩您了= = 02/12 22:02
4F：推 want0417:那17不用轉換成AVL樹嗎? 直接掛著就好? 02/12 22:06
5F：→ taitin:紅黑樹不是AVL樹阿 02/12 22:08
6F：→ taitin:只要不紅紅相連，就不用改變 02/12 22:09
7F：推 want0417:恩恩~那我知道囉 感謝大大詳細的解釋~ 02/12 22:09
8F：推 EntHeEnd:剛剛弄錯了 感謝討論 02/12 23:11
9F：推 Nandesga:我建的樹root是9 rotation跟你們不太一樣... 02/12 23:23
10F：→ taitin:你可以畫出來嗎？ 02/12 23:27
11F：推 Nandesga:我再畫了一次 ~ 結果一樣了之前搞錯 感謝 02/13 00:31
12F：推 Nandesga:不過第三個圖的5應該是黑色 ~ 4和7是紅色 02/13 00:49
13F：→ taitin:第三個圖錯，結果第四個對了XD 02/13 00:53