本文就紅黑樹的插入操作進(jìn)行細(xì)致到每一個(gè)小步驟的解析。

1，成員變量

本紅黑樹使用了三叉鏈結(jié)構(gòu)，使用的時(shí)候尤其要記得處理指向父親的指針。

為何在節(jié)點(diǎn)的構(gòu)造函數(shù)中，默認(rèn)節(jié)點(diǎn)的顏色為紅色？

因?yàn)榭紤]到紅黑樹的性質(zhì)（對(duì)于每個(gè)結(jié)點(diǎn)，從該結(jié)點(diǎn)到其所有后代葉結(jié)點(diǎn)的簡(jiǎn)單路徑上，均 包含相同數(shù)目的黑色結(jié)點(diǎn)），所以設(shè)置為紅色是最為合理方便的，如果插入的時(shí)候會(huì)有連續(xù)的紅色節(jié)點(diǎn)，再做調(diào)整也很方便。

但是如果默認(rèn)為黑節(jié)點(diǎn)，就要做調(diào)整保證每個(gè)路徑上的黑節(jié)點(diǎn)相同，相比之下會(huì)很麻煩。

2，Insert函數(shù)的實(shí)現(xiàn)（分為各個(gè)細(xì)節(jié)討論）

2,1插入時(shí)，紅黑樹是否為空樹

考慮到此情況，要先判斷紅黑樹是否為空樹。

若是，進(jìn)行相關(guān)操作后return

若不是，向下進(jìn)行

2,2若不是空樹，迭代到樹的底部，并插入節(jié)點(diǎn)

不必?fù)?dān)心parent的空指針解引用問題，由于不是空樹，所以parent一定不會(huì)為nullptr。

2,3插入節(jié)點(diǎn)后，控制平衡

理論基礎(chǔ)：

理論：（我們先約定:cur為當(dāng)前節(jié)點(diǎn)，p為父節(jié)點(diǎn)，g為祖父節(jié)點(diǎn)，u為叔叔節(jié)點(diǎn)）

情況一： cur為紅，p為紅，g為黑，u存在且為紅

如下圖：

此圖是個(gè)抽象圖，代表著多種情況，帶省略號(hào)的長(zhǎng)方形表示一個(gè)未知的樹。

解決方法：

將p,u改為黑，g改為紅，然后把g當(dāng)成cur，繼續(xù)向上調(diào)整

如果g是根節(jié)點(diǎn)，調(diào)整完成后，需要將g改為黑色（其實(shí)只要在調(diào)整操作的最后將_root的顏色置為黑色就行，不必在每種情況下特殊處理）

如果g是子樹，g一定有雙親，且g的雙親如果是紅色，需要繼續(xù)向上調(diào)整。

——————————————————————————————————————

情況二： cur為紅，p為紅，g為黑，u不存在/u存在且為黑，且為單旋情況

如下圖：

如下圖：

解決方法：

p為g的左孩子，cur為p的左孩子，則進(jìn)行右單旋轉(zhuǎn)；相反，

p為g的右孩子，cur為p的右孩子，則進(jìn)行左單旋轉(zhuǎn)

p、g變色--p變黑，g變紅

旋轉(zhuǎn)函數(shù)：

1，左單旋

解釋：

要實(shí)現(xiàn)一個(gè)操作，往往有多種方法，函數(shù)的設(shè)計(jì)也有多種。

本人選擇將旋轉(zhuǎn)函數(shù)參數(shù)統(tǒng)一設(shè)置為要處理的兩個(gè)節(jié)點(diǎn)中處于上方的節(jié)點(diǎn)。

如圖：

于是，寫出代碼實(shí)現(xiàn)如下：

cur是node的右子節(jié)點(diǎn)，parent是node的父節(jié)點(diǎn)。

要特別注意，此時(shí)使用的是三叉鏈結(jié)構(gòu)，在鏈接節(jié)點(diǎn)的同時(shí)，一定不要忘記對(duì)_parent進(jìn)行處理

在對(duì)_parent進(jìn)行處理時(shí)，當(dāng)然也要注意_parenrt是否存在，所以我們還要判斷node是否為根節(jié)點(diǎn)，再進(jìn)行相關(guān)操作。

2，右單旋

分析同上，不在贅述。

如下圖：

代碼實(shí)現(xiàn)：

————————————————————————————————————————

在插播了左單旋和右單旋的實(shí)現(xiàn)后，繼續(xù)回來討論第三種情況

情況三：cur為紅，p為紅，g為黑，u不存在/u存在且為黑，且需要雙旋

有了以上基礎(chǔ)，此處直接上圖。

解決方法：

p為g的左孩子，cur為p的右孩子，則針對(duì)p做左單旋轉(zhuǎn)，再對(duì)g做右單旋轉(zhuǎn)；相反，

p為g的右孩子，cur為p的左孩子，則針對(duì)p做右單旋轉(zhuǎn)，再對(duì)g做左單旋轉(zhuǎn)。

將cur置為黑色，g置為紅色

代碼實(shí)現(xiàn)：

復(fù)用左單旋和右單旋即可。

代碼實(shí)現(xiàn)：

解釋：

整個(gè)循環(huán)結(jié)束的條件是parent不存在或者parent為黑色

并且不必?fù)?dān)心祖父是否存在，因?yàn)槿绻鹥arent && parent->_col == RED的話，

祖父節(jié)點(diǎn)一定存在，并且為黑色，因?yàn)閜arent為紅色節(jié)點(diǎn)，不可能是根節(jié)點(diǎn)。

如果是第一種情況的話，是需要迭代調(diào)整的：要將g的位置變?yōu)閏ur，繼續(xù)向上檢查。

而第二三種情況則不需要，因?yàn)樾D(zhuǎn)了之后，沒有對(duì)上層產(chǎn)生影響，所以可以在調(diào)整之后直接跳出

循環(huán)結(jié)束后，將_root置為黑色，保證結(jié)構(gòu)即可。