概述：R-B Tree，又稱為“紅黑樹”。本文參考了《算法導(dǎo)論》中紅黑樹相關(guān)知識，加之自己的解，然后以圖文的形式對紅黑樹進(jìn)行說明。本文的主要內(nèi)容包括：紅黑樹的特性，紅黑樹的時間復(fù)雜度和它的證明，紅黑樹的左旋、右旋、插入等操作。

創(chuàng)新互聯(lián)建站自2013年創(chuàng)立以來，先為東平等服務(wù)建站，東平等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為東平企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。

1 R-B Tree簡介

  R-B Tree，全稱是Red-Black Tree，又稱為“紅黑樹”，它一種特殊的二叉查找樹。紅黑樹的每個節(jié)點(diǎn)上都有存儲位表示節(jié)點(diǎn)的顏色，可以是紅(Red)或黑(Black)。

紅黑樹的特性:
（1）每個節(jié)點(diǎn)或者是黑色，或者是紅色。
（2）根節(jié)點(diǎn)是黑色。
（3）每個葉子節(jié)點(diǎn)（NIL）是黑色。 [注意：這里葉子節(jié)點(diǎn)，是指為空(NIL或NULL)的葉子節(jié)點(diǎn)！]
（4）如果一個節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的。
（5）從一個節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。

2 R-B Tree時間復(fù)雜度

紅黑樹的時間復(fù)雜度為: O(lgn)
定理：一棵含有n個節(jié)點(diǎn)的紅黑樹的高度至多為2log(n+1).

3 R-B Tree基本操作

 R-B Tree的基本操作是添加、刪除。 添加和刪除操作，都會用到兩個基本的方法：左旋 和 右旋，統(tǒng)稱為旋轉(zhuǎn)。旋轉(zhuǎn)是為了保持紅黑樹的特性而提供的輔助方法，因為當(dāng)我們進(jìn)行添加、刪除節(jié)點(diǎn)時，可能改變紅黑樹的特性(例如，刪除一個黑色節(jié)點(diǎn)之后，就不滿足“從一個節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)”這個特性)；這里，我們就需要旋轉(zhuǎn)方法的輔助來讓樹保持紅黑樹的特性。

3.4 添加操作

  向一顆含有n個節(jié)點(diǎn)的紅黑樹中插入一個節(jié)點(diǎn)，可以在時間O(lgn)內(nèi)完成。

  將節(jié)點(diǎn)z插入紅黑樹T內(nèi)。需要執(zhí)行的操作依次時：首先，將T當(dāng)作一顆二叉樹，將z插入；然后，將z著色為紅色；最后，通過RB-INSERT-FIXUP來對節(jié)點(diǎn)重新著色并旋轉(zhuǎn)，以此來保證刪除節(jié)點(diǎn)后的樹仍然是一顆紅黑樹。

(01) 將T當(dāng)作一顆二叉樹，將z插入。
  因為紅黑樹本身就是一顆二叉樹，所以，我們可以根據(jù)二叉樹的性質(zhì)將z插入。

(02) 將z著色為紅色。
 在介紹為什么將則著色為紅色之前，我們重新溫習(xí)一下紅黑樹的特性：
（1）每個節(jié)點(diǎn)或者是黑色，或者是紅色。
（2）根節(jié)點(diǎn)是黑色。
（3）每個葉子節(jié)點(diǎn)（NIL）是黑色。 [注意：這里葉子節(jié)點(diǎn)，是指為空(NIL或NULL)的葉子節(jié)點(diǎn)！]
（4）如果一個節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的。
（5）從一個節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。

 將插入的節(jié)點(diǎn)著色為紅色，不會違背“特性(5)”；而若將插入的節(jié)點(diǎn)著色為黑色，會違背該特性。

(03) 通過RB-INSERT-FIXUP來對節(jié)點(diǎn)重新著色并旋轉(zhuǎn)。
 因為(02)中插入一個紅色節(jié)點(diǎn)之后，雖然沒有違背“特性(5)”，但是卻可能違背了其它特性(例如，若被插入節(jié)點(diǎn)的父節(jié)點(diǎn)也是紅色；插入后，則違背了“特性(4)”)。我們需要通過RB-INSERT-FIXUP進(jìn)行節(jié)點(diǎn)顏色的調(diào)整以及旋轉(zhuǎn)等工作，讓樹仍然是一顆紅黑樹。

