轉(zhuǎn)載請標(biāo)明出處，原文地址：http://blog.csdn.net/hackbuteer1/article/details/7740956

一、紅黑樹概述

     紅黑樹和我們以前學(xué)過的AVL樹類似，都是在進(jìn)行插入和刪除操作時通過特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能。不過自從紅黑樹出來后，AVL樹就被放到了博物館里，據(jù)說是紅黑樹有更好的效率，更高的統(tǒng)計性能。這一點在我們了解了紅黑樹的實現(xiàn)原理后，就會有更加深切的體會。     紅黑樹和AVL樹的區(qū)別在于它使用顏色來標(biāo)識結(jié)點的高度，它所追求的是局部平衡而不是AVL樹中的非常嚴(yán)格的平衡。學(xué)過數(shù)據(jù)結(jié)構(gòu)的人應(yīng)該都已經(jīng)領(lǐng)教過AVL樹的復(fù)雜，但AVL樹的復(fù)雜比起紅黑樹來說簡直是小巫見大巫，紅黑樹才是真正的變態(tài)級數(shù)據(jù)結(jié)構(gòu)。     由于STL中的關(guān)聯(lián)式容器默認(rèn)的底層實現(xiàn)都是紅黑樹，因此紅黑樹對于后續(xù)學(xué)習(xí)STL源碼還是很重要的，有必要掌握紅黑樹的實現(xiàn)原理和源碼實現(xiàn)。     紅黑樹是AVL樹的變種，紅黑樹通過一些著色法則確保沒有一條路徑會比其它路徑長出兩倍，因而達(dá)到接近平衡的目的。所謂紅黑樹，不僅是一個二叉搜索樹，而且必須滿足一下規(guī)則：     1、每個節(jié)點不是紅色就是黑色。     2、根節(jié)點為黑色。     3、如果節(jié)點為紅色，其子節(jié)點必須為黑色。     4、任意一個節(jié)點到到NULL（樹尾端）的任何路徑，所含之黑色節(jié)點數(shù)必須相同。上面的這些約束保證了這個樹大致上是平衡的，這也決定了紅黑樹的插入、刪除、查詢等操作是比較快速的。 根據(jù)規(guī)則4，新增節(jié)點必須為紅色；根據(jù)規(guī)則3，新增節(jié)點之父節(jié)點必須為黑色。當(dāng)新增節(jié)點根據(jù)二叉搜索樹的規(guī)則到達(dá)其插入點時，卻未能符合上述條件時，就必須調(diào)整顏色并旋轉(zhuǎn)樹形，如下圖：假設(shè)我們?yōu)樯蠄D分別插入節(jié)點3、8、35、75，根據(jù)二叉搜索樹的規(guī)則，插入這四個節(jié)點后，我們會發(fā)現(xiàn)它們都破壞了紅黑樹的規(guī)則，因此我們必須調(diào)整樹形，也就是旋轉(zhuǎn)樹形并改變節(jié)點的顏色。

二、紅黑樹上結(jié)點的插入

      在討論紅黑樹的插入操作之前必須要明白，任何一個即將插入的新結(jié)點的初始顏色都為紅色。這一點很容易理解，因為插入黑點會增加某條路徑上黑結(jié)點的數(shù)目，從而導(dǎo)致整棵樹黑高度的不平衡。但如果新結(jié)點的父結(jié)點為紅色時（如下圖所示），將會違反紅黑樹的性質(zhì)：一條路徑上不能出現(xiàn)相鄰的兩個紅色結(jié)點。這時就需要通過一系列操作來使紅黑樹保持平衡。      為了清楚地表示插入操作以下在結(jié)點中使用“新”字表示一個新插入的結(jié)點；使用“父”字表示新插入點的父結(jié)點；使用“叔”字表示“父”結(jié)點的兄弟結(jié)點；使用“祖”字表示“父”結(jié)點的父結(jié)點。插入操作分為以下幾種情況：1、黑父     如下圖所示，如果新節(jié)點的父結(jié)點為黑色結(jié)點，那么插入一個紅點將不會影響紅黑樹的平衡，此時插入操作完成。紅黑樹比AVL樹優(yōu)秀的地方之一在于黑父的情況比較常見，從而使紅黑樹需要旋轉(zhuǎn)的幾率相對AVL樹來說會少一些。2、紅父     如果新節(jié)點的父結(jié)點為紅色，這時就需要進(jìn)行一系列操作以保證整棵樹紅黑性質(zhì)。如下圖所示，由于父結(jié)點為紅色，此時可以判定，祖父結(jié)點必定為黑色。這時需要根據(jù)叔父結(jié)點的顏色來決定做什么樣的操作。青色結(jié)點表示顏色未知。由于有可能需要根結(jié)點到新點的路徑上進(jìn)行多次旋轉(zhuǎn)操作，而每次進(jìn)行不平衡判斷的起始點（我們可將其視為新點）都不一樣。所以我們在此使用一個藍(lán)色箭頭指向這個起始點，并稱之為判定點。2.1 紅叔當(dāng)叔父結(jié)點為紅色時，如下圖所示，無需進(jìn)行旋轉(zhuǎn)操作，只要將父和叔結(jié)點變?yōu)楹谏瑢⒆娓附Y(jié)點變?yōu)榧t色即可。但由于祖父結(jié)點的父結(jié)點有可能為紅色，從而違反紅黑樹性質(zhì)。此時必須將祖父結(jié)點作為新的判定點繼續(xù)向上（迭代）進(jìn)行平衡操作。需要注意的是，無論“父節(jié)點”在“叔節(jié)點”的左邊還是右邊，無論“新節(jié)點”是“父節(jié)點”的左孩子還是右孩子，它們的操作都是完全一樣的（其實這種情況包括4種，只需調(diào)整顏色，不需要旋轉(zhuǎn)樹形）。2.2 黑叔當(dāng)叔父結(jié)點為黑色時，需要進(jìn)行旋轉(zhuǎn)，以下圖示了所有的旋轉(zhuǎn)可能：Case 1:Case 2:Case 3:

