红黑树又称二叉搜索树，它主要是通过红和黑两种颜色（red、black）来标识节点。通过对任何一条从根节点到叶子节点路径上的节点颜色进行约束，红黑树保证最长路径不超过最短路径的两倍，所以说：红黑树是近似于平衡的。

创新互联专注于企业成都营销网站建设、网站重做改版、广信网站定制设计、自适应品牌网站建设、H5高端网站建设、商城网站定制开发、集团公司官网建设、外贸网站制作、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为广信等各大城市提供网站开发制作服务。

■下面是红黑树的主要特点：

        （1）红黑树的根节点是黑色的。

        （2）红黑树中若一个节点是红色的，则它的两个子节点必须是黑色的。

        （3）红黑树中从该节点到后代叶节点的路径上，黑色节点数目是相同的。

       ◆红黑树的应用：

                 C++库、linux内核、java库等

       ◆红黑树与AVL树的区别：

                  红黑树和AVL树都是高效的平衡搜索树，时间复杂度都是O(lgN);

                  红黑树对平衡的要求不是特别高，它只需要满足最长路径不超过最短路径的两倍，所以性能相对较高。

■下面是红黑树中节点结构：

enum color      //枚举节点的两种颜色
{
     RED,
     BLACK,
};

template 
struct RBTreeNode
{
     color _col;
     RBTreeNode* _left;
     RBTreeNode* _right;
     RBTreeNode* _parent;
     K _key;
     V _value;
     
     RBTreeNode(const K& key, const V& value)
          :_key(key)
          , _value(value)
          , _left(NULL)
          , _right(NULL)
          , _parent(NULL)
          , _col(RED)          //颜色必须插入的是红色，因为要保证黑色节点的个数是平衡的
     { }
};

■下面分析红黑树的插入情况：

（1）

（2）

（3）

■下面是主要的代码：

#pragma once
//实现红黑树的基本功能
/*
1.红黑树中的节点只能是红色或者黑色
2.红黑树的根节点为黑色
3.红黑树的左、右子树的黑色节点个数是相同的
4.红黑树中红色节点的两个孩子节点必须都为黑色节点
*/

enum color      //枚举节点的两种颜色
{
     RED,
     BLACK,
};

template 
struct RBTreeNode
{
     color _col;
     RBTreeNode* _left;
     RBTreeNode* _right;
     RBTreeNode* _parent;
     K _key;
     V _value;
     
     RBTreeNode(const K& key, const V& value)
          :_key(key)
          , _value(value)
          , _left(NULL)
          , _right(NULL)
          , _parent(NULL)
          , _col(RED)          //颜色必须插入的是红色，因为要保证黑色节点的个数是平衡的
     { }
};

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);
               _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;
               }
          }
          
          //寻找到数据该插入的位置
          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;
          }
          
      //处理(如果父节点为黑色，则不用对树进行调整，树保持红黑树的状态)
          while(cur != _root && parent->_col == RED)
          //插入的不是根节点，且父节点的颜色为红
          {
               Node* grandFather = parent->_parent;
               if (parent == grandFather->_left)
               {
                    Node* uncle = grandFather->_right;
                    //情况一：需要将祖父节点置为红色，将父亲节点和叔叔节点置为黑色，
                    //下次直接从祖父节点向上进行调整
                    if (uncle != NULL && uncle->_col == RED)    
                    {
                     grandFather->_col = RED;
                     parent->_col = BLACK;
                     uncle->_col = BLACK;
                     cur = grandFather;
                     parent = cur->_parent;
                    }
                    else
                    {
                     //情况二：需要先进行右单旋，然后将父亲节点置为黑色，祖父节点置为红色
                      //情况三：需要先进行左单旋，然后就会转化为情况二
                     if (cur == parent->_right && parent->_right != NULL)  //情况三左、右
                     {
                      _RotateL(parent);
                     }
                     parent->_col = BLACK;     
                     grandFather->_col = RED;
                     _RotateR(grandFather);
                    
                    }
               }
               else     //父亲节点为祖父节点的右节点
               {
                    Node* uncle = grandFather->_left;
                    //情况一：需要将祖父节点置为红色，将父亲节点和叔叔节点置为黑色，
                    //下次直接从祖父节点向上进行调整
                    if (uncle != NULL && uncle->_col == RED)
                    {
                         grandFather->_col = RED;
                         parent->_col = BLACK;
                         uncle->_col = BLACK;
                         cur = grandFather;
                         parent = cur->_parent;
                    }
                    else
                    {
                     //情况二：需要先进行左单旋，然后将父亲节点置为黑色，祖父节点置为红色
                     //情况三：需要进行右单旋，然后就会转化为情况二
                         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)    //统计一条路径上的黑色节点的数目
          {
               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)     //递归到叶子节点是的黑色节点数目是否相等
          {
               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 <<":"<_col<_right);
     }

     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->_parent = SubR;
          parent = SubR;
          if (parent->_parent == NULL)     //parent为根节点的情况
          {
               _root = parent;
          }
          else                             //parent不为根节点
          {
               Node* ppNode = parent->_parent;
               if (ppNode->_key > parent->_key)
               {
                    ppNode->_left = parent;
               }
               else
               {
                    ppNode->_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)     //parent为根节点的情况
          {
               _root = parent;
          }
          else                             //parent不为根节点
          {
               Node* ppNode = parent->_parent;
               if (ppNode->_key > parent->_key)
               {
                    ppNode->_left = parent;
               }
               else
               {
                    ppNode->_right = parent;
               }
          }
     }
     
protected:
     Node* _root;
};

void Test()
{
     RBTree 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<
            
            
                                

                    当前文章：二叉搜索树—RBTree（红黑树）                    

                    转载注明：http://chengdu.cdxwcx.cn/article/ihpeeh.html