最近覺得C++生疏了，拿出侯捷的《STL源碼剖析》翻了翻，看到C++ set，map底層實現機制，其中采用的就是紅黑樹數據結構，另外Linux內核對內存管理和進程調度都用到了紅黑樹，看來它不能讓人小視。自己從網上和書上重新看了下紅黑樹，把個人的理解放到博客上，跟大家討論，也作為自己的重新梳理的方式。
紅黑樹(Red-Black Tree)
它是在1972 年由Rudolf Bayer 發明的，他稱之為"對稱二叉B 樹"，它現代的名字是在Leo J. Guibas 和Robert Sedgewick 於1978 年寫的一篇論文中獲得的。它是復雜的，但它的操作有著良好的最壞情況運行時間，並且在實踐中是高效的: 它可以在O(log n)時間內做查找，插入和刪除，這裡的n 是樹中元素的數目。
紅黑樹本身是二叉搜索樹，同時它應該始終滿足五個性質：
紅黑樹每個節點顏色非紅即黑；
根節點顏色必須為黑色；
每個葉節點(指的NULL指針節點)顏色均為黑；
不可以出現相鄰的兩個紅色節點；
對於每個節點，其左右子樹中的黑色節點個數必須相等；
一棵正常的紅黑樹如下圖(引自wiki)：
紅黑樹的難點在於插入和刪除操作涉及到的紅黑樹重新調整問題，關於原理性問題，有篇文章《紅黑樹原理詳解》，作者：余強. 講的比較清楚，也可以參照《CLRS》第13章紅黑樹的描述，以下主要結合c語言實現代碼加注釋的方式進行分析，編完代碼後進行了一定的測試，如果還存在問題，可回帖反饋，我會進行更改，謝謝。
插入操作：
新插入一個節點時，其顏色未定，可以選擇黑色也可以選擇紅色，但是仔細看下上述紅黑樹5個性質，會發現，插入黑色節點必然會導致性質5被破壞(空樹除外)，而如果插入紅色節點，則可能破壞性質4，這其中有一定的幾率無需調整紅黑樹(父節點為黑色)，因此插入的新節點顏色設置為紅色，以下插入操作均不考慮是空樹和父節點是黑色的情況，因為這兩種情況無需進行調整。
而如果發生上面說的破壞性質4，即新插入節點與父節點均是紅色的情況，則我們需要將這兩個相鄰紅色節點分開，以使性質4重新被滿足，而涉及到的調整則需要看新插入節點的父節點、叔父節點以及祖父節點顏色而定，可以分情況討論之；
首先考慮叔父節點的顏色，這裡以叔父節點的顏色來劃分接下來的調整操作是因為插入的新節點與其父節點均為紅色，目的為了將這兩個紅色節點分開，可以通過性質推理知祖父節點必然為黑色，因為插入新節點前，樹是滿足性質的，而父節點顏色為紅色，因此祖父節點必然為黑色。調整顏色過程中，如果需要改變父節點顏色，則必然需要考慮叔父節點，因此叔父節點是插入操作分情況討論的關鍵點。
在介紹插入後紅黑樹重新調整前，首先引入左旋操作和右旋操作，在紅黑樹所有調整中，均采用左右旋操作解決節點移動問題，左右旋操作並不破壞二叉搜索樹的性質，因此不會引入額外的重新對紅黑樹進行排序的負擔，具體左右旋操作可參考其他紅黑樹相關文章或下文中對於左右旋操作的代碼分析加注釋；
重回正題，首先對插入操作所需要的調整進行分情況討論，再次強調父節點為黑色的情況不分析，因為無需作過多調整，所以下面操作中父節點顏色均為紅色：
叔父節點顏色為黑色：
以上兩種情況為插入節點的父節點在祖父節點的左子樹情況，當位於右子樹時，情況類似。
以上兩種情況，即新插入節點分別為外側插入和內側插入時，需要將父節點和新節點的相鄰紅色分開，該兩種情況下叔父節點應該為NULL節點(如果有不正確，請大家指正
)
因此調整操作是以祖父節點為基點，父節點和祖父節點的連接為軸進行右旋轉（內側插入即第二種情況必須先以父節點為基點進行左旋調整），然後改變父節點和祖父節點的顏色。
新節點外側插入情況：以祖父節點為基點，右單選，改變父節點和祖父節點顏色；
新節點內側插入情況：先對父節點左單選（如果這裡不進行左旋轉，則經過下一步的右旋轉後，新節點即成為祖父節點的左孩子，如果祖父節點為紅色，則會引入額外的調整和麻煩），改變新節點和祖父節點顏色，再對祖父節點右單旋；
叔父節點顏色為紅色
該情況下比較簡單，因為叔父和父節點都是紅色，而且祖父節點為黑色，則將祖父節點顏色變為紅色，父節點和叔父節點顏色為黑色，即可消除相鄰的兩個紅色節點而且不改變相應的黑高度，此時如果曾祖父節點顏色為黑色，則調整結束，如果曾祖父節點顏色為紅色，則可將祖父節點視為新節點，遞歸新插入情況，迭代向上處理。
總體來說插入情況相對比較簡單，主要涉及上述幾種操作，以下是c語言相關紅黑樹插入實現代碼：
/*
* key:新插入節點鍵值,root:紅黑樹根節點
* 紅黑樹節點插入
* 1、插入新節點
* 2、旋轉紅黑樹並做顏色調整
*/
rb_node_t *rb_tree_insert(int key, rb_node_t* root)
{
rb_node_t *last_node;
rb_node_t *curnode;
/* 創建節點 */
rb_node_t *node = (rb_node_t *)malloc(sizeof(rb_node_t));
node->key = key;
curnode = root; //temp node,just for save something
/* 樹為空 */
if (NULL == root)
{
node->color = black;
node->left_child = NULL;
node->right_child = NULL;
node->parent = NULL;
return node;
}
/* 向下搜索，直到找到相應的位置可以插入 */
while (curnode)
{
last_node = curnode;
node->key > curnode->key ? (curnode = curnode->right_child) : (curnode = curnode->left_child);
}
/* 判斷插入搜索到的節點的左孩子還是右孩子 */
if (node->key > last_node->key)
last_node->right_child = node;
else
last_node->left_child = node;
node->parent = last_node; //回馬槍設置父節點
node->left_child = NULL;
node->right_child = NULL;
node->color = red;
/* 重新使紅黑樹調整為平衡狀態 */
root = rb_tree_rebalance(node, root);
return root;
}
刪除操作：
紅黑樹節點刪除操作後的調整相比插入操作更加復雜，但是同樣可以分情況討論之。
首先紅黑樹刪除同樣采取跟二叉搜索樹同樣的刪除方式，即如果需要刪除節點A，則將A左子樹中最大的節點(即最右邊節點)和右子樹中最小的節點(最左邊的節點)刪除，然後用刪除節點替換A節點。
如下圖：
需要刪除8節點時，先搜索到7或9節點，將對應節點刪除掉，同時將7或9的節點替換8的節點，詳細參考請查閱二叉搜索樹的刪除。
