理解了上面大部分的邏輯之后，我們就可以開始去實(shí)現(xiàn)紅黑樹了，本文用C語(yǔ)言實(shí)現(xiàn)了2-3 B樹對(duì)應(yīng)的左斜紅黑樹。

4.1 結(jié)構(gòu)體定義

首先我們要定義紅黑樹的結(jié)構(gòu)體和接口。

rbtree.h

enum color {BLACK, RED};struct rbnode{ int value; enum color color; struct rbnode *parent; struct rbnode *left; struct rbnode *right;}; struct rbtree{ struct rbnode *root; int size; int depth;}; int insert(struct rbtree *tree, int value);int delete(struct rbtree *tree, int value);struct rbnode * find(struct rbtree *tree, int value);

這個(gè)文件也很簡(jiǎn)單，定義了紅黑樹節(jié)點(diǎn)rbnode，顏色枚舉值RED BLACK，以及rbtree，rbtree用來(lái)放置紅黑樹的根節(jié)點(diǎn)和一些其它信息。還聲明了紅黑樹的三個(gè)接口函數(shù)insert、delete 和 find。

對(duì)于紅黑樹來(lái)說，find的實(shí)現(xiàn)很簡(jiǎn)單，二叉搜索樹的查找：
rbtree.c

struct rbnode * find(struct rbtree *tree, int value){ struct rbnode *p = tree->root; while(p){ if (value == p->value) return p; if (value < p->value) p = p->left; else p = p->right; } return NULL;}

紅黑樹本身也是個(gè)二叉搜索樹，所以它的查找函數(shù)和二叉搜索樹的查找是一樣的。

4.2 翻色與旋轉(zhuǎn)代碼

下面我們來(lái)說下翻色與旋轉(zhuǎn)函數(shù)的實(shí)現(xiàn)

rbtree.c

static void color_flip_up(struct rbnode *node){ node->color = RED; node->left->color = BLACK; node->right->color = BLACK;} static void color_flip_down(struct rbnode *node){ node->color = BLACK; node->left->color = RED; node->right->color = RED;}

翻色函數(shù)很好理解，向上翻色就是把自己變紅，把左子和右子都變黑，向下翻色正好相反。

再來(lái)看一下旋轉(zhuǎn)函數(shù)
rbtree.c

void rotate_left(struct rbtree *tree, struct rbnode *y){ struct rbnode* x = y->right; if(!x) return;  x->parent = y->parent; if(y->parent){ int flag = y == y->parent->left; flag ? (y->parent->left = x) : (y->parent->right = x); } else { tree->root = x; }  y->right = x->left; if(x->left) x->left->parent = y;  x->left = y; y->parent = x;  enum color c = x->color; x->color = y->color; y->color = c; } void rotate_right(struct rbtree *tree, struct rbnode *y){ struct rbnode *x = y->left; if(!x) return;  x->parent = y->parent; if(y->parent){ int flag = y->parent->left == y; flag ? (y->parent->left = x) : (y->parent->right = x); } else { tree->root = x; }  y->left = x->right; if(x->right) x->right->parent = y;  x->right = y; y->parent = x; enum color color = x->color; x->color = y->color; y->color = color;}

我們以左旋為例講解一下。左旋旋轉(zhuǎn)的是自己和右子，往左旋把自己旋下去了，把右子旋上來(lái)了，右子占據(jù)了自己的位置，自己成了右子的左子。函數(shù)首先做的是交接parent，把右子先掛到parent上去，然后把右子的左子掛接到自己身上，接著讓自己成為右子的左子，最后交換二者的顏色，這么做是為了保持兩者的連接顏色不變。右旋的邏輯是類似的，這里就不再多講解了。

4.3 插入操作的代碼

代碼如下，主要是兩個(gè)函數(shù)，insert和insert_fix。

rbtree.c

