紅黑樹(shù)的性質(zhì)：

性質(zhì)1：每個(gè)節(jié)點(diǎn)要么是黑色，要么是紅色。

• 性質(zhì)2：根節(jié)點(diǎn)是黑色。
• 性質(zhì)3：每個(gè)葉子節(jié)點(diǎn)（NIL）是黑色。
• 性質(zhì)4：每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)一定都是黑色。不能有兩個(gè)紅色節(jié)點(diǎn)相連。
• 性質(zhì)5：任意一節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)的路徑都包含數(shù)量相同的黑結(jié)點(diǎn)。俗稱(chēng)：黑高！
• 從性質(zhì)5又可以推出：性質(zhì)5.1：如果一個(gè)節(jié)點(diǎn)存在黑子節(jié)點(diǎn)，那么該結(jié)點(diǎn)肯定有兩個(gè)子節(jié)點(diǎn)

總結(jié)：
根節(jié)點(diǎn)必黑，新增是紅色，只能黑連黑，不能紅連紅

紅黑樹(shù)的操作：

紅黑樹(shù)能自平衡，它靠的三種操作：左旋、右旋和變色。
1.變色：結(jié)點(diǎn)的顏色由紅變黑或由黑變紅。
2.左旋：以某個(gè)結(jié)點(diǎn)作為支點(diǎn)(旋轉(zhuǎn)結(jié)點(diǎn))，其右子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)，右子結(jié)點(diǎn)的左子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的右子結(jié)點(diǎn)，左子結(jié)點(diǎn)保持不變。

3.右旋：以某個(gè)結(jié)點(diǎn)作為支點(diǎn)(旋轉(zhuǎn)結(jié)點(diǎn))，其左子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)，左子結(jié)點(diǎn)的右子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的左子結(jié)點(diǎn)，右子結(jié)點(diǎn)保持不變

紅黑樹(shù)插入節(jié)點(diǎn)情景分析

情景1：紅黑樹(shù)為空樹(shù)
最簡(jiǎn)單的一種情景，直接把插入結(jié)點(diǎn)作為根結(jié)點(diǎn)就行
注意：根據(jù)紅黑樹(shù)性質(zhì)2：根節(jié)點(diǎn)是黑色。還需要把插入結(jié)點(diǎn)設(shè)為黑色。

情景2：插入結(jié)點(diǎn)的Key已存在
處理：更新當(dāng)前節(jié)點(diǎn)的值，為插入節(jié)點(diǎn)的值

情景3：插入結(jié)點(diǎn)的父結(jié)點(diǎn)為黑結(jié)點(diǎn)
由于插入的結(jié)點(diǎn)是紅色的，當(dāng)插入結(jié)點(diǎn)的黑色時(shí)，并不會(huì)影響紅黑樹(shù)的平衡，直接插入即可，無(wú)需做自平衡。

情景4：插入節(jié)點(diǎn)的父節(jié)點(diǎn)為紅色
再次回想下紅黑樹(shù)的性質(zhì)2：根結(jié)點(diǎn)是黑色。如果插入節(jié)點(diǎn)的父結(jié)點(diǎn)為紅結(jié)點(diǎn)，那么該父結(jié)點(diǎn)不可能為根結(jié)點(diǎn)，所以插入結(jié)點(diǎn)總是存在祖父結(jié)點(diǎn)。
這一點(diǎn)很關(guān)鍵，因?yàn)楹罄m(xù)的旋轉(zhuǎn)操作肯定需要祖父結(jié)點(diǎn)的參與

插入情景4.1：叔叔結(jié)點(diǎn)存在并且為紅結(jié)點(diǎn)
依據(jù)紅黑樹(shù)性質(zhì)4可知，紅色節(jié)點(diǎn)不能相連 ==> 祖父結(jié)點(diǎn)肯定為黑結(jié)點(diǎn)；
因?yàn)椴豢梢酝瑫r(shí)存在兩個(gè)相連的紅結(jié)點(diǎn)。那么此時(shí)該插入子樹(shù)的紅黑層數(shù)的情況是：黑紅紅。顯然最簡(jiǎn)單的處理方式是把其改為：紅黑紅
處理：
1.將P和U節(jié)點(diǎn)改為黑色
2.將PP改為紅色
3.將PP設(shè)置為當(dāng)前節(jié)點(diǎn)，進(jìn)行后續(xù)處理

插入情景4.2：叔叔結(jié)點(diǎn)不存在或?yàn)楹诮Y(jié)點(diǎn)，并且插入結(jié)點(diǎn)的父親結(jié)點(diǎn)是祖父結(jié)點(diǎn)的左子結(jié)點(diǎn)
注意：單純從插入前來(lái)看，叔叔節(jié)點(diǎn)非紅即空（NIL節(jié)點(diǎn)），否則的話(huà)破壞了紅黑樹(shù)性質(zhì)5，此路徑會(huì)比其它路徑多一個(gè)黑色節(jié)點(diǎn)。

插入情景4.2.1：新插入節(jié)點(diǎn)，為其父節(jié)點(diǎn)的左子節(jié)點(diǎn)（LL紅色情況）
處理：
1.變顏色：將P設(shè)置為黑色，將PP設(shè)置為紅色
2.對(duì)PP節(jié)點(diǎn)進(jìn)行右旋

插入情景4.2.2：新插入節(jié)點(diǎn)，為其父節(jié)點(diǎn)的右子節(jié)點(diǎn)（LR紅色情況）
處理：
1.對(duì)P進(jìn)行左旋
2.將P設(shè)置為當(dāng)前節(jié)點(diǎn)，得到LL紅色情況
3.按照LL紅色情況處理（1.變顏色 2.右旋PP）

插入情景4.3：叔叔結(jié)點(diǎn)不存在或?yàn)楹诮Y(jié)點(diǎn)，并且插入結(jié)點(diǎn)的父親結(jié)點(diǎn)是祖父結(jié)點(diǎn)的右子結(jié)點(diǎn)
處理：
1.變顏色：將P設(shè)置為黑色，將PP設(shè)置為紅色
2.對(duì)PP節(jié)點(diǎn)進(jìn)行左旋

插入情景4.3.2：新插入節(jié)點(diǎn)，為其父節(jié)點(diǎn)的左子節(jié)點(diǎn)（RL紅色情況）
處理：
1.對(duì)P進(jìn)行右旋
2.將P設(shè)置為當(dāng)前節(jié)點(diǎn)，得到RR紅色情況
3.按照RR紅色情況處理（1.變顏色 2.左旋PP）

總結(jié)

爸叔通紅就變色，爸紅叔黑就旋轉(zhuǎn)，哪邊黑往哪邊轉(zhuǎn)。

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的红黑树分析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。