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種，只需調整顏色，不需要旋轉樹形）。
整理了很多Linux後臺架構師學習資料，影片，面試題，
請私信
1。2。2。2 黑叔
當叔父結點為黑色時，需要進行旋轉，以下圖示了所有的旋轉可能：
Case 1：
Case 2：
Case 3：
Case 4：
可以觀察到，當旋轉完成後，新的旋轉根全部為黑色，此時不需要再向上回溯進行平衡操作，插入操作完成。需要注意，上面四張圖的“叔”、“1”、“2”、“3”結點有可能為黑哨兵結點。
其實紅黑樹的插入操作不是很難，甚至比AVL樹的插入操作還更簡單些。紅黑樹的插入操作原始碼如下：
// 元素插入操作 insert_unique（）// 插入新值：節點鍵值不允許重複，若重複則插入無效// 注意，返回值是個pair，第一個元素是個紅黑樹迭代器，指向新增節點// 第二個元素表示插入成功與否templatepair：：iterator ， bool>rb_tree：：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（_insert（x ， y ， z） ， true）； else // 否則（插入點之父節點不為最左節點） ——j； // 調整j，回頭準備測試 } if（key_compare（key（j。node） ， KeyOfValue（）（v） ）） // 新鍵值不與既有節點之鍵值重複，於是以下執行安插操作 return pair（_insert（x ， y ， z） ， true）； // 以上，x為新值插入點，y為插入點之父節點，v為新值 // 進行至此，表示新值一定與樹中鍵值重複，那麼就不應該插入新值 return pair（j ， false）；} // 真正地插入執行程式 _insert（）templatetypename：：_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）； // 返回一個迭代器，指向新增節點} // 全域性函式// 重新令樹形平衡（改變顏色及旋轉樹形）// 引數一為新增節點，引數二為根節點rootinline 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；}
