二叉搜索樹—RBTree（紅黑樹）

       紅黑樹又稱二叉搜索樹，它主要是通過紅和黑兩種顏色（red、black）來標(biāo)識節(jié)點。通過對任何一條從根節(jié)點到葉子節(jié)點路徑上的節(jié)點顏色進行約束，紅黑樹保證最長路徑不超過最短路徑的兩倍，所以說：紅黑樹是近似于平衡的。

■下面是紅黑樹的主要特點：

        （1）紅黑樹的根節(jié)點是黑色的。

        （2）紅黑樹中若一個節(jié)點是紅色的，則它的兩個子節(jié)點必須是黑色的。

        （3）紅黑樹中從該節(jié)點到后代葉節(jié)點的路徑上，黑色節(jié)點數(shù)目是相同的。

       ◆紅黑樹的應(yīng)用：

                 C++庫、linux內(nèi)核、java庫等

       ◆紅黑樹與AVL樹的區(qū)別：

                  紅黑樹和AVL樹都是高效的平衡搜索樹，時間復(fù)雜度都是O(lgN);

                  紅黑樹對平衡的要求不是特別高，它只需要滿足最長路徑不超過最短路徑的兩倍，所以性能相對較高。

■下面是紅黑樹中節(jié)點結(jié)構(gòu)：

enum color      //枚舉節(jié)點的兩種顏色
{
     RED,
     BLACK,
};

template <class K, class V>
struct RBTreeNode
{
     color _col;
     RBTreeNode<K, V>* _left;
     RBTreeNode<K, V>* _right;
     RBTreeNode<K, V>* _parent;
     K _key;
     V _value;
     
     RBTreeNode(const K& key, const V& value)
          :_key(key)
          , _value(value)
          , _left(NULL)
          , _right(NULL)
          , _parent(NULL)
          , _col(RED)          //顏色必須插入的是紅色，因為要保證黑色節(jié)點的個數(shù)是平衡的
     { }
};

■下面分析紅黑樹的插入情況：

（1）

（2）

（3）

■下面是主要的代碼：

#pragma once
//實現(xiàn)紅黑樹的基本功能
/*
1.紅黑樹中的節(jié)點只能是紅色或者黑色
2.紅黑樹的根節(jié)點為黑色
3.紅黑樹的左、右子樹的黑色節(jié)點個數(shù)是相同的
4.紅黑樹中紅色節(jié)點的兩個孩子節(jié)點必須都為黑色節(jié)點
*/

enum color      //枚舉節(jié)點的兩種顏色
{
     RED,
     BLACK,
};

template <class K, class V>
struct RBTreeNode
{
     color _col;
     RBTreeNode<K, V>* _left;
     RBTreeNode<K, V>* _right;
     RBTreeNode<K, V>* _parent;
     K _key;
     V _value;
     
     RBTreeNode(const K& key, const V& value)
          :_key(key)
          , _value(value)
          , _left(NULL)
          , _right(NULL)
          , _parent(NULL)
          , _col(RED)          //顏色必須插入的是紅色，因為要保證黑色節(jié)點的個數(shù)是平衡的
     { }
};

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)      //根節(jié)點為空的情況，必須將根節(jié)點置為黑色
          {
               _root = new Node(key, value);
               _root->_col = BLACK;
               return true;
          }
          Node* cur = _root;
          Node* parent = NULL;
          while (cur)
          {
               if (cur->_key < key)
               {
                    parent = cur;
                    cur = cur->_right;
               }
               else if (cur->_key > key)
               {
                    parent = cur;
                    cur = cur->_left;
               }
               else
               {
                    break;
               }
          }
          
          //尋找到數(shù)據(jù)該插入的位置
          if (parent->_key < key)
          {
               Node* tmp = new Node(key, value);
               parent->_right = tmp;
               tmp->_parent = parent;
          }
          else if (parent->_key > key)
          {
               Node* tmp = new Node(key, value);
               parent->_left = tmp;
               tmp->_parent = parent;
          }
          
      //處理(如果父節(jié)點為黑色，則不用對樹進行調(diào)整，樹保持紅黑樹的狀態(tài))
          while(cur != _root && parent->_col == RED)
          //插入的不是根節(jié)點，且父節(jié)點的顏色為紅
          {
               Node* grandFather = parent->_parent;
               if (parent == grandFather->_left)
               {
                    Node* uncle = grandFather->_right;
                    //情況一：需要將祖父節(jié)點置為紅色，將父親節(jié)點和叔叔節(jié)點置為黑色，
                    //下次直接從祖父節(jié)點向上進行調(diào)整
                    if (uncle != NULL && uncle->_col == RED)    
                    {
                     grandFather->_col = RED;
                     parent->_col = BLACK;
                     uncle->_col = BLACK;
                     cur = grandFather;
                     parent = cur->_parent;
                    }
                    else
                    {
                     //情況二：需要先進行右單旋，然后將父親節(jié)點置為黑色，祖父節(jié)點置為紅色
                      //情況三：需要先進行左單旋，然后就會轉(zhuǎn)化為情況二
                     if (cur == parent->_right && parent->_right != NULL)  //情況三左、右
                     {
                      _RotateL(parent);
                     }
                     parent->_col = BLACK;     
                     grandFather->_col = RED;
                     _RotateR(grandFather);
                    
                    }
               }
               else     //父親節(jié)點為祖父節(jié)點的右節(jié)點
               {
                    Node* uncle = grandFather->_left;
                    //情況一：需要將祖父節(jié)點置為紅色，將父親節(jié)點和叔叔節(jié)點置為黑色，
                    //下次直接從祖父節(jié)點向上進行調(diào)整
                    if (uncle != NULL && uncle->_col == RED)
                    {
                         grandFather->_col = RED;
                         parent->_col = BLACK;
                         uncle->_col = BLACK;
                         cur = grandFather;
                         parent = cur->_parent;
                    }
                    else
                    {
                     //情況二：需要先進行左單旋，然后將父親節(jié)點置為黑色，祖父節(jié)點置為紅色
                     //情況三：需要進行右單旋，然后就會轉(zhuǎn)化為情況二
                         if (cur == parent->_left && parent->_left != NULL)//情況三右、左
                         {
                              _RotateR(parent);
                         }
                         parent->_col = BLACK;
                         grandFather->_col = RED;
                         _RotateL(grandFather);
                    }
               }
          }
          _root->_col = BLACK;
          return true;
     }

     void InOrder()
     {
          _InOrder(_root);
          cout << endl;
     }
     
     bool Check()     //檢查是否為紅黑樹
     {
          int countBlack = 0;
          Node* cur = _root;
          while (cur->_left != NULL)    //統(tǒng)計一條路徑上的黑色節(jié)點的數(shù)目
          {
               if (cur->_col == BLACK)
               {
                    countBlack++;
               }
               cur = cur->_left;
          }
          return _Check(_root, 0, countBlack);
     }
     