Case 4:

      可以觀察到，當(dāng)旋轉(zhuǎn)完成后，新的旋轉(zhuǎn)根全部為黑色，此時不需要再向上回溯進(jìn)行平衡操作，插入操作完成。需要注意，上面四張圖的“叔”、“1”、“2”、“3”結(jié)點有可能為黑哨兵結(jié)點。      其實紅黑樹的插入操作不是很難，甚至比AVL樹的插入操作還更簡單些。紅黑樹的插入操作源代碼如下：[cpp] view plain copy// 元素插入操作  insert_unique()  // 插入新值：節(jié)點鍵值不允許重復(fù)，若重復(fù)則插入無效  // 注意，返回值是個pair，第一個元素是個紅黑樹迭代器，指向新增節(jié)點  // 第二個元素表示插入成功與否  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;    // 根節(jié)點root的父節(jié)點      rb_tree_node* x = root();    // 從根節(jié)點開始      bool comp = true;      while(x != 0)      {          y = x;          comp = key_compare(KeyOfValue()(v) , key(x));    // v鍵值小于目前節(jié)點之鍵值？          x = comp ? left(x) : right(x);   // 遇“大”則往左，遇“小于或等于”則往右      }      // 離開while循環(huán)之后，y所指即插入點之父節(jié)點（此時的它必為葉節(jié)點）      iterator j = iterator(y);     // 令迭代器j指向插入點之父節(jié)點y      if(comp)     // 如果離開while循環(huán)時comp為真（表示遇“大”，將插入于左側(cè)）      {          if(j == begin())    // 如果插入點之父節(jié)點為最左節(jié)點              return pair<iterator , bool>(_insert(x , y , z) , true);          else     // 否則（插入點之父節(jié)點不為最左節(jié)點）              --j;   // 調(diào)整j，回頭準(zhǔn)備測試      }      if(key_compare(key(j.node) , KeyOfValue()(v) ))          // 新鍵值不與既有節(jié)點之鍵值重復(fù)，于是以下執(zhí)行安插操作          return pair<iterator , bool>(_insert(x , y , z) , true);      // 以上，x為新值插入點，y為插入點之父節(jié)點，v為新值        // 進(jìn)行至此，表示新值一定與樹中鍵值重復(fù)，那么就不應(yīng)該插入新值      return pair<iterator , bool>(j , false);  }    // 真正地插入執(zhí)行程序 _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)  {      // 參數(shù)x_ 為新值插入點，參數(shù)y_為插入點之父節(jié)點，參數(shù)v為新值      link_type x = (link_type) x_;      link_type y = (link_type) y_;      link_type z;        // key_compare 是鍵值大小比較準(zhǔn)則。應(yīng)該會是個function object      if(y == header || x != 0 || key_compare(KeyOfValue()(v) , key(y) ))      {          z = create_node(v);    // 產(chǎn)生一個新節(jié)點          left(y) = z;           // 這使得當(dāng)y即為header時，leftmost() = z          if(y == header)          {              root() = z;              rightmost() = z;          }          else if(y == leftmost())     // 如果y為最左節(jié)點              leftmost() = z;          // 維護(hù)leftmost()，使它永遠(yuǎn)指向最左節(jié)點      }      else      {          z = create_node(v);        // 產(chǎn)生一個新節(jié)點          right(y) = z;              // 令新節(jié)點成為插入點之父節(jié)點y的右子節(jié)點          if(y == rightmost())              rightmost() = z;       // 維護(hù)rightmost()，使它永遠(yuǎn)指向最右節(jié)點      }      parent(z) = y;      // 設(shè)定新節(jié)點的父節(jié)點      left(z) = 0;        // 設(shè)定新節(jié)點的左子節(jié)點      right(z) = 0;       // 設(shè)定新節(jié)點的右子節(jié)點      // 新節(jié)點的顏色將在_rb_tree_rebalance()設(shè)定（并調(diào)整）      _rb_tree_rebalance(z , header->parent);      // 參數(shù)一為新增節(jié)點，參數(shù)二為根節(jié)點root      ++node_count;       // 節(jié)點數(shù)累加      return iterator(z);  // 返回一個迭代器，指向新增節(jié)點  }      // 全局函數(shù)  // 重新令樹形平衡（改變顏色及旋轉(zhuǎn)樹形）  // 參數(shù)一為新增節(jié)點，參數(shù)二為根節(jié)點root  inline void _rb_tree_rebalance(_rb_tree_node_base* x , _rb_tree_node_base*& root)  {      x->color = _rb_tree_red;    //新節(jié)點必為紅      while(x != root && x->parent->color == _rb_tree_red)    // 父節(jié)點為紅      {          if(x->parent == x->parent->parent->left)      // 父節(jié)點為祖父節(jié)點之左子節(jié)點          {              _rb_tree_node_base* y = x->parent->parent->right;    // 令y為伯父節(jié)點              if(y && y->color == _rb_tree_red)    // 伯父節(jié)點存在，且為紅              {                  x->parent->color = _rb_tree_black;           // 更改父節(jié)點為黑色                  y->color = _rb_tree_black;                   // 更改伯父節(jié)點為黑色                  x->parent->parent->color = _rb_tree_red;     // 更改祖父節(jié)點為紅色                  x = x->parent->parent;              }              else    // 無伯父節(jié)點，或伯父節(jié)點為黑色              {                  if(x == x->parent->right)   // 如果新節(jié)點為父節(jié)點之右子節(jié)點                  {                      x = x->parent;                      _rb_tree_rotate_left(x , root);    // 第一個參數(shù)為左旋點                  }                  x->parent->color = _rb_tree_black;     // 改變顏色                  x->parent->parent->color = _rb_tree_red;                  _rb_tree_rotate_right(x->parent->parent , root);    // 第一個參數(shù)為右旋點              }          }          else          // 父節(jié)點為祖父節(jié)點之右子節(jié)點          {              _rb_tree_node_base* y = x->parent->parent->left;    // 令y為伯父節(jié)點              if(y && y->color == _rb_tree_red)    // 有伯父節(jié)點，且為紅              {                  x->parent->color = _rb_tree_black;           // 更改父節(jié)點為黑色                  y->color = _rb_tree_black;                   // 更改伯父節(jié)點為黑色                  x->parent->parent->color = _rb_tree_red;     // 更改祖父節(jié)點為紅色                  x = x->parent->parent;          // 準(zhǔn)備繼續(xù)往上層檢查              }              else    // 無伯父節(jié)點，或伯父節(jié)點為黑色              {                  if(x == x->parent->left)        // 如果新節(jié)點為父節(jié)點之左子節(jié)點                  {                      x = x->parent;                      _rb_tree_rotate_right(x , root);    // 第一個參數(shù)為右旋點                  }                  x->parent->color = _rb_tree_black;     // 改變顏色                  x->parent->parent->color = _rb_tree_red;                  _rb_tree_rotate_left(x->parent->parent , root);    // 第一個參數(shù)為左旋點              }          }      }//while      root->color = _rb_tree_black;    // 根節(jié)點永遠(yuǎn)為黑色  }      // 左旋函數(shù)  inline void _rb_tree_rotate_left(_rb_tree_node_base* x , _rb_tree_node_base*& root)  {      // x 為旋轉(zhuǎn)點      _rb_tree_node_base* y = x->right;          // 令y為旋轉(zhuǎn)點的右子節(jié)點      x->right = y->left;      if(y->left != 0)          y->left->parent = x;           // 別忘了回馬槍設(shè)定父節(jié)點      y->parent = x->parent;        // 令y完全頂替x的地位（必須將x對其父節(jié)點的關(guān)系完全接收過來）      if(x == root)    // x為根節(jié)點          root = y;      else if(x == x->parent->left)         // x為其父節(jié)點的左子節(jié)點          x->parent->left = y;      else                                  // x為其父節(jié)點的右子節(jié)點          x->parent->right = y;      y->left = x;      x->parent = y;  }      // 右旋函數(shù)  inline void _rb_tree_rotate_right(_rb_tree_node_base* x , _rb_tree_node_base*& root)  {      // x 為旋轉(zhuǎn)點      _rb_tree_node_base* y = x->left;          // 令y為旋轉(zhuǎn)點的左子節(jié)點      x->left = y->right;      if(y->right != 0)          y->right->parent = x;           // 別忘了回馬槍設(shè)定父節(jié)點      y->parent = x->parent;        // 令y完全頂替x的地位（必須將x對其父節(jié)點的關(guān)系完全接收過來）      if(x == root)          root = y;      else if(x == x->parent->right)         // x為其父節(jié)點的右子節(jié)點          x->parent->right = y;      else                                  // x為其父節(jié)點的左子節(jié)點          x->parent->left = y;      y->right = x;      x->parent = y;  }  轉(zhuǎn)載請標(biāo)明出處，原文地址：http://blog.csdn.net/hackbuteer1/article/details/7740956