? ? ? ?紅黑樹的插入可在O(lg n)完成，紅黑樹的插入類似于二叉搜索樹的插入，為了盡量維護(hù)紅黑樹的性質(zhì)，將插入的新節(jié)點(diǎn)標(biāo)記為RED，然后調(diào)用RB-INSERT-FIXUP對紅黑樹的性質(zhì)進(jìn)行維護(hù)，RB-INSERT代碼如下：

?

RB-INSERT(T,z)????????

?????? y = T.nil??????????????

?????? x = T.root?????????????

?????? while x != T.nil???????

????????????? y = x??????????????????

????????????? if z.key < x.key???????

???????????????????? x = x.left?????????????

????????????? else x = x.right???????

?????? z.p = y???

????????????

?????? if y == T.nil??????????

???????????? T.root= z????????????

????? else ?if ?z.key < y.key??

???????????? y.left= z????????????

????? else ?y.right = z??

???

????? z.left = T.nil????????

????? z.right = T.nil???????

????? z.color = RED?????

???

?? ? ??RB-INSERT-FIXUP(T, z)?

?

?????? RB-INSERT-FIXUP負(fù)責(zé)在插入之后，維護(hù)紅黑樹的性質(zhì)，代碼如下：

RB-INSERT-FIXUP(T,z)????????????????

?????? while z.p.color == RED???????????????

????????????? if z.p == z.p.p. left????????????????

???????????????????? y = z.p.p.right??????????????????????

???????????????????? if y.color == RED????????????????????

??????????????????????????? z.p.color = BLACK ????????????????? // case 1??????????

??????????????????????????? y.color = BLACK ? ? ? ? ? ? ? ? ? ? ?// case 1????????????

??????????????????????????? z.p.p.color = RED ?????????????????? // case 1??????????

??????????????????????????? z = z.p.p ???????????????????????????????? // case 1 ?

???????????????????? else?

? ? ???? ? ???? ? ???? ? ???if z == z.p.right???????????????

?????????????????????????? ? ? ???z= z.p ???????????????????????????????????? ? ? ???//case 3???????????????????

?????????????????????????? ? ? ???LEFT-ROTATE(T,z) ? ? ? ? ? ? ? ? ? ? ?// case 3???

?????

??????????????????? ? ? ???z.p.color= BLACK ? ? ? ? ? ? ? ? ? ? ? ? ? ? // case 2?????????

??????????????????? ? ? ???z.p.p.color= RED ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// case 2?????????

??????????????????? ? ? ???RIGHT-ROTATE(T,z.p.p) ??????????????? // case 2????

????? ? ? ???else(same as then clause with “right” and “l(fā)eft” exchanged)

????????????? ? ? ???y = z.p.p.left??????????????????????

????????????? ? ? ???if y.color == RED?????????????????? ??

???????????????????? ? ? ???z.p.color = BLACK ? ? ? ? ? ? ? ? ? ?// case 1??????????

???????????????????? ? ? ???y.color = BLACK ????????????????????? // case 1????????????

???????????????????? ? ? ???z.p.p.color = RED ?????????????????? // case 1??????????

???????????????????? ? ? ???z = z.p.p ???????????????????????????????? // case 1 ?

????????????? ? ? ???else?

? ? ???? ? ???? ? ???? ? ???if z == z.p.left???????????????

??????????????????? ? ? ???? ? ???z = z.p ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//case 3???????????????????

??????????????????? ? ? ???? ? ???RIGHT-ROTATE(T,z) ??????????????? // case 3???

?????

???????????? ? ? ???? ? ???z.p.color= BLACK ???????????????????????? // case2?????????

???????????? ? ? ???? ? ???z.p.p.color= RED ????????????????????????? // case2?????????

???????????? ? ? ???? ? ???LEFT-ROTATE(T,z.p.p) ?????????????????? // case 2?

?T.root.color = BLACK????????????????

?

?????? 對于新插入的結(jié)點(diǎn)z來說，因z的顏色為紅色，所以，性質(zhì)1,3,5都不會早到破壞，性質(zhì)2,4有可能被破壞。如果z是根節(jié)點(diǎn)，則破壞了性質(zhì)2，如果z的父節(jié)點(diǎn)為紅色，則破壞了性質(zhì)4。如果z的父節(jié)點(diǎn)z.p為黑色的話，則紅黑樹的性質(zhì)沒有發(fā)生改變。若z為根節(jié)點(diǎn)，則直接置root的color為BLACK即可。所以只考慮z的父節(jié)點(diǎn)為RED的情況。

