紅黑樹 RBTree

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

1 R-B Tree簡(jiǎn)介

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

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

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

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

3 R-B Tree基本操作

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

3.4 添加操作

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

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

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

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

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

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

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

情況一：被插入的節(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)象說(shuō)明：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，且當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)的另一個(gè)子節(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ù)對(duì)“當(dāng)前節(jié)點(diǎn)”進(jìn)行操作。

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

Case 2 現(xiàn)象說(shuō)明：當(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)象說(shuō)明：當(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<iostream>
using namespace std;
enum Color
{
 BLACK,
 RED
};
template<class K,class V>
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<K, V>* _left;
 RBTreeNode<K, V>* _right;
 RBTreeNode<K, V>* _parent;
 Color _col;
 K _key;
 V _value; 
};
template<class K,class V>
class RBTree
{
 typedef RBTreeNode<K, V> 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 <key)
  {
   parent->_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<int, int> 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)用比較廣泛，主要是用它來(lái)存儲(chǔ)有序的數(shù)據(jù)，它的時(shí)間復(fù)雜度是O(lgn)，效率非常之高。
例如，Java中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虛擬內(nèi)存的管理，都是通過(guò)紅黑樹去實(shí)現(xiàn)的。

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