作者ybite (小犬)
看板Grad-ProbAsk
標題Re: [理工] [DS] 紅黑樹的建立
時間Sun Feb 13 23:42:33 2011
※ 引述《christianSK (AG)》之銘言：
: 4 7 12 15 3 5 14 18
: Horowitz裡沒有從empty開始建立的過程
: 而我在一開始的地方遇到了點困難
: 在前三項插入之後 會變成怎麼樣呢? 4 7 12 都變成blcak嗎?
: 先謝謝大家~
請參考超好用Demo:
http://gauss.ececs.uc.edu/RedBlack/redblack.html
Insert就是「紅叔」和「黑叔」兩種情況
Figure
紅 黑 Leaf省略
Insert 4（沒點時第一個點直接塗黑）
4
Insert 7，塗紅
4
\
7
Insert 12，紅紅相連
檢查過後發現12的叔叔是黑的（葉子），做Rotation後重塗
4
\
7
\
12
↓
7
/ \
4 12
Insert 15，紅紅相連，15有紅叔，
重新塗色（父叔塗黑、爺爺塗紅），向上檢查
檢查到root後直接把root塗黑
7
/ \
4 12
\
15
↓
7
/ \
4 12
\
15
↓
7
/ \
4 12
\
15
Insert 3,5
7
/ \
4 12
/ \
3 15
Insert 5
7
/ \
4 12
/ \ \
3 5 15
Insert 14，紅紅相連，14有黑叔（葉子），做兩次Rotation+重塗（中間省略）
7
/ \
4 12
/ \ \
3 5 15
/
14
↓
7
/ \
4 12
/ \ \
3 5 14
\
15
↓
7
/ \
4 14
/ \ / \
3 5 12 15
Insert 18，紅紅相連，18有紅叔，重塗往上觀察
由於14塗紅後不會有紅紅相連，因此做完！
7
/ \
4 14
/ \ / \
3 5 12 15
\
18
↓
7
/ \
4 14
/ \ / \
3 5 12 15
\
18
----------------------------------------------
如果考紅黑樹的Deletion，我真的很想分數送給他...
紅兄、黑兄二黑姪、黑兄紅姪的雙黑處理超級世界無敵難記...
如果有心想搞懂請看最上面的Java Demo。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.127.176.48
※ 編輯: ybite 來自: 122.127.176.48 (02/13 23:42)
推 christianSK:謝謝!! 02/13 23:44
推 mqazz1:推用心 deletion的確有夠麻煩= =" 02/13 23:49
推 BenLinus:推! ^^ 02/13 23:56
→ cksh3300110:超用心~ 紅黑數刪除ORZ 02/14 00:03
推 death888:所以是只有黑叔的情況才需要rotation嗎 02/14 18:46
→ death888:還有INSERT 12那步的重新塗色是怎麼塗的 不太懂囧 02/14 18:47
→ robert527152:跟alv的rotate一樣，著色為root紅sub黑 02/14 19:11
推 death888:所以rotation與否跟黑叔沒關係囉 02/14 19:14
→ death888:那紅叔跟黑叔兩種情況的差別在哪 我看這例子看不太出來 02/14 19:15
推 BenLinus:有吧, insert時若有 red violation 就看叔叔的顏色來作處 02/14 19:33
→ BenLinus:理, 若是紅叔, 就recolor; 若是黑叔, 就要rotation才行 02/14 19:34
推 death888:那recolor的做法是什麼? 還有我看書上說兩個兒子不能為紅 02/14 19:40
→ death888:否則要做recolor 可是上面的例子並沒有考慮這情況? 02/14 19:41
推 BenLinus:應該是不能紅紅相接吧 @@ 可以有兩個紅子 02/14 19:43