推 shenevol:網路上不是有紅黑樹動畫嗎XDDD 建議原原PO可以去看看喔 10/01 22:22
推 da0910cc: 10/03 17:21
※ 引述《showyoulovex (NONO)》之銘言：
: 依序建立 2.7.8.1.5.6.4.3
: 這題看過紅黑樹定義 也看過前面人家問的
: 建立起來還是有問題...尤其是紅紅該怎樣旋轉總是會有問題
: 麻煩大大 能夠解說一下過程
: 我自己的答案就不放上來的了..因為建立到中後半就開始錯了
以下我加上""代表紅色 rotation操作就直接照定義做囉
首先
插入新點 "2" 又因為"2"是root一定要是黑色 所以再轉成黑色 2
插入新點 "7" 和 "8" 變成 2 2這個點會有RR連續紅點 所以要做rotation處理
\ R
"7"
\ R
"8"
變成 7
/ \
"2" "8"
再插入新點"1" 但因為7這個點有兩個子點為紅色 所以先作color change才能插
再變成 "7" 因為root必為黑色 又變成 7
/ \ / \
2 8 2 8
插入新點"1"再變成 7
/ \
2 8
/
"1"
再插入新點"5"變成 7
/ \
2 8
/ \
"1" "5"
再插入新點"6" 因為2這個點有兩個子點為紅色 要先作color change才能插
變成 7 再插入新點"4"變成 7
/ \ / \
"2" 8 "2" 8
/ \ / \
1 5 1 5
\ / \
"6" "4" "6"
再插入新點"3" 因為5這個點有兩個子點為紅色 要先做color change才能插
變成 7 又7這個點會有LR連續紅點 還要再做ratation處理才能插"3"
L/ \
"2" 8
/ \R
1 "5"
/ \
4 6
變成 5 (其中孤兒4和6是按照BST順序放)
/ \
"2" "7"
/ \ / \
1 4 6 8
最後插入新點"3"才變成 5
/ \
"2" "7"
/ \ / \
1 4 6 8
/
"3"
以上就是最後結果(累...)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.57.123.227
※ 編輯: liataian 來自: 61.57.123.227 (10/01 07:53)
※ 編輯: liataian 來自: 61.57.123.227 (10/01 08:22)
※ 編輯: liataian 來自: 61.57.123.227 (10/01 08:33)
※ 編輯: liataian 來自: 61.57.123.227 (10/01 08:46)
※ 編輯: liataian 來自: 61.57.123.227 (10/01 08:48)