?

?????? 根據(jù)z的父節(jié)點(diǎn)是左孩子或者右孩子的處理方法是對稱的，所以只考慮z的父節(jié)點(diǎn)是左孩子的情況（if z.p == z.p.p. left）。根據(jù)z的叔叔結(jié)點(diǎn)y的顏色不同，以及z所處的位置，分為以下三種情況：

?

1：z的叔叔結(jié)點(diǎn)y的顏色為RED，記為case1：

?????? 這種情況，不管z是左孩子，還是右孩子，都是同樣的處理方法：

z是右孩子

z是左孩子。

?????? 這種情況的處理代碼是：

??????????????????????????? z.p.color = BLACK ????????????????? // case 1??????????

??????????????????????????? y.color = BLACK ????????????????????? // case 1????????????

??????????????????????????? z.p.p.color = RED ?????????????????? // case 1??????????

??????????????????????????? z = z.p.p ???????????????????????????????? // case 1??

? ? ???得到下面的圖：

z是右孩子

z是左孩子

?

???? 這種情況就是把z的父節(jié)點(diǎn)和叔叔結(jié)點(diǎn)y都變成BLACK，然后z的祖父結(jié)點(diǎn)變?yōu)?/span>RED，然后使祖父結(jié)點(diǎn)成為新的z，繼續(xù)向上處理。

?????? 這種處理方式，各個分支的黑高沒有發(fā)生變化，同時維護(hù)了原紅色z的父節(jié)點(diǎn)為BLACK的性質(zhì)。

?????? 這樣處理之后，可以轉(zhuǎn)變?yōu)槭Ｏ碌那闆r2或者3的一種：

?

2：z的叔叔結(jié)點(diǎn)y的顏色為BLACK，z為左孩子，記為case2：

?????? 這種情況下， 因為z的父節(jié)點(diǎn)是RED，所以z的祖父節(jié)點(diǎn)是BLACK，如下圖：

?????? 這種情況下的調(diào)整代碼為：

???????????????????? z.p.color = BLACK ???????????????????????? // case 2?????????

??????????????????? z.p.p.color= RED ????????????????????????? // case 2?????????

??????????????????? RIGHT-ROTATE(T,z.p.p) ?

?????? 將z的父節(jié)點(diǎn)變?yōu)锽LACK，祖父節(jié)點(diǎn)變?yōu)镽ED，同時對祖父節(jié)點(diǎn)進(jìn)行右旋，得到下面的圖：

?????? 這種情況下，整個分支的黑高保持不變，同時內(nèi)部分支的黑高也維持了性質(zhì)5。同時，z的父節(jié)點(diǎn)不再是RED，所以退出循環(huán)。

3：z的叔叔結(jié)點(diǎn)y的顏色為BLACK，z為右孩子，記為case3：

?????? 這種情況與case2類似，如下圖;

?????? 這種情況下的調(diào)整代碼為：

??????????????????????????? z = z.p ???????????????????????????????????? // case 3???????????????????

?????????????????????????? LEFT-ROTATE(T, z) ?????????????????? // case 3?

調(diào)整后得到下面的圖：

?????? 調(diào)整后，各個分支的黑高沒有發(fā)生任何變化，同時，變成了與case2吻合的情況。

?

分析：

?????? n個結(jié)點(diǎn)的紅黑樹高度為O(lg n)，插入操作中，除了最后一步外，剩下的操作與二叉搜索樹的插入相同，也就是時間復(fù)雜度為O(lg n)。在RD-INSERT-FIXUP中，僅當(dāng)case1時，z才沿著樹上升，while循環(huán)才會重復(fù)執(zhí)行。所以while的重復(fù)次數(shù)為O(lgn)。如果是case2或者3，則while循環(huán)直接結(jié)束。所以，RB-INSERT的時間復(fù)雜度為O(lg n)。

?

轉(zhuǎn)載于:https://www.cnblogs.com/gqtcgq/p/7247233.html

總結(jié)

以上是生活随笔為你收集整理的算法导论笔记：13-02红黑树插入的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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