紅黑樹的定義和插入在紅黑樹的實現(xiàn)（一）中已經(jīng)描述和實現(xiàn)了，下面說一下紅黑樹的刪除。

　　紅黑樹的刪除也包括兩個步驟：

　　1.刪除結(jié)點

　　2.調(diào)整樹滿足紅黑樹的定義

　　首先是刪除一個結(jié)點，同樣可以按二叉排序樹的刪除結(jié)點來刪除。刪除結(jié)點又分為4中情況：

　　（1）刪除結(jié)點沒有左孩子，有右孩子

　　（2）刪除結(jié)點沒有右孩子，有左孩子

　　（3）刪除結(jié)點為葉子結(jié)點

　　（4）刪除結(jié)點既有左孩子又有右孩子

　　對于情況（1），可以直接用右孩子代替刪除的結(jié)點，并且由于刪除結(jié)點有右孩子，所以刪除結(jié)點必定為黑色，右孩子必定為紅色（假設(shè)刪除結(jié)點為紅色，右孩子必定為黑色，這樣是違反紅黑樹定義4的，所以刪除結(jié)點必定為黑色，同理右孩子必定為紅色），因此只要把右孩子著為黑色，紅黑樹依然沒有違反定義。對于情況（2），與情況（1）相同，只是把右孩子換成左孩子。對于情況（3），可以直接刪除結(jié)點，不過如果該刪除的結(jié)點為黑色，刪除后會違反定義4，所以必須進行調(diào)整。對于情況（4），可以轉(zhuǎn)換為前三種情況，因為可以用刪除結(jié)點在中序排序中的后繼結(jié)點代替該刪除結(jié)點，相當(dāng)于刪除的是后繼結(jié)點，而后繼結(jié)點屬于前面三種情況的一種。代碼如下：

?

1 rb_node_t *rb_erase_node(rb_node_t *node, rb_node_t **root) 2 { 3 rb_node_t *replace, *p; 4 5 if (NULL == node) 6 return NULL; 7 if (NULL == node->lchild) 8 { 9 /*左孩子為空,直接用右孩子代替node*/ 10 replace = node->rchild; 11 p = node->parent; 12 if (replace) 13 { 14 replace->parent = p; 15 replace->color = BLACK; 16 } 17 else if (BLACK == node->color) 18 rb_erase_fix_node(node, root);/*注意這里*/ 19 if (NULL == p) 20 *root = replace; 21 else if (node == p->lchild) 22 p->lchild = replace; 23 else 24 p->rchild = replace; 25 } 26 else if (NULL == node->rchild) 27 { 28 /*右孩子為空,且左孩子不為空*/ 29 replace = node->lchild; 30 p = node->parent; 31 replace->parent = p; 32 replace->color = BLACK; 33 rebalance = NULL; 34 if (NULL == p) 35 *root = replace; 36 else if (node == p->lchild) 37 p->lchild = replace; 38 else 39 p->rchild = replace; 40 } 41 else 42 { 43 /*左右孩子均不為空*/ 44 replace = rb_next(node); 45 key_copy(node, replace); 46 info_copy(node, replace); 47 node = replace; 48 /*左孩子為空*/ 49 replace = node->rchild; 50 p = node->parent; 51 if (replace) 52 { 53 replace->parent = p; 54 replace->color = BLACK; 55 } 56 else if (BLACK == node->color) 57 rb_erase_fix_node(node, root);/*注意這里*/ 58 if (node == p->lchild) 59 p->lchild = replace; 60 else 61 p->rchild = replace; 62 } 63 return node; 64 }

?

?

　　現(xiàn)在我們來看調(diào)整。刪除結(jié)點后真正需要調(diào)整的是遇到情況3，想想刪除一個結(jié)點會違反紅黑樹的哪些定義呢？很有很能是違反第4條定義，因為可能會刪除一個顏色為黑色的結(jié)點。紅黑樹的調(diào)整總共包括8種情況，和插入調(diào)整情況一樣，其實就是4種，另外四種都是對稱的，這里就只討論刪除結(jié)點為父結(jié)點左孩子的情況，將刪除結(jié)點作為調(diào)整結(jié)點。情況（1）調(diào)整結(jié)點的兄弟為紅色，那么父結(jié)點必定為黑色，將父結(jié)點設(shè)置為紅色，兄弟結(jié)點設(shè)置為黑色，左旋父結(jié)點，這樣就轉(zhuǎn)化為了情況2；情況（2）調(diào)整結(jié)點的兄弟為黑色。情況（2）中可以分成三種情況討論，即情況（2-1）兄弟結(jié)點的左右孩子均為黑色，這種情況可以直接設(shè)置兄弟結(jié)點顏色為紅色，將調(diào)整結(jié)點設(shè)置為父親結(jié)點；情況（2-2）兄弟結(jié)點的左孩子為紅色，右孩子為黑色，將兄弟結(jié)點設(shè)置為紅色，兄弟結(jié)點的左孩子設(shè)置為黑色，右旋兄弟結(jié)點轉(zhuǎn)換為情況（2-3）；兄弟結(jié)點的右孩子為紅色，將兄弟結(jié)點的右孩子設(shè)置為黑色，兄弟結(jié)點的顏色設(shè)置為父結(jié)點的顏色，父結(jié)點設(shè)置為黑色，左旋父結(jié)點，這樣就已經(jīng)調(diào)整好了。這里要注意的就是調(diào)整完之后要將刪除結(jié)點徹底的從樹中刪除，調(diào)整時由于調(diào)整的需要，并沒有把結(jié)點從樹上刪除（算法導(dǎo)論用了一個叫NIL的結(jié)點作為了替代，所以直接刪除了結(jié)點，這是實現(xiàn)細節(jié)，對于理解整個的調(diào)整沒有什么影響的）；還有就是如果兄弟結(jié)點的孩子右不錯字的情況，要特別小心，自己就是沒有考慮全部的情況，所以總是段錯誤，后來調(diào)試發(fā)現(xiàn)是空指針異常了。