int insert(struct rbtree *tree, int value){ struct rbnode *p = malloc(sizeof(*p)); if(!p) return -1;  p->value = value; p->color = RED; p->parent = NULL; p->left = NULL; p->right = NULL;  if(!tree->root){ tree->root = p; p->color = BLACK; tree->size++; tree->depth++; return 0; }  struct rbnode *i = tree->root, *parent; int flag; while(i){ parent = i; if(value < i->value){ i = i->left; flag = 1; } else if(value > i->value){ i = i->right; flag = 0; } else { free(p); return -1; } }  p->parent = parent; flag ? (parent->left = p) : (parent->right = p); insert_fix(tree, p); tree->size++; return 0; } void insert_fix(struct rbtree *tree, struct rbnode *node){ struct rbnode *x = node, *y, *tmp; while(x->parent){ y = x->parent;  if(x == y->left){ if(y->color == BLACK) return; rotate_right(tree, y->parent); color_flip_up(y); x = y; } else { if(y->left && y->left->color == RED){ color_flip_up(y); x = y; } else { rotate_left(tree, y); tmp = x, x = y, y = tmp; if(y->color == BLACK) return; rotate_right(tree, y->parent); color_flip_up(y); x = y; } } } if(tree->root->color == RED){ tree->root->color = BLACK; tree->depth++; }}

函數(shù)insert的邏輯很簡(jiǎn)單，就是創(chuàng)建新的節(jié)點(diǎn)，新節(jié)點(diǎn)的顏色設(shè)為紅色，按照二叉搜索樹的方式尋找要插入的位置，然后調(diào)用insert_fix,來(lái)保證整個(gè)樹是一個(gè)符合定義的紅黑樹。insert_fix的實(shí)現(xiàn)主體是一個(gè)while循環(huán)，當(dāng)x的parent存在時(shí)就一直循環(huán)，直到x是根節(jié)點(diǎn)為止，當(dāng)然while內(nèi)部有提前結(jié)束循環(huán)的地方。進(jìn)入循環(huán)體內(nèi)，首先我們要明白的就是，此時(shí)x的顏色是RED，這是因?yàn)榈谝淮窝h(huán)的時(shí)候x是RED的，后面循環(huán)再次進(jìn)來(lái)的時(shí)候x也是RED的，如果不是的話就不會(huì)繼續(xù)循環(huán)了。先分x是左子還是右子兩種情況來(lái)討論，當(dāng)x是左子的時(shí)候，看parent是不是RED，如果是BLACK的話，直接return。如果是RED的話，此時(shí)x和y都是左斜的，y是左斜的是因?yàn)槲覀儗?shí)現(xiàn)的是左斜紅黑樹，原有的紅色節(jié)點(diǎn)只可能是左斜的。對(duì)于雙紅色左斜節(jié)點(diǎn)的處理，我把圖片又放到下面了，大家可以再看一看。這種情況我們應(yīng)當(dāng)對(duì)y的parent進(jìn)行右旋，右旋之后，y成了兩個(gè)紅色節(jié)點(diǎn)的父節(jié)點(diǎn)，由于旋轉(zhuǎn)之前y是紅色，所以y的parent不可能是紅色，只能是黑色，所以旋轉(zhuǎn)之后交換了顏色，所以此時(shí)y肯定是黑色。y是黑色，左子右子都是紅色，正好可以翻色，翻色之后，左子右子都變成了黑色，y變成了紅色，讓x=y進(jìn)行下一輪循環(huán)。當(dāng)x是右子的時(shí)候，先看一下左兄弟是不是紅色，如果是的話，父節(jié)點(diǎn)y肯定是黑色，正好可以翻色，對(duì)y進(jìn)行翻色，讓x=y，繼續(xù)下一輪循環(huán)。如果x的左兄弟不是紅色的，先左旋y，左旋之后x y的父子關(guān)系變了，交換一下它們的值，讓x仍然是子，y仍然是父。判斷y的顏色，如果是黑色直接return函數(shù)結(jié)束，如果是紅色，x y又形成了雙左斜紅色的情況，和上面的處理方式是一樣的，右旋y的parent，翻色y，讓x=y，繼續(xù)下一輪循環(huán)。函數(shù)最后判斷根節(jié)點(diǎn)是否為紅色，如果為紅色的話，說明之前的根節(jié)點(diǎn)經(jīng)歷過分割，樹的高度增加1，再把根節(jié)點(diǎn)重置為黑色。

