概要
紅黑樹在日常的使用中比較常用，例如Java的TreeMap和TreeSet，C++的STL，以及Linux核心中都有用到。之前寫過一篇文章專門介紹紅黑樹的理論知識，本文将給出紅黑數的C語言的實作代碼，後序章節再分别給出C++和Java版本的實作。還是那句話，三種實作原理相同，擇其一了解即可；若文章有錯誤或不足的地方，望不吝指出！
目錄
1. 紅黑樹的介紹
2. 紅黑樹的C實作(代碼說明)
3. 紅黑樹的C實作(完整源碼)
4. 紅黑樹的C測試程式
紅黑樹的介紹
紅黑樹(Red-Black Tree，簡稱R-B Tree)，它一種特殊的二叉查找樹。
紅黑樹是特殊的二叉查找樹，意味着它滿足二叉查找樹的特征：任意一個節點所包含的鍵值，大于等于左孩子的鍵值，小于等于右孩子的鍵值。
除了具備該特性之外，紅黑樹還包括許多額外的資訊。
紅黑樹的每個節點上都有存儲位表示節點的顔色，顔色是紅(Red)或黑(Black)。
紅黑樹的特性:
(1) 每個節點或者是黑色，或者是紅色。
(2) 根節點是黑色。
(3) 每個葉子節點是黑色。 [注意：這裡葉子節點，是指為空的葉子節點！]
(4) 如果一個節點是紅色的，則它的子節點必須是黑色的。
(5) 從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點。
關于它的特性，需要注意的是：
第一，特性(3)中的葉子節點，是隻為空(NIL或null)的節點。
第二，特性(5)，確定沒有一條路徑會比其他路徑長出倆倍。因而，紅黑樹是相對是接近平衡的二叉樹。
紅黑樹示意圖如下：
紅黑樹的C實作(代碼說明)
紅黑樹的基本操作是添加、删除和旋轉。在對紅黑樹進行添加或删除後，會用到旋轉方法。為什麼呢？道理很簡單，添加或删除紅黑樹中的節點之後，紅黑樹就發生了變化，可能不滿足紅黑樹的5條性質，也就不再是一顆紅黑樹了，而是一顆普通的樹。而通過旋轉，可以使這顆樹重新成為紅黑樹。簡單點說，旋轉的目的是讓樹保持紅黑樹的特性。
旋轉包括兩種：左旋 和 右旋。下面分别對旋轉(左旋和右旋)、添加、删除進行介紹。
1. 基本定義
#define RED 0 // 紅色節點
#define BLACK 1 // 黑色節點
typedef int Type;
// 紅黑樹的節點
typedef struct RBTreeNode{
unsigned char color; // 顔色(RED 或 BLACK)
Type key; // 關鍵字(鍵值)
struct RBTreeNode *left; // 左孩子
struct RBTreeNode *right; // 右孩子
struct RBTreeNode *parent; // 父結點
}Node, *RBTree;
// 紅黑樹的根
typedef struct rb_root{
Node *node;
}RBRoot; RBTreeNode是紅黑樹的節點類，RBRoot是紅黑樹的根。
2. 左旋
對x進行左旋，意味着"将x變成一個左節點"。
左旋的實作代碼(C語言)
/*
* 對紅黑樹的節點(x)進行左旋轉
*
* 左旋示意圖(對節點x進行左旋)：
* px px
* / /
* x y
* / \ --(左旋)--> / \ #
* lx y x ry
* / \ / \
* ly ry lx ly
*
*
*/
static void rbtree_left_rotate(RBRoot *root, Node *x)
{
// 設定x的右孩子為y
Node *y = x->right;
// 将 “y的左孩子” 設為 “x的右孩子”；
// 如果y的左孩子非空，将 “x” 設為 “y的左孩子的父親”
x->right = y->left;
if (y->left != NULL)
y->left->parent = x;
// 将 “x的父親” 設為 “y的父親”
y->parent = x->parent;
if (x->parent == NULL)
{
//tree = y; // 如果 “x的父親” 是空節點，則将y設為根節點
root->node = y; // 如果 “x的父親” 是空節點，則将y設為根節點
}
else
{
if (x->parent->left == x)
x->parent->left = y; // 如果 x是它父節點的左孩子，則将y設為“x的父節點的左孩子”
else
x->parent->right = y; // 如果 x是它父節點的左孩子，則将y設為“x的父節點的左孩子”
}
// 将 “x” 設為 “y的左孩子”
y->left = x;
// 将 “x的父節點” 設為 “y”
x->parent = y;
} 3. 右旋
對y進行左旋，意味着"将y變成一個右節點"。
右旋的實作代碼(C語言)
/*
* 對紅黑樹的節點(y)進行右旋轉
*
* 右旋示意圖(對節點y進行左旋)：
* py py
* / /
* y x
* / \ --(右旋)--> / \ #
* x ry lx y
* / \ / \ #
* lx rx rx ry
*
*/
static void rbtree_right_rotate(RBRoot *root, Node *y)
{
// 設定x是目前節點的左孩子。
Node *x = y->left;
// 将 “x的右孩子” 設為 “y的左孩子”；
// 如果"x的右孩子"不為空的話，将 “y” 設為 “x的右孩子的父親”
y->left = x->right;
if (x->right != NULL)
x->right->parent = y;
// 将 “y的父親” 設為 “x的父親”
x->parent = y->parent;
if (y->parent == NULL)
{
//tree = x; // 如果 “y的父親” 是空節點，則将x設為根節點
root->node = x; // 如果 “y的父親” 是空節點，則将x設為根節點
}
else
{
if (y == y->parent->right)
y->parent->right = x; // 如果 y是它父節點的右孩子，則将x設為“y的父節點的右孩子”
else
y->parent->left = x; // (y是它父節點的左孩子) 将x設為“x的父節點的左孩子”
}
// 将 “y” 設為 “x的右孩子”
x->right = y;
// 将 “y的父節點” 設為 “x”
y->parent = x;
} 4. 添加
将一個節點(z)插入到紅黑樹中，需要執行哪些步驟呢？首先，将紅黑樹當作一顆二叉查找樹，将節點插入；然後，将節點着色為紅色；最後，通過"旋轉和重新着色"等一系列操作來修正該樹，使之重新成為一顆紅黑樹。較長的描述如下：
第一步: 将紅黑樹當作一顆二叉查找樹，将節點插入。
紅黑樹本身就是一顆二叉查找樹，将節點插入後，該樹仍然是一顆二叉查找樹。也就意味着，樹的鍵值仍然是有序的。此外，無論是左旋還是右旋，若旋轉之前這棵樹是二叉查找樹，旋轉之後它一定還是二叉查找樹。這也就意味着，任何的旋轉和重新着色操作，都不會改變它仍然是一顆二叉查找樹的事實。
好吧？那接下來，我們就來想方設法的旋轉以及重新着色，使這顆樹重新成為紅黑樹！
第二步：将插入的節點着色為"紅色"。
為什麼着色成紅色，而不是黑色呢？為什麼呢？在回答之前，我們需要重新溫習一下紅黑樹的特性：
(1) 每個節點或者是黑色，或者是紅色。
(2) 根節點是黑色。
(3) 每個葉子節點是黑色。 [注意：這裡葉子節點，是指為空的葉子節點！]
(4) 如果一個節點是紅色的，則它的子節點必須是黑色的。
(5) 從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點。
将插入的節點着色為紅色，不會違背"特性(5)"！少違背一條特性，就意味着我們需要處理的情況越少。接下來，就要努力的讓這棵樹滿足其它性質即可；滿足了的話，它就又是一顆紅黑樹了。o(∩∩)o...哈哈
第三步: 通過一系列的旋轉或着色等操作，使之重新成為一顆紅黑樹。
第二步中，将插入節點着色為"紅色"之後，不會違背"特性(5)"。那它到底會違背哪些特性呢？
對于"特性(1)"，顯然不會違背了。因為我們已經将它塗成紅色了。
對于"特性(2)"，顯然也不會違背。在第一步中，我們是将紅黑樹當作二叉查找樹，然後執行的插入操作。而根據二叉查找數的特點，插入操作不會改變根節點。是以，根節點仍然是黑色。
對于"特性(3)"，顯然不會違背了。這裡的葉子節點是指的空葉子節點，插入非空節點并不會對它們造成影響。
對于"特性(4)"，是有可能違背的！
那接下來，想辦法使之"滿足特性(4)"，就可以将樹重新構造成紅黑樹了。
添加操作的實作代碼(C語言)
/*
* 添加節點：将節點(node)插入到紅黑樹中
*
* 參數說明：
* root 紅黑樹的根
* node 插入的結點 // 對應《算法導論》中的z
*/
static void rbtree_insert(RBRoot *root, Node *node)
{
Node *y = NULL;
Node *x = root->node;
// 1. 将紅黑樹當作一顆二叉查找樹，将節點添加到二叉查找樹中。
while (x != NULL)
{
y = x;
if (node->key < x->key)
x = x->left;
else
x = x->right;
}
rb_parent(node) = y;
if (y != NULL)
{
if (node->key < y->key)
y->left = node; // 情況2：若“node所包含的值” < “y所包含的值”，則将node設為“y的左孩子”
else
y->right = node; // 情況3：(“node所包含的值” >= “y所包含的值”)将node設為“y的右孩子”
}
else
{
root->node = node; // 情況1：若y是空節點，則将node設為根
}
// 2. 設定節點的顔色為紅色
node->color = RED;
// 3. 将它重新修正為一顆二叉查找樹
rbtree_insert_fixup(root, node);
} rbtree_insert(root, node)的作用是将"node"節點插入到紅黑樹中。其中，root是根，node是被插入節點。
rbtree_insert(root, node)是參考《算法導論》中紅黑樹的插入函數的僞代碼進行實作的。
添加修正操作的實作代碼(C語言)
/*
* 紅黑樹插入修正函數
*
* 在向紅黑樹中插入節點之後(失去平衡)，再調用該函數；
* 目的是将它重新塑造成一顆紅黑樹。
*
* 參數說明：
* root 紅黑樹的根
* node 插入的結點 // 對應《算法導論》中的z
*/
static void rbtree_insert_fixup(RBRoot *root, Node *node)
{
Node *parent, *gparent;
// 若“父節點存在，并且父節點的顔色是紅色”
while ((parent = rb_parent(node)) && rb_is_red(parent))
{
gparent = rb_parent(parent);
//若“父節點”是“祖父節點的左孩子”
if (parent == gparent->left)
{
// Case 1條件：叔叔節點是紅色
{
Node *uncle = gparent->right;
if (uncle && rb_is_red(uncle))
{
rb_set_black(uncle);
rb_set_black(parent);
rb_set_red(gparent);
node = gparent;
continue;
}
}
// Case 2條件：叔叔是黑色，且目前節點是右孩子
if (parent->right == node)
{
Node *tmp;
rbtree_left_rotate(root, parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3條件：叔叔是黑色，且目前節點是左孩子。
rb_set_black(parent);
rb_set_red(gparent);
rbtree_right_rotate(root, gparent);
}
else//若“z的父節點”是“z的祖父節點的右孩子”
{
// Case 1條件：叔叔節點是紅色
{
Node *uncle = gparent->left;
if (uncle && rb_is_red(uncle))
{
rb_set_black(uncle);
rb_set_black(parent);
rb_set_red(gparent);
node = gparent;
continue;
}
}
// Case 2條件：叔叔是黑色，且目前節點是左孩子
if (parent->left == node)
{
Node *tmp;
rbtree_right_rotate(root, parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3條件：叔叔是黑色，且目前節點是右孩子。
rb_set_black(parent);
rb_set_red(gparent);
rbtree_left_rotate(root, gparent);
}
}
// 将根節點設為黑色
rb_set_black(root->node);
} rbtree_insert_fixup(root, node)的作用是對應"上面所講的第三步"。
5. 删除操作
将紅黑樹内的某一個節點删除。需要執行的操作依次是：首先，将紅黑樹當作一顆二叉查找樹，将該節點從二叉查找樹中删除；然後，通過"旋轉和重新着色"等一系列來修正該樹，使之重新成為一棵紅黑樹。較長的描述如下：
第一步：将紅黑樹當作一顆二叉查找樹，将節點删除。
這和"删除正常二叉查找樹中删除節點的方法是一樣的"。分3種情況：
① 被删除節點沒有兒子，即為葉節點。那麼，直接将該節點删除就OK了。
② 被删除節點隻有一個兒子。那麼，直接删除該節點，并用該節點的唯一子節點頂替它的位置。
③
被删除節點有兩個兒子。那麼，先找出它的後繼節點；然後把“它的後繼節點的内容”複制給“該節點的内容”；之後，删除“它的後繼節點”。在這裡，後繼節點相當于替身，在将後繼節點的内容複制給"被删除節點"之後，再将後繼節點删除。這樣就巧妙的将問題轉換為"删除後繼節點"的情況了，下面就考慮後繼節點。
在"被删除節點"有兩個非空子節點的情況下，它的後繼節點不可能是雙子非空。既然"的後繼節點"不可能雙子都非空，就意味着"該節點的後繼節點"要麼沒有兒子，要麼隻有一個兒子。若沒有兒子，則按"情況①
"進行處理；若隻有一個兒子，則按"情況② "進行處理。
第二步：通過"旋轉和重新着色"等一系列來修正該樹，使之重新成為一棵紅黑樹。
因為"第一步"中删除節點之後，可能會違背紅黑樹的特性。是以需要通過"旋轉和重新着色"來修正該樹，使之重新成為一棵紅黑樹。
删除操作的實作代碼(C語言)
/*
* 删除結點
*
* 參數說明：
* tree 紅黑樹的根結點
* node 删除的結點
*/
void rbtree_delete(RBRoot *root, Node *node)
{
Node *child, *parent;
int color;
// 被删除節點的"左右孩子都不為空"的情況。
if ( (node->left!=NULL) && (node->right!=NULL) )
{
// 被删節點的後繼節點。(稱為"取代節點")
// 用它來取代"被删節點"的位置，然後再将"被删節點"去掉。
Node *replace = node;
// 擷取後繼節點
replace = replace->right;
while (replace->left != NULL)
replace = replace->left;
// "node節點"不是根節點(隻有根節點不存在父節點)
if (rb_parent(node))
{
if (rb_parent(node)->left == node)
rb_parent(node)->left = replace;
else
rb_parent(node)->right = replace;
}
else
// "node節點"是根節點，更新根節點。
root->node = replace;
// child是"取代節點"的右孩子，也是需要"調整的節點"。
// "取代節點"肯定不存在左孩子！因為它是一個後繼節點。
child = replace->right;
parent = rb_parent(replace);
// 儲存"取代節點"的顔色
color = rb_color(replace);
// "被删除節點"是"它的後繼節點的父節點"
if (parent == node)
{
parent = replace;
}
else
{
// child不為空
if (child)
rb_set_parent(child, parent);
parent->left = child;
replace->right = node->right;
rb_set_parent(node->right, replace);
}
replace->parent = node->parent;
replace->color = node->color;
replace->left = node->left;
node->left->parent = replace;
if (color == BLACK)
rbtree_delete_fixup(root, child, parent);
free(node);
return ;
}
if (node->left !=NULL)
child = node->left;
else
child = node->right;
parent = node->parent;
// 儲存"取代節點"的顔色
color = node->color;
if (child)
child->parent = parent;
// "node節點"不是根節點
if (parent)
{
if (parent->left == node)
parent->left = child;
else
parent->right = child;
}
else
root->node = child;
if (color == BLACK)
rbtree_delete_fixup(root, child, parent);
free(node);
} rbtree_delete(root, node)的作用是将"node"節點插入到紅黑樹中。其中，root是根，node是被插入節點。
删除修正操作的實作代碼(C語言)
/*
* 紅黑樹删除修正函數
*
* 在從紅黑樹中删除插入節點之後(紅黑樹失去平衡)，再調用該函數；
* 目的是将它重新塑造成一顆紅黑樹。
*
* 參數說明：
* root 紅黑樹的根
* node 待修正的節點
*/
static void rbtree_delete_fixup(RBRoot *root, Node *node, Node *parent)
{
Node *other;
while ((!node || rb_is_black(node)) && node != root->node)
{
if (parent->left == node)
{
other = parent->right;
if (rb_is_red(other))
{
// Case 1: x的兄弟w是紅色的
rb_set_black(other);
rb_set_red(parent);
rbtree_left_rotate(root, parent);
other = parent->right;
}
if ((!other->left || rb_is_black(other->left)) &&
(!other->right || rb_is_black(other->right)))
{
// Case 2: x的兄弟w是黑色，且w的倆個孩子也都是黑色的
rb_set_red(other);
node = parent;
parent = rb_parent(node);
}
else
{
if (!other->right || rb_is_black(other->right))
{
// Case 3: x的兄弟w是黑色的，并且w的左孩子是紅色，右孩子為黑色。
rb_set_black(other->left);
rb_set_red(other);
rbtree_right_rotate(root, other);
other = parent->right;
}
// Case 4: x的兄弟w是黑色的；并且w的右孩子是紅色的，左孩子任意顔色。
rb_set_color(other, rb_color(parent));
rb_set_black(parent);
rb_set_black(other->right);
rbtree_left_rotate(root, parent);
node = root->node;
break;
}
}
else
{
other = parent->left;
if (rb_is_red(other))
{
// Case 1: x的兄弟w是紅色的
rb_set_black(other);
rb_set_red(parent);
rbtree_right_rotate(root, parent);
other = parent->left;
}
if ((!other->left || rb_is_black(other->left)) &&
(!other->right || rb_is_black(other->right)))
{
// Case 2: x的兄弟w是黑色，且w的倆個孩子也都是黑色的
rb_set_red(other);
node = parent;
parent = rb_parent(node);
}
else
{
if (!other->left || rb_is_black(other->left))
{
// Case 3: x的兄弟w是黑色的，并且w的左孩子是紅色，右孩子為黑色。
rb_set_black(other->right);
rb_set_red(other);
rbtree_left_rotate(root, other);
other = parent->left;
}
// Case 4: x的兄弟w是黑色的；并且w的右孩子是紅色的，左孩子任意顔色。
rb_set_color(other, rb_color(parent));
rb_set_black(parent);
rb_set_black(other->left);
rbtree_right_rotate(root, parent);
node = root->node;
break;
}
}
}
if (node)
rb_set_black(node);
} rbtree_delete_fixup(root, node, parent)是對應"上面所講的第三步"。
紅黑樹的C實作(完整源碼)
下面是紅黑數實作的完整代碼和相應的測試程式。
(1) 除了上面所說的"左旋"、"右旋"、"添加"、"删除"等基本操作之後，還實作了"周遊"、"查找"、"列印"、"最小值"、"最大值"、"建立"、"銷毀"等接口。
(2) 函數接口分為内部接口和外部接口。内部接口是static函數，外部接口則是非static函數，外部接口都在.h頭檔案中表明了。
(3) 測試代碼中提供了"插入"和"删除"動作的檢測開關。預設是關閉的，打開方法可以參考"代碼中的說明"。建議在打開開關後，在草稿上自己動手繪制一下紅黑樹。
紅黑樹的實作檔案(rbtree.h)
1 #ifndef _RED_BLACK_TREE_H_
2 #define _RED_BLACK_TREE_H_
3
4 #define RED 0 // 紅色節點
5 #define BLACK 1 // 黑色節點
6
7 typedef int Type;
8
9 // 紅黑樹的節點
10 typedef struct RBTreeNode{
11 unsigned char color; // 顔色(RED 或 BLACK)
12 Type key; // 關鍵字(鍵值)
13 struct RBTreeNode *left; // 左孩子
14 struct RBTreeNode *right; // 右孩子
15 struct RBTreeNode *parent; // 父結點
16 }Node, *RBTree;
17
18 // 紅黑樹的根
19 typedef struct rb_root{
20 Node *node;
21 }RBRoot;
22
23 // 建立紅黑樹，傳回"紅黑樹的根"！
24 RBRoot* create_rbtree();
25
26 // 銷毀紅黑樹
27 void destroy_rbtree(RBRoot *root);
28
29 // 将結點插入到紅黑樹中。插入成功，傳回0；失敗傳回-1。
30 int insert_rbtree(RBRoot *root, Type key);
31
32 // 删除結點(key為節點的值)
33 void delete_rbtree(RBRoot *root, Type key);
34
35
36 // 前序周遊"紅黑樹"
37 void preorder_rbtree(RBRoot *root);
38 // 中序周遊"紅黑樹"
39 void inorder_rbtree(RBRoot *root);
40 // 後序周遊"紅黑樹"
41 void postorder_rbtree(RBRoot *root);
42
43 // (遞歸實作)查找"紅黑樹"中鍵值為key的節點。找到的話，傳回0；否則，傳回-1。
44 int rbtree_search(RBRoot *root, Type key);
45 // (非遞歸實作)查找"紅黑樹"中鍵值為key的節點。找到的話，傳回0；否則，傳回-1。
46 int iterative_rbtree_search(RBRoot *root, Type key);
47
48 // 傳回最小結點的值(将值儲存到val中)。找到的話，傳回0；否則傳回-1。
49 int rbtree_minimum(RBRoot *root, int *val);
50 // 傳回最大結點的值(将值儲存到val中)。找到的話，傳回0；否則傳回-1。
51 int rbtree_maximum(RBRoot *root, int *val);
52
53 // 列印紅黑樹
54 void print_rbtree(RBRoot *root);
55
56 #endif 1 /**
2 * C語言實作的紅黑樹(Red Black Tree)
3 *
4 * @author skywang
5 * @date 2013/11/18
6 */
7
8 #include <stdio.h>
9 #include <stdlib.h>
10 #include "rbtree.h"
11
12 #define rb_parent(r) ((r)->parent)
13 #define rb_color(r) ((r)->color)
14 #define rb_is_red(r) ((r)->color==RED)
15 #define rb_is_black(r) ((r)->color==BLACK)
16 #define rb_set_black(r) do { (r)->color = BLACK; } while (0)
17 #define rb_set_red(r) do { (r)->color = RED; } while (0)
18 #define rb_set_parent(r,p) do { (r)->parent = (p); } while (0)
19 #define rb_set_color(r,c) do { (r)->color = (c); } while (0)
20
21 /*
22 * 建立紅黑樹，傳回"紅黑樹的根"！
23 */
24 RBRoot* create_rbtree()
25 {
26 RBRoot *root = (RBRoot *)malloc(sizeof(RBRoot));
27 root->node = NULL;
28
29 return root;
30 }
31
32 /*
33 * 前序周遊"紅黑樹"
34 */
35 static void preorder(RBTree tree)
36 {
37 if(tree != NULL)
38 {
39 printf("%d ", tree->key);
40 preorder(tree->left);
41 preorder(tree->right);
42 }
43 }
44 void preorder_rbtree(RBRoot *root)
45 {
46 if (root)
47 preorder(root->node);
48 }
49
50 /*
51 * 中序周遊"紅黑樹"
52 */
53 static void inorder(RBTree tree)
54 {
55 if(tree != NULL)
56 {
57 inorder(tree->left);
58 printf("%d ", tree->key);
59 inorder(tree->right);
60 }
61 }
62
63 void inorder_rbtree(RBRoot *root)
64 {
65 if (root)
66 inorder(root->node);
67 }
68
69 /*
70 * 後序周遊"紅黑樹"
71 */
72 static void postorder(RBTree tree)
73 {
74 if(tree != NULL)
75 {
76 postorder(tree->left);
77 postorder(tree->right);
78 printf("%d ", tree->key);
79 }
80 }
81
82 void postorder_rbtree(RBRoot *root)
83 {
84 if (root)
85 postorder(root->node);
86 }
87
88 /*
89 * (遞歸實作)查找"紅黑樹x"中鍵值為key的節點
90 */
91 static Node* search(RBTree x, Type key)
92 {
93 if (x==NULL || x->key==key)
94 return x;
95
96 if (key < x->key)
97 return search(x->left, key);
98 else
99 return search(x->right, key);
100 }
101 int rbtree_search(RBRoot *root, Type key)
102 {
103 if (root)
104 return search(root->node, key)? 0 : -1;
105 }
106
107 /*
108 * (非遞歸實作)查找"紅黑樹x"中鍵值為key的節點
109