1. 紅黑樹
1.1 紅黑樹概述
紅黑樹和我們以前學過的AVL樹類似，都是在進行插入和刪除操作時通過特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能。不過自從紅黑樹出來后，AVL樹就被放到了博物館里，據說是紅黑樹有更好的效率，更高的統計性能。這一點在我們了解了紅黑樹的實現原理后，就會有更加深切的體會。
紅黑樹和AVL樹的區別在于它使用顏色來標識結點的高度，它所追求的是局部平衡而不是AVL樹中的非常嚴格的平衡。學過數據結構的人應該都已經領教過AVL樹的復雜，但AVL樹的復雜比起紅黑樹來說簡直是小巫見大巫，紅黑樹才是真正的變態級數據結構。
由于STL中的關聯式容器默認的底層實現都是紅黑樹，因此紅黑樹對于后續學習STL源碼還是很重要的，有必要掌握紅黑樹的實現原理和源碼實現。
紅黑樹是AVL樹的變種，紅黑樹通過一些著色法則確保沒有一條路徑會比其它路徑長出兩倍，因而達到接近平衡的目的。所謂紅黑樹，不僅是一個二叉搜索樹，而且必須滿足一下規則：
- 1、每個節點不是紅色就是黑色。
- 2、根節點為黑色。
- 3、如果節點為紅色，其子節點必須為黑色。
- 4、任意一個節點到到NULL（樹尾端）的任何路徑，所含之黑色節點數必須相同。
上面的這些約束保證了這個樹大致上是平衡的，這也決定了紅黑樹的插入、刪除、查詢等操作是比較快速的。 根據規則4，新增節點必須為紅色；根據規則3，新增節點之父節點必須為黑色。當新增節點根據二叉搜索樹的規則到達其插入點時，卻未能符合上述條件時，就必須調整顏色并旋轉樹形，如下圖：
假設我們為上圖分別插入節點3、8、35、75，根據二叉搜索樹的規則，插入這四個節點后，我們會發現它們都破壞了紅黑樹的規則，因此我們必須調整樹形，也就是旋轉樹形并改變節點的顏色。
1.2 紅黑樹上結點的插入
在討論紅黑樹的插入操作之前必須要明白，任何一個即將插入的新結點的初始顏色都為紅色。這一點很容易理解，因為插入黑點會增加某條路徑上黑結點的數目，從而導致整棵樹黑高度的不平衡。但如果新結點的父結點為紅色時（如下圖所示），將會違反紅黑樹的性質：一條路徑上不能出現相鄰的兩個紅色結點。這時就需要通過一系列操作來使紅黑樹保持平衡。
為了清楚地表示插入操作以下在結點中使用“新”字表示一個新插入的結點；使用“父”字表示新插入點的父結點；使用“叔”字表示“父”結點的兄弟結點；使用“祖”字表示“父”結點的父結點。插入操作分為以下幾種情況：
1.2.1 黑父
如下圖所示，如果新節點的父結點為黑色結點，那么插入一個紅點將不會影響紅黑樹的平衡，此時插入操作完成。紅黑樹比AVL樹優秀的地方之一在于黑父的情況比較常見，從而使紅黑樹需要旋轉的幾率相對AVL樹來說會少一些。
1.2.2 紅父
如果新節點的父結點為紅色，這時就需要進行一系列操作以保證整棵樹紅黑性質。如下圖所示，由于父結點為紅色，此時可以判定，祖父結點必定為黑色。這時需要根據叔父結點的顏色來決定做什么樣的操作。青色結點表示顏色未知。由于有可能需要根結點到新點的路徑上進行多次旋轉操作，而每次進行不平衡判斷的起始點（我們可將其視為新點）都不一樣。所以我們在此使用一個藍色箭頭指向這個起始點，并稱之為判定點。
1.2.2.1 紅叔
當叔父結點為紅色時，如下圖所示，無需進行旋轉操作，只要將父和叔結點變為黑色，將祖父結點變為紅色即可。但由于祖父結點的父結點有可能為紅色，從而違反紅黑樹性質。此時必須將祖父結點作為新的判定點繼續向上（迭代）進行平衡操作。
需要注意的是，無論“父節點”在“叔節點”的左邊還是右邊，無論“新節點”是“父節點”的左孩子還是右孩子，它們的操作都是完全一樣的（其實這種情況包括4種，只需調整顏色，不需要旋轉樹形）。
1.2.2.2 黑叔
當叔父結點為黑色時，需要進行旋轉，以下圖示了所有的旋轉可能：
Case 1:
Case 2:
Case 3:
Case 4:
可以觀察到，當旋轉完成后，新的旋轉根全部為黑色，此時不需要再向上回溯進行平衡操作，插入操作完成。需要注意，上面四張圖的“叔”、“1”、“2”、“3”結點有可能為黑哨兵結點。
其實紅黑樹的插入操作不是很難，甚至比AVL樹的插入操作還更簡單些。紅黑樹的插入操作源代碼如下：
// 元素插入操作 insert_unique()
// 插入新值：節點鍵值不允許重復，若重復則插入無效
// 注意，返回值是個pair，第一個元素是個紅黑樹迭代器，指向新增節點
// 第二個元素表示插入成功與否
template<class Key , class Value , class KeyOfValue , class Compare , class Alloc>
pair<typename rb_tree<Key , Value , KeyOfValue , Compare , Alloc>::iterator , bool>
rb_tree<Key , Value , KeyOfValue , Compare , Alloc>::insert_unique(const Value &v)
{
rb_tree_node* y = header; // 根節點root的父節點
rb_tree_node* x = root(); // 從根節點開始
bool comp = true;
while(x != 0)
{
y = x;
comp = key_compare(KeyOfValue()(v) , key(x)); // v鍵值小于目前節點之鍵值？
x = comp ? left(x) : right(x); // 遇“大”則往左，遇“小于或等于”則往右
}
// 離開while循環之后，y所指即插入點之父節點（此時的它必為葉節點）
iterator j = iterator(y); // 令迭代器j指向插入點之父節點y
if(comp) // 如果離開while循環時comp為真（表示遇“大”，將插入于左側）
{
if(j == begin()) // 如果插入點之父節點為最左節點
return pair<iterator , bool>(_insert(x , y , z) , true);
else // 否則（插入點之父節點不為最左節點）
--j; // 調整j，回頭準備測試
}
if(key_compare(key(j.node) , KeyOfValue()(v) ))
// 新鍵值不與既有節點之鍵值重復，于是以下執行安插操作
return pair<iterator , bool>(_insert(x , y , z) , true);
// 以上，x為新值插入點，y為插入點之父節點，v為新值
// 進行至此，表示新值一定與樹中鍵值重復，那么就不應該插入新值
return pair<iterator , bool>(j , false);
}
// 真正地插入執行程序 _insert()
template<class Key , class Value , class KeyOfValue , class Compare , class Alloc>
typename<Key , Value , KeyOfValue , Compare , Alloc>::_insert(base_ptr x_ , base_ptr y_ , const Value &v)
{
// 參數x_ 為新值插入點，參數y_為插入點之父節點，參數v為新值
link_type x = (link_type) x_;
link_type y = (link_type) y_;
link_type z;
// key_compare 是鍵值大小比較準則。應該會是個function object
if(y == header || x != 0 || key_compare(KeyOfValue()(v) , key(y) ))
{
z = create_node(v); // 產生一個新節點
left(y) = z; // 這使得當y即為header時，leftmost() = z
if(y == header)
{
root() = z;
rightmost() = z;
}
else if(y == leftmost()) // 如果y為最左節點
leftmost() = z; // 維護leftmost()，使它永遠指向最左節點
}
else
{
z = create_node(v); // 產生一個新節點
right(y) = z; // 令新節點成為插入點之父節點y的右子節點
if(y == rightmost())
rightmost() = z; // 維護rightmost()，使它永遠指向最右節點
}
parent(z) = y; // 設定新節點的父節點
left(z) = 0; // 設定新節點的左子節點
right(z) = 0; // 設定新節點的右子節點
// 新節點的顏色將在_rb_tree_rebalance()設定（并調整）
_rb_tree_rebalance(z , header->parent); // 參數一為新增節點，參數二為根節點root
++node_count; // 節點數累加
return iterator(z); // 返回一個迭代器，指向新增節點
}
// 全局函數
// 重新令樹形平衡（改變顏色及旋轉樹形）
// 參數一為新增節點，參數二為根節點root
inline void _rb_tree_rebalance(_rb_tree_node_base* x , _rb_tree_node_base*& root)
{
x->color = _rb_tree_red; //新節點必為紅
while(x != root && x->parent->color == _rb_tree_red) // 父節點為紅
{
if(x->parent == x->parent->parent->left) // 父節點為祖父節點之左子節點
{
_rb_tree_node_base* y = x->parent->parent->right; // 令y為伯父節點
if(y && y->color == _rb_tree_red) // 伯父節點存在，且為紅
{
x->parent->color = _rb_tree_black; // 更改父節點為黑色
y->color = _rb_tree_black; // 更改伯父節點為黑色
x->parent->parent->color = _rb_tree_red; // 更改祖父節點為紅色
x = x->parent->parent;
}
else // 無伯父節點，或伯父節點為黑色
{
if(x == x->parent->right) // 如果新節點為父節點之右子節點
{
x = x->parent;
_rb_tree_rotate_left(x , root); // 第一個參數為左旋點
}
x->parent->color = _rb_tree_black; // 改變顏色
x->parent->parent->color = _rb_tree_red;
_rb_tree_rotate_right(x->parent->parent , root); // 第一個參數為右旋點
}
}
else // 父節點為祖父節點之右子節點
{
_rb_tree_node_base* y = x->parent->parent->left; // 令y為伯父節點
if(y && y->color == _rb_tree_red) // 有伯父節點，且為紅
{
x->parent->color = _rb_tree_black; // 更改父節點為黑色
y->color = _rb_tree_black; // 更改伯父節點為黑色
x->parent->parent->color = _rb_tree_red; // 更改祖父節點為紅色
x = x->parent->parent; // 準備繼續往上層檢查
}
else // 無伯父節點，或伯父節點為黑色
{
if(x == x->parent->left) // 如果新節點為父節點之左子節點
{
x = x->parent;
_rb_tree_rotate_right(x , root); // 第一個參數為右旋點
}
x->parent->color = _rb_tree_black; // 改變顏色
x->parent->parent->color = _rb_tree_red;
_rb_tree_rotate_left(x->parent->parent , root); // 第一個參數為左旋點
}
}
}//while
root->color = _rb_tree_black; // 根節點永遠為黑色
}
// 左旋函數
inline void _rb_tree_rotate_left(_rb_tree_node_base* x , _rb_tree_node_base*& root)
{
// x 為旋轉點
_rb_tree_node_base* y = x->right; // 令y為旋轉點的右子節點
x->right = y->left;
if(y->left != 0)
y->left->parent = x; // 別忘了回馬槍設定父節點
y->parent = x->parent;
// 令y完全頂替x的地位（必須將x對其父節點的關系完全接收過來）
if(x == root) // x為根節點
root = y;
else if(x == x->parent->left) // x為其父節點的左子節點
x->parent->left = y;
else // x為其父節點的右子節點
x->parent->right = y;
y->left = x;
x->parent = y;
}
// 右旋函數
inline void _rb_tree_rotate_right(_rb_tree_node_base* x , _rb_tree_node_base*& root)
{
// x 為旋轉點
_rb_tree_node_base* y = x->left; // 令y為旋轉點的左子節點
x->left = y->right;
if(y->right != 0)
y->right->parent = x; // 別忘了回馬槍設定父節點
y->parent = x->parent;
// 令y完全頂替x的地位（必須將x對其父節點的關系完全接收過來）
if(x == root)
root = y;
else if(x == x->parent->right) // x為其父節點的右子節點
x->parent->right = y;
else // x為其父節點的左子節點
x->parent->left = y;
y->right = x;
x->parent = y;
}
2. 紅黑樹
linux內核紅黑樹的算法都定義在
linux-2.6.38.8/include/linux/rbtree.h和linux-2.6.38.8/lib/rbtree.c兩個文件中。
2.1 結構體
紅黑樹和我們以
struct rb_node
{
unsigned long rb_parent_color;
#define RB_RED 0
#define RB_BLACK 1
struct rb_node *rb_right;
struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
這里的巧妙之處是使用成員rb_parent_color同時存儲兩種數據，一是其雙親結點的地址，另一是此結點的著色。__attribute__((aligned(sizeof(long))))屬性保證了紅黑樹中的每個結點的首地址都是32位對齊的（在32位機上），也就是說每個結點首地址的bit[1]和bit[0]都是0，因此就可以使用bit[0]來存儲結點的顏色屬性而不干擾到其雙親結點首地址的存儲。
操作rb_parent_color的函數：
#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3)) //獲得其雙親結點的首地址
#define rb_color(r) ((r)->rb_parent_color & 1) //獲得顏色屬性
#define rb_is_red(r) (!rb_color(r)) //判斷顏色屬性是否為紅
#define rb_is_black(r) rb_color(r) //判斷顏色屬性是否為黑
#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0) //設置紅色屬性
#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0) //設置黑色屬性
static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) //設置其雙親結點首地址的函數
{
rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
}
static inline void rb_set_color(struct rb_node *rb, int color) //設置結點顏色屬性的函數
{
rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
}
初始化新結點：
static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
struct rb_node ** rb_link)
{
node->rb_parent_color = (unsigned long )parent; //設置其雙親結點的首地址(根結點的雙親結點為NULL),且顏色屬性設為黑色
node->rb_left = node->rb_right = NULL; //初始化新結點的左右子樹
*rb_link = node; //指向新結點
}
指向紅黑樹根結點的指針：
struct rb_root
{
struct rb_node *rb_node;
};
#define RB_ROOT (struct rb_root) { NULL, } //初始化指向紅黑樹根結點的指針
#define rb_entry(ptr, type, member) container_of(ptr, type, member) //用來獲得包含struct rb_node的結構體的首地址
#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL) //判斷樹是否為空
#define RB_EMPTY_NODE(node) (rb_parent(node) == node) //判斷node的雙親結點是否為自身
#define RB_CLEAR_NODE(node) (rb_set_parent(node, node)) //設置雙親結點為自身
2.2 插入
首先像二叉查找樹一樣插入一個新結點，然后根據情況作出相應的調整，以使其滿足紅黑樹的顏色屬性（其實質是維持紅黑樹的平衡）。
函數rb_insert_color使用while循環不斷地判斷雙親結點是否存在，且顏色屬性為紅色。
若判斷條件為真，則分成兩部分執行后續的操作：
（1）、當雙親結點是祖父結點左子樹的根時，則：
a、存在叔父結點，且顏色屬性為紅色。
b、當node是其雙親結點右子樹的根時，則左旋，然后執行第c步。
c、當node是其雙親結點左子樹的根時。
（2）當雙親結點是祖父結點右子樹的根時的操作與第（1）步大致相同，這里略過不談。
若為假，則始終設置根結點的顏色屬性為黑色。
void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
struct rb_node *parent, *gparent;
while ((parent = rb_parent(node)) && rb_is_red(parent)) //雙親結點不為NULL，且顏色屬性為紅色
{
gparent = rb_parent(parent); //獲得祖父結點
if (parent == gparent->rb_left) //雙親結點是祖父結點左子樹的根
{
{
register struct rb_node *uncle = gparent->rb_right; //獲得叔父結點
if (uncle && rb_is_red(uncle)) //叔父結點存在，且顏色屬性為紅色
{
rb_set_black(uncle); //設置叔父結點為黑色
rb_set_black(parent); //設置雙親結點為黑色
rb_set_red(gparent); //設置祖父結點為紅色
node = gparent; //node指向祖父結點
continue; //繼續下一個while循環
}
}
if (parent->rb_right == node) //當node是其雙親結點右子樹的根時
{
register struct rb_node *tmp;
__rb_rotate_left(parent, root); //左旋
tmp = parent; //調整parent和node指針的指向
parent = node;
node = tmp;
}
rb_set_black(parent); //設置雙親結點為黑色
rb_set_red(gparent); //設置祖父結點為紅色
__rb_rotate_right(gparent, root); //右旋
} else { // !(parent == gparent->rb_left)
{
register struct rb_node *uncle = gparent->rb_left;
if (uncle && rb_is_red(uncle))
{
rb_set_black(uncle);
rb_set_black(parent);
rb_set_red(gparent);
node = gparent;
continue;
}
}
if (parent->rb_left == node)
{
register struct rb_node *tmp;
__rb_rotate_right(parent, root);
tmp = parent;
parent = node;
node = tmp;
}
rb_set_black(parent);
rb_set_red(gparent);
__rb_rotate_left(gparent, root);
} //end if (parent == gparent->rb_left)
} //end while ((parent = rb_parent(node)) && rb_is_red(parent))
rb_set_black(root->rb_node);
}
2.3 刪除
像二叉查找樹的刪除操作一樣，首先需要找到所需刪除的結點，然后根據該結點左右子樹的有無分為三種情形：
若node結點的顏色屬性為黑色，則需要調用__rb_erase_color函數來進行調整。
void rb_erase(struct rb_node *node, struct rb_root *root)
{
struct rb_node *child, *parent;
int color;
if (!node->rb_left) //刪除結點無左子樹
child = node->rb_right;
else if (!node->rb_right) //刪除結點無右子樹
child = node->rb_left;
else //左右子樹都有
{
struct rb_node *old = node, *left;
node = node->rb_right;
while ((left = node->rb_left) != NULL)
node = left;
if (rb_parent(old)) {
if (rb_parent(old)->rb_left == old)
rb_parent(old)->rb_left = node;
else
rb_parent(old)->rb_right = node;
} else
root->rb_node = node;
child = node->rb_right;
parent = rb_parent(node);
color = rb_color(node);
if (parent == old) {
parent = node;
} else {
if (child)
rb_set_parent(child, parent);
parent->rb_left = child;
node->rb_right = old->rb_right;
rb_set_parent(old->rb_right, node);
}
node->rb_parent_color = old->rb_parent_color;
node->rb_left = old->rb_left;
rb_set_parent(old->rb_left, node);
goto color;
} //end else
parent = rb_parent(node); //獲得刪除結點的雙親結點
color = rb_color(node); //獲取刪除結點的顏色屬性
if (child)
rb_set_parent(child, parent);
if (parent)
{
if (parent->rb_left == node)
parent->rb_left = child;
else
parent->rb_right = child;
}
else
root->rb_node = child;
color:
if (color == RB_BLACK) //如果刪除結點的顏色屬性為黑色，則需調用__rb_erase_color函數來進行調整
__rb_erase_color(child, parent, root);
}
2.4 遍歷
rb_first和rb_next函數可組成中序遍歷，即以升序遍歷紅黑樹中的所有結點。
struct rb_node *rb_first(const struct rb_root *root)
{
struct rb_node *n;
n = root->rb_node;
if (!n)
return NULL;
while (n->rb_left)
n = n->rb_left;
return n;
}
struct rb_node *rb_next(const struct rb_node *node)
{
struct rb_node *parent;
if (rb_parent(node) == node)
return NULL;
/* If we have a right-hand child, go down and then left as far
as we can. */
if (node->rb_right) {
node = node->rb_right;
while (node->rb_left)
node=node->rb_left;
return (struct rb_node *)node;
}
/* No right-hand children. Everything down and left is
smaller than us, so any 'next' node must be in the general
direction of our parent. Go up the tree; any time the
ancestor is a right-hand child of its parent, keep going
up. First time it's a left-hand child of its parent, said
parent is our 'next' node. */
while ((parent = rb_parent(node)) && node == parent->rb_right)
node = parent;
return parent;
}