protected:
     bool _Check(Node* root, int blackNum, int curBalanceNum)
     {
          if (root == NULL)
          {
               return false;
          }
          if (root->_parent != NULL && root->_col == BLACK)   
          {
               if (root->_parent->_col == RED)
               {
                    return true;
               }
          }
          if (root->_left == NULL && root->_right == NULL)     //遞歸到葉子節(jié)點是的黑色節(jié)點數(shù)目是否相等
          {
               if (blackNum == curBalanceNum)
               {
                    return true;
               }
               else
               {
                    return false;
               }
          }
          return _Check(root->_left, blackNum++, curBalanceNum)
           && _Check(root->_right, blackNum++, curBalanceNum);
     }

     void _InOrder(Node* root)
     {
          if (root == NULL)
          {
               return;
          }
          _InOrder(root->_left);
          cout << root->_key <<":"<<root->_col<<endl;
          _InOrder(root->_right);
     }

     void _RotateL(Node*& parent)     //左單旋
     {
          Node* SubR = parent->_right;    //新建兩個節(jié)點指針
          Node* SubRL = SubR->_left;
          parent->_right = SubRL;        //進行調(diào)整
          if (SubRL)
          {
               SubRL->_parent = parent;
          }
          SubR->_left = parent;
          SubR->_parent = parent->_parent;
          parent->_parent = SubR;
          parent = SubR;
          if (parent->_parent == NULL)     //parent為根節(jié)點的情況
          {
               _root = parent;
          }
          else                             //parent不為根節(jié)點
          {
               Node* ppNode = parent->_parent;
               if (ppNode->_key > parent->_key)
               {
                    ppNode->_left = parent;
               }
               else
               {
                    ppNode->_right = parent;
               }
          }
     }

     void _RotateR(Node*& parent)     //右單旋
     {
          Node* SubL = parent->_left;   //新建兩個節(jié)點指針
          Node* SubLR = SubL->_right;
          parent->_left = SubLR;    //進行調(diào)整
          if (SubLR)
          {
               SubLR->_parent = parent;
          }
          SubL->_right = parent;
          SubL->_parent = parent->_parent;
          parent->_parent = SubL;
          parent = SubL;
          if (parent->_parent == NULL)     //parent為根節(jié)點的情況
          {
               _root = parent;
          }
          else                             //parent不為根節(jié)點
          {
               Node* ppNode = parent->_parent;
               if (ppNode->_key > parent->_key)
               {
                    ppNode->_left = parent;
               }
               else
               {
                    ppNode->_right = parent;
               }
          }
     }
     
protected:
     Node* _root;
};

void Test()
{
     RBTree<int, int> ht;
     ht.Insert(5, 1);
     ht.Insert(9, 1);
     ht.Insert(3, 1);
     ht.Insert(1, 1);
     ht.Insert(8, 1);
     ht.Insert(2, 1);
     ht.Insert(4, 1);
     ht.Insert(6, 1);
     ht.Insert(7, 1);
     
     ht.InOrder();
     cout<<ht.Check()<<endl;
}