好吧，nginx是個幌子。主要介紹對紅黑樹的一些理論知識，nginx的主要源碼附在後面。這篇文章並不會面面俱到，我的水平也沒到那個高度。
紅黑樹的特性：
1.紅黑樹是一棵二叉搜索樹。
2.樹上的每個結點或為紅，或為黑。
3.如果一個結點為紅色，那麼它的左右子結點一定為黑色。
4.從根結點到每個葉子結點路徑中經過的黑色結點數是相同的。
5.根結點必須是黑色。
理解這些特性是很重要的。正是因為有這些特性，才保證了紅黑樹的高效。（至於為什麼，我學的還不精，不亂講了。）。
紅黑樹的插入和刪除結點動作本質上還是按照二叉搜索樹的規則來進行的。不過在基本操作完成後，如果違反了紅黑樹的某個特性，這時才需要做一些旋轉操作進行紅黑結點的平衡。所以說，紅黑樹相當一部分的插入和刪除動作就是基本的二叉搜索樹的插入和刪除。本文只列舉那些需要旋轉處理的情況。
紅黑樹的插入操作:
約定如下：當前操作結點為X，X的父節點為P，P的父節點PP，P的兄弟結點為S。
根據規則4，新插入的結點（X）必須是red。如果X的父節點（P）也是red。那麼違反了規則3，必須通過旋轉操作以滿足特性。分為三種情況。
I1：
X為red，P為red，S為black。可以推導出PP也為black。
分為三步：將P置black，將PP置紅，PP右旋轉。（反向同理）。
I2：
X為red，P為red，S為black。可以推導出PP也為black。
直接將P左旋轉，此時變成了I1。按照I1步驟進行平衡（反向同理，方向相反）。
I3：
X為red，P為red，S為red。可以推導出PP為black。
這種情況將P和S置black，將PP置red。這種情況比較特殊，如果PP的父節點PPP也為red呢？那麼以P結點為新的X向上遞歸。直到PPP為黑。如果遞歸到root結點，那麼直接設置root為black即可。（相當於每個路徑中的black結點數同時+1）。
至此，紅黑樹的插入操作理論就全部講完了，我說清了嗎？
紅黑樹的刪除操作:
紅黑樹的刪除操作第一步也遵循二叉搜索樹的規律。
我們假設要刪除的結點為Y。分為三種情況：
至此結點的刪除已經完成，第二步就是平衡紅黑結點，是樹滿足紅黑樹的性質。
約定如下：當前操作結點為X，X的父節點為P,X的兄弟結點為S(注意這裡是X的兄弟)。S的子結點為Sl Sr。
D1：
X為black，S為red。則Sl Sr必為black。
變換後並沒有使樹滿足紅黑樹的性質，而是把它轉換為了另一種情況。（D2 D3 D4）。
D2：
X為black，S為black。則Sl Sr為black。
因為刪除X，所以X分支比S分支少一個black結點。將S置red後，整個子樹左右分支black結點平衡（比其他分支少一個）。所以將P設置為新的X。（這裡理解比較容易，不畫圖了）。
D3：
X為black，S為black。則Sl 為red Sr位black。
S置red Sl置black。 S右旋轉。轉化成D4。
D4：
X為black，S為black。則Sl 為black Sr位red。
將S設置為P的顏色，P置black。置Sr為black。左旋轉P。這樣左子樹缺失的black結點補回來了。刪除完成。
可見當刪除結點有左右子樹時，只有D4，才能真正完成平衡。D1 D2 D3都是向D4轉化。
說到後面自己都懵圈了，感覺要出丑。寫都寫了，還是發出來吧。
為什麼我上面的理論說的這麼簡單粗暴呢？nginx就是這麼寫的呀。
插入代碼：
void
ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
{
ngx_rbtree_node_t **root, *temp, *sentinel;
/* a binary tree insert */
root = (ngx_rbtree_node_t **) &tree->root;
sentinel = tree->sentinel; //sentinel為哨兵，我覺得就是NULL
if (*root == sentinel) {
node->parent = NULL;
node->left = sentinel;
node->right = sentinel;
ngx_rbt_black(node);
*root = node;
return;
}
tree->insert(*root, node, sentinel); //按照二叉搜索樹插入結點
/* re-balance tree */
while (node != *root && ngx_rbt_is_red(node->parent)) { //平衡紅黑結點
if (node->parent == node->parent->parent->left) {
temp = node->parent->parent->right;
if (ngx_rbt_is_red(temp)) { //I3
ngx_rbt_black(node->parent);
ngx_rbt_black(temp);
ngx_rbt_red(node->parent->parent);
node = node->parent->parent;
} else {
if (node == node->parent->right) { //I2
node = node->parent;
ngx_rbtree_left_rotate(root, sentinel, node);
}
ngx_rbt_black(node->parent); //I1
ngx_rbt_red(node->parent->parent);
ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);
}
} else { //反向同理，方向相反。
temp = node->parent->parent->left;
if (ngx_rbt_is_red(temp)) {
ngx_rbt_black(node->parent);
ngx_rbt_black(temp);
ngx_rbt_red(node->parent->parent);
node = node->parent->parent;
} else {
if (node == node->parent->left) {
node = node->parent;
ngx_rbtree_right_rotate(root, sentinel, node);
}
ngx_rbt_black(node->parent);
ngx_rbt_red(node->parent->parent);
ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);
}
}
}
ngx_rbt_black(*root); //無腦設置，任何情況都對。
}
刪除代碼：
void
ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
{
ngx_uint_t red;
ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w;
/* a binary tree delete */
root = (ngx_rbtree_node_t **) &tree->root;
sentinel = tree->sentinel; //哨兵（NULL）
if (node->left == sentinel) {//情況1 2 刪除結點Y為單支結點或者葉子結點
temp = node->right;
subst = node;
} else if (node->right == sentinel) {//情況1 2 刪除結點Y為單支結點或者葉子結點
temp = node->left;
subst = node;
} else { //情況1 情況3 刪除結點Y為雙支結點
subst = ngx_rbtree_min(node->right, sentinel);
if (subst->left != sentinel) {
temp = subst->left;
} else {
temp = subst->right;
}
}
if (subst == *root) {
*root = temp;
ngx_rbt_black(temp);
/* DEBUG stuff */
node->left = NULL;
node->right = NULL;
node->parent = NULL;
node->key = 0;
return;
}
red = ngx_rbt_is_red(subst); //記錄Y的顏色
if (subst == subst->parent->left) { //這裡是按照二叉搜索樹的性質，刪除結點後重新生成二叉搜索樹。
subst->parent->left = temp;
} else {
subst->parent->right = temp;
}
if (subst == node) {
temp->parent = subst->parent;
} else {
if (subst->parent == node) {
temp->parent = subst;
} else {
temp->parent = subst->parent;
}
subst->left = node->left;
subst->right = node->right;
subst->parent = node->parent;
ngx_rbt_copy_color(subst, node);
if (node == *root) {
*root = subst;
} else {
if (node == node->parent->left) {
node->parent->left = subst;
} else {
node->parent->right = subst;
}
}
if (subst->left != sentinel) {
subst->left->parent = subst;
}
if (subst->right != sentinel) {
subst->right->parent = subst;
}
}
/* DEBUG stuff */
node->left = NULL;
node->right = NULL;
node->parent = NULL;
node->key = 0;
if (red) { //刪除結點Y為red 直接退出
return;
}
/* a delete fixup */
while (temp != *root && ngx_rbt_is_black(temp)) { //temp就是上文中的X。開始平衡紅黑結點。直到X為紅色，或者到達root
if (temp == temp->parent->left) {
w = temp->parent->right;
if (ngx_rbt_is_red(w)) { //D1
ngx_rbt_black(w);
ngx_rbt_red(temp->parent);
ngx_rbtree_left_rotate(root, sentinel, temp->parent);
w = temp->parent->right;
}
if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {//D2
ngx_rbt_red(w);
temp = temp->parent;
} else {
if (ngx_rbt_is_black(w->right)) { //D3
ngx_rbt_black(w->left);
ngx_rbt_red(w);
ngx_rbtree_right_rotate(root, sentinel, w);
w = temp->parent->right;
}
ngx_rbt_copy_color(w, temp->parent); //D4
ngx_rbt_black(temp->parent);
ngx_rbt_black(w->right);
ngx_rbtree_left_rotate(root, sentinel, temp->parent);
temp = *root;
}
} else { //反向同理，方向相反。
w = temp->parent->left;
if (ngx_rbt_is_red(w)) {
ngx_rbt_black(w);
ngx_rbt_red(temp->parent);
ngx_rbtree_right_rotate(root, sentinel, temp->parent);
w = temp->parent->left;
}
if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
ngx_rbt_red(w);
temp = temp->parent;
} else {
if (ngx_rbt_is_black(w->left)) {
ngx_rbt_black(w->right);
ngx_rbt_red(w);
ngx_rbtree_left_rotate(root, sentinel, w);
w = temp->parent->left;
}
ngx_rbt_copy_color(w, temp->parent);
ngx_rbt_black(temp->parent);
ngx_rbt_black(w->left);
ngx_rbtree_right_rotate(root, sentinel, temp->parent);
temp = *root;
}
}
}
ngx_rbt_black(temp); //置black
}
我這寫的真是shit啊。研究nginx源碼的湊合著看吧。紅黑樹研究透了卷土重寫。輕點吐槽。
