资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

二叉搜索树—RBTree(红黑树)

       红黑树又称二叉搜索树,它主要是通过红和黑两种颜色(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)

二叉搜索树—RBTree(红黑树)

(2)

二叉搜索树—RBTree(红黑树)

(3)

二叉搜索树—RBTree(红黑树)

■下面是主要的代码:

#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://cdkjz.cn/article/ihpeeh.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220