總的來說：當(dāng)節(jié)點(diǎn)z被著色為紅色節(jié)點(diǎn)，并插入二叉樹時，有三種情況。

情況一：被插入的節(jié)點(diǎn)是根節(jié)點(diǎn)。
  直接把此節(jié)點(diǎn)涂為黑色。

情況二：被插入的節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色。
  什么也不需要做。節(jié)點(diǎn)被插入后，仍然是紅黑樹。

情況三：被插入的節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色。
  那么，該情況與紅黑樹的“特性(5)”相沖突。情況三包含了“Case 1”、“Case 2” 和“Case 3”三種情況，情況三的目的是恢復(fù)紅黑樹的特性，它的處理思想是：將紅色的節(jié)點(diǎn)移到根節(jié)點(diǎn)；然后，將根節(jié)點(diǎn)設(shè)為黑色。下面介紹情況三的三種情況。

Case 1：叔叔是紅色

Case 1 現(xiàn)象說明：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，且當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)的另一個子節(jié)點(diǎn)（叔叔節(jié)點(diǎn)）也是紅色。
Case 1 處理策略：
  (01) 將“父節(jié)點(diǎn)”設(shè)為黑色。
  (02) 將“叔叔節(jié)點(diǎn)”設(shè)為黑色。
  (03) 將“祖父節(jié)點(diǎn)”設(shè)為“紅色”。
  (04) 將“祖父節(jié)點(diǎn)”設(shè)為“當(dāng)前節(jié)點(diǎn)”(紅色節(jié)點(diǎn))；即，之后繼續(xù)對“當(dāng)前節(jié)點(diǎn)”進(jìn)行操作。

Case 2：叔叔是黑色，且當(dāng)前節(jié)點(diǎn)是右孩子

Case 2 現(xiàn)象說明：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，且當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的右孩子
Case 2 處理策略：
  (01) 將“父節(jié)點(diǎn)”作為“新的當(dāng)前節(jié)點(diǎn)”。
  (02) 以“新的當(dāng)前節(jié)點(diǎn)”為支點(diǎn)進(jìn)行左旋。

Case 3：叔叔是黑色，當(dāng)前節(jié)點(diǎn)是做孩子

Case 3：叔叔是黑色，且當(dāng)前節(jié)點(diǎn)是左孩子
Case 3 現(xiàn)象說明：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，且當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的左孩子
Case 3 處理策略：
  (01) 將“父節(jié)點(diǎn)”設(shè)為“黑色”。
  (02) 將“祖父節(jié)點(diǎn)”設(shè)為“紅色”。
  (03) 以“祖父節(jié)點(diǎn)”為支點(diǎn)進(jìn)行右旋。

 #include
using namespace std;
enum Color
{
 BLACK,
 RED
};
template
struct RBTreeNode
{
 RBTreeNode(const K& key,const V&value,const Color col = RED)
 :_left(NULL)
 ,_right(NULL)
 ,_parent(NULL)
 ,_col(col)
 ,_key(key)
 ,_value(value)
 {}
 RBTreeNode* _left;
 RBTreeNode* _right;
 RBTreeNode* _parent;
 Color _col;
 K _key;
 V _value; 
};
template
class RBTree
{
 typedef RBTreeNode Node;
public:
 RBTree()
  :_root(NULL)
 {}
 bool Insert(const K& key, const V& value)
 {
  if (_root == NULL)
  {
   _root = new Node(key, value, BLACK);
   return true;
  }
  Node* parent = NULL;
  Node* cur = _root;
  while (cur)
  {
   if (cur->_key > key)
   {
    parent = cur;
    cur = cur->_left;
   }
   else if (cur->_key < key)
   {
    parent = cur;
    cur = cur->_right;
   }
   else
   {
    break;
   }
  }
  cur = new Node(key, value, RED);
  if (parent->_key _right = cur;
   cur->_parent = parent;
  }
  else
  {
   parent->_left = cur;
   cur->_parent = parent;
  }
  //調(diào)色
  while (cur != _root && parent->_col == RED)
  {
   Node* grandfather = parent->_parent;
   if (parent == grandfather->_left)
   {
    Node* uncle = grandfather->_right;
    if (uncle && uncle->_col == RED)
    {
     uncle->_col = parent->_col = BLACK;
     grandfather->_col = RED;
     cur = grandfather;
     parent = cur->_parent;
    }
    //當(dāng)叔叔節(jié)點(diǎn)為黑色，且S為F的右孩子，處理步驟;1 以父節(jié)點(diǎn)進(jìn)行左旋 2將父節(jié)點(diǎn)變黑祖父節(jié)點(diǎn)變紅，3然后進(jìn)行右旋
    else
    {
     if (cur == parent->_right)
     {
      RotateL(parent);
      swap(cur, parent);
     }
     RotateR(grandfather);
     parent->_col = BLACK;
     grandfather->_col = RED;
    }
   }
   else  //往右子樹插
   {
    Node* uncle = grandfather->_left;
    if (uncle && uncle->_col == RED)
    {
     uncle->_col = parent->_col = BLACK;
     grandfather->_col = RED;
     cur = grandfather;
     parent = cur->_parent;
    }
    else
    {
     if (cur == parent->_left)
     {
      RotateR(parent);
      swap(cur, parent);
     }
     RotateL(grandfather);
     parent->_col = BLACK;
     grandfather->_col = RED;
    }
   }
  }
  _root->_col = BLACK;
  return true;
 }

