紅黑樹(shù)之插入實(shí)現(xiàn)

性質(zhì)

1. 紅黑樹(shù)的結(jié)點(diǎn)都是紅色或者黑色

2. 根結(jié)點(diǎn)是黑色

3. 所有葉子都是黑色（這里的葉子結(jié)點(diǎn)是空結(jié)點(diǎn)）

4. 每個(gè)紅色結(jié)點(diǎn)必須有兩個(gè)黑色的子結(jié)點(diǎn)

5. 從任何一個(gè)節(jié)點(diǎn)到其每個(gè)葉子的所有簡(jiǎn)單路徑都包含相同數(shù)目的黑色結(jié)點(diǎn)

• 性質(zhì)1和性質(zhì)3總是能夠保持著；

• 性質(zhì)4只有在這些情況下才會(huì)發(fā)生作用：

• 增加紅色結(jié)點(diǎn)

• 將黑色結(jié)點(diǎn)重新繪制成紅色結(jié)點(diǎn)

• 旋轉(zhuǎn)

• 性質(zhì)5在這些情況下才會(huì)發(fā)生作用：

• 增加黑色結(jié)點(diǎn)

• 將紅色結(jié)點(diǎn)重新繪制黑色結(jié)點(diǎn)

• 旋轉(zhuǎn)

舉例：

插入

用BST的方法將結(jié)點(diǎn)插入，將該結(jié)點(diǎn)標(biāo)記為紅色的（因?yàn)槿绻麡?biāo)記為黑色，則會(huì)導(dǎo)致根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑會(huì)多出一個(gè)黑結(jié)點(diǎn)，無(wú)法滿足性質(zhì)5，而且不容易進(jìn)行調(diào)整），插入的情況包括下面幾種：

1. 插入到一個(gè)空的樹(shù)，插入結(jié)點(diǎn)則為根結(jié)點(diǎn)，只需要將紅色結(jié)點(diǎn)重新轉(zhuǎn)染成黑色結(jié)點(diǎn)來(lái)滿足性質(zhì)2；

2. 新結(jié)點(diǎn)的父結(jié)點(diǎn)為黑色，滿足所有條件；

3. 新結(jié)點(diǎn)的父結(jié)點(diǎn)為紅色，因?yàn)樾再|(zhì)2和性質(zhì)4，所以樹(shù)必然有祖父結(jié)點(diǎn)，則又包括以下的情況：

1. 新插入結(jié)點(diǎn)為父親結(jié)點(diǎn)的左子結(jié)點(diǎn)，那么就構(gòu)成了一個(gè)左左的情況，在之前平衡樹(shù)中提到過(guò)，如果要將其進(jìn)行平衡，則需要對(duì)父結(jié)點(diǎn)進(jìn)行一次單右旋轉(zhuǎn)，形成一個(gè)父親結(jié)點(diǎn)為相對(duì)根結(jié)點(diǎn)，子結(jié)點(diǎn)和祖父結(jié)點(diǎn)為子結(jié)點(diǎn)的樹(shù)，同時(shí)將父親結(jié)點(diǎn)的紅色改為黑色，祖父結(jié)點(diǎn)更改為紅色，這下之前無(wú)法滿足的性質(zhì)4和性質(zhì)5就滿足了；

   

2. 新插入結(jié)點(diǎn)為父親結(jié)點(diǎn)的右子結(jié)點(diǎn)，那么就會(huì)構(gòu)成一個(gè)左右的情況，在之前的平衡樹(shù)也提到過(guò)要進(jìn)行一次雙旋轉(zhuǎn)，先對(duì)新結(jié)點(diǎn)進(jìn)行一次單左旋轉(zhuǎn)，變成了左左的結(jié)構(gòu)，再進(jìn)行一次單右旋轉(zhuǎn)，從而達(dá)到滿足所有性質(zhì)；

   

3. 父親結(jié)點(diǎn)和叔父結(jié)點(diǎn)均為紅色，顯然無(wú)法滿足性質(zhì)4，則將父親結(jié)點(diǎn)和叔父結(jié)點(diǎn)繪制成黑色，祖父結(jié)點(diǎn)設(shè)置成紅色，但是仍然無(wú)法滿足情況，比如考慮到祖父結(jié)點(diǎn)可能是根結(jié)點(diǎn)，則無(wú)法滿足性質(zhì)2，或者祖父結(jié)點(diǎn)的父結(jié)點(diǎn)是紅色的，則無(wú)法滿足性質(zhì)4，這時(shí)需要將祖父結(jié)點(diǎn)作為新的結(jié)點(diǎn)來(lái)看待進(jìn)行各種情況的判斷，涉及到對(duì)祖父結(jié)點(diǎn)的遞歸；

   

4. 父親結(jié)點(diǎn)為紅色同時(shí)叔父結(jié)點(diǎn)為黑色或者從缺，這里又分為

   網(wǎng)友評(píng)論

   更多精彩分享

   學(xué)習(xí)是年輕人改變自己的最好方式