?

static void rb_erase_fix_node(rb_node_t *node, rb_node_t **root) {rb_node_t *p, *s, *sl, *sr;while (node != *root && node->color == BLACK){p = node->parent;if (node == p->lchild) {/*node為左孩子*/ s = p->rchild;/*s必定不為空*/if (RED == s->color){/*情況1：node的兄弟為紅色,設(shè)置p為紅色，s為黑色，左旋p，轉(zhuǎn)換為情況2* P S* / \ / \* n? s --> p SR* / \ / \* SL SR n? SL* */p->color = RED;s->color = BLACK;rb_rotate_left(p, s);if (NULL == s->parent)*root = s;}else {sl = s->lchild;sr = s->rchild;if (NULL == sl && NULL == sr || sl && BLACK == sl->color && sr && BLACK == sr->color){/*情況2：node的兄弟為黑色,設(shè)置s設(shè)為紅色,node設(shè)置為p* p? p?* / \ / \* n? S --> n? s* / \ / \* SL SR SL SR* */s->color = RED;node = p;}else if ((NULL == sr || sr && BLACK == sr->color) && sl && RED == sl->color){ /*情況3：node的兄弟的右孩子為黑色,左孩子為紅色,設(shè)置sl設(shè)為黑色,s設(shè)置為紅色,右旋s* p? p?* / \ / \* n? S --> n? SL* / \ \* sl SR s* \* SR* */sl->color = BLACK;s->color = RED;rb_rotate_right(s, sl);if (NULL == sl->parent)*root = sl;}else{/*情況4：node的兄弟的右孩子為紅色,設(shè)置sr設(shè)為黑色,s設(shè)置為p的顏色,p設(shè)置為黑色,左旋p* p? s? * / \ / \* n? S --> P SR * \ / * sr n? * */sr->color = BLACK;s->color = p->color;p->color = BLACK;rb_rotate_left(p, s);if (NULL == s->parent) *root = s;node = *root;}}}else{/*node為右孩子*/ s = p->lchild;/*s必定不為空*/if (RED == s->color){/*情況1：node的兄弟為紅色,設(shè)置p為紅色，s為黑色，右旋p，轉(zhuǎn)換為情況2* P S* / \ / \* s n? --> p SR* / \ / \* SL SR SR n? * */p->color = RED;s->color = BLACK;rb_rotate_right(p, s);if (NULL == s->parent)*root = s;}else {sl = s->lchild;sr = s->rchild;if (NULL == sl && NULL == sr || sl && BLACK == sl->color && sr && BLACK == sr->color){/*情況2：node的兄弟的兩個孩子均為黑色,設(shè)置s設(shè)為紅色,node設(shè)置為p* p? p?* / \ / \* S n? --> s n? * / \ / \* SL SR SL SR* */s->color = RED;node = p;}else if ((NULL == sl || sl && BLACK == sl->color) && sr && RED == sr->color){ /*情況3：node的兄弟的左孩子為黑色,右孩子為紅色,設(shè)置sr設(shè)為黑色,s設(shè)置為紅色,左旋s* p? p?* / \ / \* S n? --> SR n? * / \ / * SL sr s * / * SL * */sr->color = BLACK;s->color = RED;rb_rotate_left(s, sr);if (NULL == sr->parent)*root = sr;}else{/*情況4：node的兄弟的左孩子為紅色,設(shè)置sl設(shè)為黑色,s設(shè)置為p的顏色,p設(shè)置為黑色,右旋p* p? s? * / \ / \* S n? --> SL P * / \ * sl n? * */sl->color = BLACK;s->color = p->color;p->color = BLACK;rb_rotate_right(p, s);if (NULL == s->parent) *root = s;node = *root;}}}}node->color = BLACK; }

?附：紅黑色實現(xiàn)代碼

?

?

總結(jié)

以上是生活随笔為你收集整理的红黑树的实现（二）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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