 void InOrder()
 {
  _InOrder(_root);
  cout << endl;
 }
protected:
 void RotateL(Node* parent)
 {
  Node* subR = parent->_right;
  Node* subRL = subR->_left;
  parent->_right = subRL;
  if(subRL)
  {
   subRL->_parent = parent;
  }
  subR->_left = parent;
  subR->_parent = parent->_parent;
  parent = subR;
  if (parent->_parent == NULL)
  {
   _root = parent;
  }
  else
  {
   if (parent->_key < parent->_parent->_key)
   {
    parent->_parent->_left = parent;
   }
   else
   {
    parent->_parent->_right = parent;
   }
  }
 }
 void RotateR(Node* parent)
 {
  Node* subL = parent->_left;
  Node* subLR = subL->_right;
  parent->_left = subLR;
  if(subLR)
  {
   subLR->_parent = parent;
  }
  subL->_right = parent;
  subL->_parent = parent->_parent;
  parent->_parent = subL;
  parent = subL;
  if (parent->_parent == NULL)
  {
   _root = parent;
  }
  else
  {
   if (parent->_key < parent->_parent->_key)
   {
    parent->_parent->_left = parent;
   }
   else
   {
    parent->_parent->_right = parent;
   }
  }
 }
 void _InOrder(Node*& root)
 {
  if (root == NULL)
  {
   return;
  }
  _InOrder(root->_left);
  cout << root->_key << " ";
  _InOrder(root->_right);
 }

protected:
 Node* _root;
};
void TestRBTree()
{
 RBTree t1;
 int a[10] = { 5, 2, 9, 6, 7, 3, 40, 1, 8 };
 for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
 {
  t1.Insert(a[i], i);
  t1.InOrder();
 }
 cout << "IsBalanceTree:" << t1.IsBalanceTree() << endl;
}
int main()
{
 TestRBTree();
 system("pause");
 return 0;
}

4 運(yùn)行結(jié)果

 5 紅黑樹的應(yīng)用

紅黑樹的應(yīng)用比較廣泛，主要是用它來存儲有序的數(shù)據(jù)，它的時間復(fù)雜度是O(lgn)，效率非常之高。
例如，Java中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虛擬內(nèi)存的管理，都是通過紅黑樹去實現(xiàn)的。

這里大致介紹下，紅黑樹和AVL樹的差異。AVL樹也是特殊的二叉樹，它的特性是“任何節(jié)點(diǎn)的左右子樹的高度之差不超過1”。基本上，用到紅黑樹的地方都可以用AVL樹(自平衡二叉查找樹)去替換。但是一般情況下，在執(zhí)行添加、刪除節(jié)點(diǎn)時，AVL樹比紅黑樹執(zhí)行的操作更多一些，效率更低一些；而且紅黑樹也是相對平衡的二叉樹(從一個節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn))。因此，紅黑樹的效率會高更一點(diǎn)。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

當(dāng)前題目：紅黑樹RBTree-創(chuàng)新互聯(lián)
當(dāng)前網(wǎng)址：http://weahome.cn/article/hgjeh.html