4.4 刪除操作的代碼

刪除操作主要有兩個(gè)函數(shù)，delete 和 delete_fix，delete比insert稍微復(fù)雜一點(diǎn)，要處理被刪除的點(diǎn)不是葉子節(jié)點(diǎn)的情況。對(duì)于非葉子節(jié)點(diǎn)的情況，其右子樹一定存在，用右子樹的最小值，也就是右子樹的最左子節(jié)點(diǎn)的值覆蓋自己，然后刪除右子樹的最左子節(jié)點(diǎn)就可以了。

rbtree.c

int delete(struct rbtree *tree, int value){ if(!tree->root) return -1;  struct rbnode *i = tree->root, *j; while(i){ if(value < i->value){ i = i->left; } else if(value > i->value){ i = i->right; } else { if(!i->left || !i->right){ delete_fix(tree, i); tree->size--; return 0; } j = i->right; while(j->left) j = j->left; i->value = j->value; delete_fix(tree, j); tree->size--; return 0; } } return -1;} void delete_fix(struct rbtree *tree, struct rbnode *node){ if(node->left && node->left->color == RED) rotate_right(tree, node); if(node->color == RED) goto delete;  struct rbnode *self = node, *parent, *brother, *nephew; int red_borrowed = 0; while(self->parent){ parent = self->parent; if(self == parent->left){ // left child brother = parent->right; nephew = brother->left; if(nephew && nephew->color == RED){ nephew->color = BLACK; rotate_right(tree, brother); rotate_left(tree, parent); self->color = RED; if(red_borrowed){ red_borrowed = 0; self->color = BLACK; } break; } else { int old_red_borrowed = red_borrowed; red_borrowed = 0; if(parent->color == BLACK) red_borrowed = 1; color_flip_down(parent); if(old_red_borrowed) self->color = BLACK; rotate_left(tree, parent); if(red_borrowed){ self = brother; continue; } else { break; } } // left child end } else { // right child  brother = parent->left; nephew = brother->left; if(brother && brother->color == RED){ if(brother->right && brother->right->left && brother->right->left->color == RED){ struct rbnode *n = brother->right->left; rotate_right(tree, parent); rotate_right(tree, parent); n->color = BLACK; self->color = RED; if(red_borrowed){ red_borrowed = 0; self->color = BLACK; } rotate_left(tree, brother); break; } else { rotate_right(tree, parent); color_flip_down(parent); if(red_borrowed){ red_borrowed = 0; self->color = BLACK; } break; } } else if(nephew && nephew->color == RED){ rotate_right(tree, parent); nephew->color = BLACK; self->color = RED; if(red_borrowed){ red_borrowed = 0; self->color = BLACK; } break; } else { int old_red_borrowed = red_borrowed; red_borrowed = 0; if(parent->color == BLACK) red_borrowed = 1; color_flip_down(parent); if(old_red_borrowed) self->color = BLACK; if(red_borrowed){ self = parent; continue; } else { break; } } // right child end } }  if(red_borrowed) tree->depth--;  struct rbnode *child; delete: child = node->left ? node->left : node->right; if(node->parent){ int flag = node == node->parent->left; flag ? (node->parent->left = child) : (node->parent->right = child); } else { tree->root = child; if(!tree->root) tree->depth--; } if(child) child->parent = node->parent; free(node);}

函數(shù)delete_fix首先考慮兩種特殊情況，如果node是紅色的，或者node的左子是紅色的，直接右旋自己，把自己變成紅色，然后直接goto delete。剩下的情況就是node不是紅色的，也是說node是單元素節(jié)點(diǎn)，要想辦法把自己變成紅色的，也就是通過借元素變成雙元素節(jié)點(diǎn)。進(jìn)入循環(huán)的條件是當(dāng)前元素的parent不為空，循環(huán)內(nèi)部有一個(gè)變量red_borrowed控制著是否繼續(xù)循環(huán)，如果為1則循環(huán)，如果為0則結(jié)束循環(huán)，也就是說循環(huán)至少會(huì)執(zhí)行一次，然后x->parent和red_borrowed共同決定是否繼續(xù)循環(huán)。循環(huán)體內(nèi)分為兩種情況，自己是左子和自己是右子的情況，自己是左子的情況又分兩種，自己是右子的情況又分四種。下面通過畫圖給大家解析一下。字母與代碼中對(duì)應(yīng)的節(jié)點(diǎn)如下：
x:self
y:parent
z:brother
w:nephew(侄子)
注意在每次循環(huán)開始的時(shí)候x都是黑色的。由于我們是左斜紅黑樹，所以z不可能是紅色的，可能的情況只有w是紅色的或者是黑色的(下一種情況)，對(duì)于這種情況，我們通過其對(duì)應(yīng)的2-3 B樹可以看出來(lái)我們應(yīng)該如何把紅黑樹調(diào)整成目標(biāo)的樣子。我們先把w的顏色置黑，因?yàn)樗罱K的顏色是黑色的，提前置黑能避免旋轉(zhuǎn)時(shí)的顏色交換。然后通過右旋z、左旋y把紅黑樹調(diào)整成目標(biāo)形態(tài)，然后把x的顏色置紅，然后再根據(jù)red_borrowed把x置黑。此種情況我們幫x借到了紅色，對(duì)應(yīng)著2-3 B樹中借到了元素，所以循環(huán)結(jié)束。

這種情況是兄弟節(jié)點(diǎn)沒法借的情況，只有向父節(jié)點(diǎn)借，向父節(jié)點(diǎn)借有兩種情況，一是父節(jié)點(diǎn)是紅色，能借到，循環(huán)就結(jié)束了，二是父節(jié)點(diǎn)是黑色，借不到，只能強(qiáng)行借了，把red_borrowed設(shè)置為1。我們還要考慮上一輪的red_borrowed，如果為1，要把借來(lái)的紅色還了，也就是說x剛借來(lái)紅色就還了，x還是黑色的。如果red_borrowed為0的話說明是第一次循環(huán)，x是要被刪除的元素，所以不存在違背紅子不紅的問題。如果這一輪的red_borrowed是1的話則繼續(xù)循環(huán)，否則就結(jié)束循環(huán)。

這是一種比較復(fù)雜的情況，對(duì)應(yīng)著2-3 B樹的情況是父節(jié)點(diǎn)和兄弟節(jié)點(diǎn)都有兩個(gè)元素的情況?？醇t黑樹比較復(fù)雜，我們看2-3 B樹是怎么操作的，通過B樹的操作反推紅黑樹應(yīng)該如何操作。第一步我們右旋y，得到了一個(gè)x y o n ，一個(gè)局部有紅色節(jié)點(diǎn)的樹。第二步，只考慮這個(gè)樹，我們最后可以通過右旋y并調(diào)整顏色的方式把紅色轉(zhuǎn)移給x，這樣我們就達(dá)到目的了。然后我們發(fā)現(xiàn)o的顏色是右斜的，對(duì)z左旋一下，把它調(diào)整為一個(gè)左斜紅黑樹。

這種情況對(duì)應(yīng)的2-3 B樹是父節(jié)點(diǎn)有兩個(gè)元素，向父節(jié)點(diǎn)借一個(gè)元素并和兄弟節(jié)點(diǎn)合并，所以我們先右旋y，然后對(duì)y進(jìn)行翻色，x就變?yōu)榧t色了。通過前面的分析我們知道，雖然x是紅色右斜的，但是有兩種情況，要么x是被借紅的，所以還會(huì)變成黑色，要么x就是要被刪除的節(jié)點(diǎn)，所以不需要把x旋轉(zhuǎn)為左斜的。

這種情況是父節(jié)點(diǎn)只有一個(gè)元素兄弟節(jié)點(diǎn)有兩個(gè)元素，直接向兄弟借元素，一個(gè)右旋y并調(diào)整顏色，就搞定了。

這種情況和左2是相同的，而且還比左2簡(jiǎn)單，由于z是左斜的，所以旋轉(zhuǎn)的動(dòng)作都省了。

五、總結(jié)回顧