红黑树的性质

  1. 根节点是黑色的
  2. 如果一个节点是红色的，则它的两个孩子节点是黑色的
  3. 对于每个节点，从该节点到其所有厚点叶节点的简单路径上，均包含相同数目的黑色节点
  4. 每个叶子节点都是黑色的（此叶子节点指的是空节点）

    红黑树的节点表示

    红黑树 - 图1
    看图说节点
    红黑树的节点参数，

    一个指向上面的节点定义为_parent 一个指向左边的节点的节点指针 _left 一个指向右边的 _right 一个pair类型的值 一个颜色的识别

当然这么写参数那得来个构造函数了，“细节”。

  1. template<class K,class V>
  2. struct RBNode {
  3.     //各个节点
  4.     RBNode<K, V>* _parent;
  5.     RBNode<K, V>* _left;
  6.     RBNode<K, V>* _right;
  7.     //key-value
  8.     pair<K, V> _kv;
  9.     //颜色
  10.     COLOR _color;
  11.     RBNode(const pair<K, V>& kv = pair<K, V>())
  12.         :_parent(nullptr)
  13.         , _left(nullptr)
  14.         , _right(nullptr)
  15.         , _kv(kv)
  16.         //新申请的节点定义为RED，黑色的加入，会导致其他所有路径的黑色都遭到破坏；
  17.         , _color(RED) {
  18.     }
  19. };

对树的类进行定义：
红黑树 - 图2
红黑树的头节点——header
指向如图上图：具体下面再写

  1. template<class K,class V>
  2. class RBTree {
  3. public:
  4.     //类型定义,用Node表示RBNode<K,V>
  5.     typedef RBNode<K,V> Node;
  6.     RBTree()
  7.         :_header(new Node) {
  8.         //创建空树
  9.         _header->_left = _header->_right = _header;
  10.     }
  11. private:
  12.     Node* _header;
  13. };

红黑树的插入：
当插入c节点时，为了满足性质，需要对节点进行调整，为了保证调整最优；
如果插入节点的父节点（u）和叔叔节点（u）为红色，那么只需要改变叔叔节点（u）和父节点（p）颜色为黑色，祖父节（g）为黑色即可；
当然如果祖父节点（g) 为根节点，再把其变为黑色；
红黑树 - 图3
不是根节点，向上调整；
红黑树 - 图4
【文章福利】需要C/C++ Linux服务器架构师学习资料加群812855908（资料包括C/C++，Linux，golang技术，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，ffmpeg等）
红黑树 - 图5
结构右旋：

写一个左旋的操作，在树结构变化时可高效的改变保证结构性质； 如果 当出现情况1： 插入节点为c，当它的叔叔节点为黑色，或者叔叔节点不存在，操作相同；

红黑树 - 图6

  1. 记录三个节点，只有这三个节点指向变化；
  2. 由图：
  3. 用parent表示g，
  4. 用subL表示p，
  5. 用subLR表示p的右子节点即c；
  6. 用pparent表示g的父节点；
  7.     //          parent
  8.     //    subL
  9.     //            subLR    
  10.     void RotateR(Node* parent) {
  11.         Node* subL = parent->_left;
  12.         Node* subLR = subL->_right;
  13.         //改变节点指向：
  14.         subL->_right = parent;
  15.         parent->_left = subLR;
  16.         //如果存在父节点存在，如果为nullptr则没有父节点；
  17.         if (subLR)
  18.             subLR->_parent = parent;
  19.         //判断根
  20.         if (parent == _header->_parent) {
  21.             _header->_parent = subL;
  22.             subL->_parent = _header;
  23.         }
  24.         //不是根
  25.         else {
  26.             Node* pparent = parent->_parent;
  27.             subL->_parent = pparent;
  28.             if (pparent->_left == parent)
  29.                 pparent->_left = subL;
  30.             else
  31.                 pparent->_right = subL;
  32.         }
  33.         //先要将parent的父节点赋值出去，才能改变paremt的父节点；
  34.         parent->_parent = subL;
  35.     }

结构左旋：
如图顺序（未画完全，子节点仍然有且满足性质）
红黑树 - 图7

  1. 记录三个节点，只有这三个节点指向变化；（操作和右旋思路相同）
  2. 由图：
  3. 用pparent表示p的父节点；
  4.     //            parent
  5.     //                    subR
  6.     //            subRL                
  7.     void RotateL(Node* parent) {
  8.         Node* subR = parent->_right;
  9.         Node* subRL = subR->_left;
  10.         subR->_left = parent;
  11.         parent->_right = subRL;
  12.         if (subRL) {
  13.             subRL->_parent = parent;
  14.         }
  15.         if (_header->_parent == parent) {
  16.             _header->_parent = subR;
  17.             subR->_parent = _header;
  18.         }
  19.         else {
  20.             Node* pparent = parent->_parent;
  21.             subR->_parent = pparent;
  22.             if (pparent->_left == parent)
  23.                 pparent->_left = subR;
  24.             else
  25.                 pparent->_right = subR;
  26.         }
  27.         parent->_parent = subR;
  28.     }

头节点指向的左右节点：
如图：header头节点指向最左最右的节点；
红黑树 - 图8
找红黑树的最左节点：

  1. //最左节点
  2.     Node* leftMost() {
  3.         Node* cur = _header->_parent;
  4.         while (cur && cur->_left) {
  5.             cur = cur->_left;
  6.         }
  7.         return cur;
  8.     }

找红黑树的最右节点：

  1. //最右节点
  2.     Node* rightMost() {
  3.         Node* cur = _header->_parent;
  4.         while (cur && cur->_right) {
  5.             cur = cur->_right;
  6.         }
  7.         return cur;
  8.     }

红黑树的插入情况分析：
情况1：插入节点的父节点颜色为黑色；
处理1：直接插入;
情况2：插入节点的父节点为红色，叔叔节点存在且为红色；
处理2：插入后叔叔节点和父节点颜色变黑，祖父节点颜色变红，向上遍历查看情况；
情况3：父节点为红色，叔叔节点存在为黑色或不存在，插入节点为父节点的左子树，父节点为祖父节点的左子树；
处理3：进行结构右旋操作（RotateR）；
情况4：和情况3的结构调整相反父节点为红色，叔叔节点存在为黑色或不存在，插入节点为父节点的右子树，父节点为祖父节点的右子树；
处理4：进行结构左旋操作（RotateL）；
情况5：和情况6结构调整相反父节点为红色，叔叔节点存在为黑色或不存在，插入节点为父节点的左子树，父节点为祖父节点的右子树；
处理5：先以父节点为根，先右旋操作（RotateR），再以祖父节点为根，左旋操作（RotateL）；
情况6：父节点为红色，叔叔节点存在为黑色或不存在，插入节点为父节点的右子树，父节点为祖父节点的左子树；
处理6：先以父节点为根，左旋操作（RotateL），再以祖父节点为根，右旋操作（RotateR）；
上图:（个情况）
情况1：
红黑树 - 图9
情况2：
红黑树 - 图10
情况3：
红黑树 - 图11
情况4：
和情况3相反，自己画去；
情况5：
情况6相反，自己画去；
情况6
红黑树 - 图12

上代码：

  1. //插入
  2.     bool insert(const pair<K,V>& kv) {
  3.         //1.搜索树颜色
  4.         //空树：_header->parent:nullptr
  5.         if (_header->_parent == nullptr) {
  6.             //创建根节点
  7.             Node* root = new Node(kv);
  8.             _header->_parent = root;
  9.             root->_parent = _header;
  10.             _header->_left = _header->_right = root;
  11.             //根节点是黑色
  12.             root->_color = BLACK;
  13.             return true;
  14.         }
  16.         //从根节点开始搜索
  17.         //正常插入
  18.         Node* cur = _header->_parent;
  19.         Node* parent = nullptr;
  20.         while (cur) {
  21.             parent = cur;
  22.             //和key值进行比较
  23.             //kv： pair<K,V>, key:pair.first
  24.             if (cur->_kv.first == kv.first) {
  25.                 //key值存在，不允许插入
  26.                 return false;
  27.             }
  29.             else if (cur->_kv.first > kv.first) {
  30.             //向小的找,左子树去找
  31.                 cur = cur->_left;
  32.             }
  33.             else {
  34.             //向大的找,右子树去找
  35.                 cur = cur->_right;
  36.             }
  37.         }//找到了
  39.         //创建待插入节点
  40.         cur = new Node(kv);
  41.         if (parent->_kv.first > cur->_kv.first)
  42.             parent->_left = cur;//比较大小，插在左右那个位置；
  43.         else
  44.             parent->_right = cur;
  45.         cur->_parent = parent;
  46.         //2.调整结构或者修改颜色
  47.     //判断是否至少有三层；
  48.         while (cur != _header->_parent && cur->_parent->_color == RED) {
  49.             parent = cur->_parent;
  50.             Node* gfather = parent->_parent;
  51.             //可能出现情况6，情况3
  52.             if (gfather->_left == parent) {
  53.                 Node* uncle = gfather->_right;
  54.                 //情况2：uncle存在，并且都是红色
  55.                 if (uncle && uncle->_color == RED) {
  56.                     parent->_color = uncle->_color = BLACK;
  57.                     gfather->_color = RED;
  58.                     //继续向上更新
  59.                     cur = gfather;
  60.                 }
  61.                 //
  62.                 else {
  63.                     cout << "Rotate" << endl;
  64.                     //双旋结构
  65.                     //情况6：
  66.                     if (cur == parent->_right) {
  67.                         RotateL(parent);
  68.                         swap(cur, parent);
  69.                     }
  70. //经过第一次左旋后，情况6 与情况3 只有cur节点和父节点的指向不一样，
  71. //经过swap两者后，接下来操作相同都为右旋；
  72.                     RotateR(gfather);
  73.                     parent->_color = BLACK;
  74.                     gfather->_color = RED;
  75.                     break;
  76.                 }
  77.             }
  78.             else {
  79.                 //gfather->_right=parent的情况；
  80.                 //情况4，情况5,；
  81.                 //处理与情况3，情况6相反；
  82.                 Node* uncle = gfather->_right;
  83.                 //uncle存在，且都是红色，最简
  84.                 if (uncle && uncle->_color == RED) {
  85.                     parent->_color = uncle->_color = BLACK;
  86.                     gfather->_color = RED;
  87.                     cur = gfather;
  88.                 }
  89.                 //情况3：uncle不存在，或者uncle存在为黑色
  90.                 //双旋结构
  91.                 else {
  92.                     //        gfather
  93.                     //    uncle        parent  
  94.                     //             cur
  95.                     //
  96.                     if (cur == parent->_left) {
  97.                         RotateR(parent);
  98.                         swap(cur, parent);
  99.                     }
  100.                     RotateL(gfather);
  101.                     parent->_color = BLACK;
  102.                     gfather->_color = RED;
  103.                     break;
  104.                 }
  105.             }
  106.         }
  107.         //根节点的颜色改成黑的；
  108.         _header->_parent->_color = BLACK;
  109.         //更新header左右指向
  110.         _header->_left = leftMost();
  111.         _header->_right = rightMost();
  112.     }

中序遍历进行打印：

  1. //对中序遍历进行封装：
  2.     void inorder() {
  3.         _inorder(_header->_parent);
  4.         cout << endl;
  5.     }
  6.     //使用递归从叶子节点开始；
  7.     //1.打印最左节点，
  8.     //2.打印此节点
  9.     //3.打印右节点
  10.     void _inorder(Node* root) {
  11.         if (root) {
  12.             _inorder(root->_left);
  13.             cout << root->_kv.first << "--->" << root->_kv.second << endl;
  14.             _inorder(root->_right);
  15.         }
  16.     }

判断是否满足红黑树的性质：

  1. //红黑树：
  2.     //1.根：黑色
  3.     //2.每条路径黑色个数相同
  4.     //3.红色不能连续
  5.     bool isBalance() {
  6.         if (_header->_parent == nullptr)
  7.             return true;//只有头节点也是满足红黑树
  8.         Node* root = _header->_parent;
  9.         //1.判断根节点的颜色
  10.         if (root->_color == RED)
  11.             return false;
  12.         //统计一条路劲的黑色节点个数
  13.         int bCount = 0;
  14.         Node* cur = root;
  15.         while (cur) {
  16.             if (cur->_color == BLACK)
  17.                 ++bCount;
  18.             cur = cur->_left;
  19.         }
  20.         //遍历每一条路径
  21.         int curBCount = 0;
  22.         return _isBalance(root, bCount, curBCount);
  23.     }
  24.     bool _isBalance(Node* root, int& bCount, int curBCount) {
  25.         //当root为空，一条路径遍历结束
  26.         if(root == nullptr){
  27.         //判断黑色节点个数是否相同
  28.         if (bCount != curBCount)
  29.             return false;
  30.         else
  31.             return true;
  32.         }
  33.         //判断是否为黑节点
  34.         if (root->_color == BLACK)
  35.             ++curBCount;
  36.         //判断红色节点是否有连续
  37.         if (root->_parent && root->_color == RED
  38.             && root->_parent->_color == RED) {
  39.             cout << "data: " << root->_kv.first << "--->" << root->_kv.second << endl;
  40.             return false;
  41.         }
  42.         return _isBalance(root->_left, bCount, curBCount) 
  43.             && _isBalance(root->_right,bCount, curBCount);
  44.     }

完整代码如下：可直接调试

  1. #include<iostream>
  2. #include<iostream>
  3. #include<utility>
  4. using namespace std;
  5. //设置颜色属性
  6. enum COLOR {
  7.     BLACK,
  8.     RED
  9. };
  10. template<class K,class V>
  11. struct RBNode {
  12.     //typedef bool color;
  13.     //各个节点
  14.     RBNode<K, V>* _parent;
  15.     RBNode<K, V>* _left;
  16.     RBNode<K, V>* _right;
  17.     //key-value
  18.     pair<K, V> _kv;
  19.     //颜色
  20.     COLOR _color;
  21.     RBNode(const pair<K, V>& kv = pair<K, V>())
  22.         :_parent(nullptr)
  23.         , _left(nullptr)
  24.         , _right(nullptr)
  25.         , _kv(kv)
  26.         , _color(RED) {
  27.     }
  28. };
  29. template<class K,class V>
  30. class RBTree {
  31. public:
  32.     //类型定义
  33.     typedef RBNode<K,V> Node;
  34.     RBTree()
  35.         :_header(new Node) {
  36.         //创建空树
  37.         _header->_left = _header->_right = _header;
  38.     }
  39.     //插入
  40.     bool insert(const pair<K,V>& kv) {
  41.         //1.搜索树颜色
  42.         //空树：_header->parent:nullptr
  43.         if (_header->_parent == nullptr) {
  44.             //创建根节点
  45.             Node* root = new Node(kv);
  46.             _header->_parent = root;
  47.             root->_parent = _header;
  48.             _header->_left = _header->_right = root;
  49.             //根节点是黑色
  50.             root->_color = BLACK;
  51.             return true;
  52.         }
  53.         //从根节点开始搜索
  54.         //正常插入
  55.         Node* cur = _header->_parent;
  56.         Node* parent = nullptr;
  57.         while (cur) {
  58.             parent = cur;
  59.             //和key值进行比较
  60.             //kv： pair<K,V>, key:pair.first
  61.             if (cur->_kv.first == kv.first) {
  62.                 //key值不允许重复
  63.                 return false;
  64.             }
  65.             else if (cur->_kv.first > kv.first) {
  66.                 cur = cur->_left;
  67.             }
  68.             else {
  69.                 cur = cur->_right;
  70.             }
  71.         }
  72.         //创建待插入节点
  73.         cur = new Node(kv);
  74.         if (parent->_kv.first > cur->_kv.first)
  75.             parent->_left = cur;
  76.         else
  77.             parent->_right = cur;
  78.         cur->_parent = parent;
  79.         //2.修改颜色或者调整结构
  80.         while (cur != _header->_parent && cur->_parent->_color == RED) {
  81.             parent = cur->_parent;
  82.             Node* gfather = parent->_parent;
  83.             if (gfather->_left == parent) {
  84.                 Node* uncle = gfather->_right;
  85.                 //1.uncle存在，并且都是红色
  86.                 if (uncle && uncle->_color == RED) {
  87.                     parent->_color = uncle->_color = BLACK;
  88.                     gfather->_color = RED;
  89.                     //继续更新
  90.                     cur = gfather;
  91.                 }
  93.                 else {
  94.                     cout << "Rotate" << endl;
  95.                     //双旋结构
  96.                     if (cur == parent->_right) {
  97.                         RotateL(parent);
  98.                         swap(cur, parent);
  99.                     }
  100.                     RotateR(gfather);
  101.                     parent->_color = BLACK;
  102.                     gfather->_color = RED;
  103.                     break;
  104.                 }
  105.             }
  106.             else {
  107.                 //gfather->_right=parent;
  108.                 Node* uncle = gfather->_right;
  109.                 //uncle存在，且都是红色，最简
  110.                 if (uncle && uncle->_color == RED) {
  111.                     parent->_color = uncle->_color = BLACK;
  112.                     gfather->_color = RED;
  113.                     cur = gfather;
  114.                 }
  115.                 //uncle不存在，或者uncle存在为黑色
  116.                 //双旋结构
  117.                 else {
  118.                     //        gfather
  119.                     //    uncle        parent  
  120.                     //             cur
  121.                     //
  122.                     if (cur == parent->_left) {
  123.                         RotateR(parent);
  124.                         swap(cur, parent);
  125.                     }
  126.                     RotateL(gfather);
  127.                     parent->_color = BLACK;
  128.                     gfather->_color = RED;
  129.                     break;
  130.                 }
  131.             }
  132.         }
  133.         //根节点的颜色改成黑的；
  134.         _header->_parent->_color = BLACK;
  135.         //更新header左右指向
  136.         _header->_left = leftMost();
  137.         _header->_right = rightMost();
  138.     }
  139.     //            parent
  140.     //                    subR
  141.     //            subRL                
  142.     void RotateL(Node* parent) {
  143.         Node* subR = parent->_right;
  144.         Node* subRL = subR->_left;
  145.         subR->_left = parent;
  146. parent->_right = subRL;
  147. if (subRL) {
  148.     subRL->_parent = parent;
  149. }
  150. if (_header->_parent == parent) {
  151.     _header->_parent = subR;
  152.     subR->_parent = _header;
  153. }
  154. else {
  155.     Node* pparent = parent->_parent;
  156.     subR->_parent = pparent;
  157.     if (pparent->_left == parent)
  158.         pparent->_left = subR;
  159.     else
  160.         pparent->_right = subR;
  161. }
  162. parent->_parent = subR;
  163.     }
  164.     //          parent
  165.     //        subL
  166.     //            subLR    
  167.     void RotateR(Node* parent) {
  168.         Node* subL = parent->_left;
  169.         Node* subLR = subL->_right;
  170.         subL->_right = parent;
  171.         parent->_left = subLR;
  172.         if (subLR)
  173.             subLR->_parent = parent;
  174.         //判断根
  175.         if (parent == _header->_parent) {
  176.             _header->_parent = subL;
  177.             subL->_parent = _header;
  178.         }
  179.         //不是根
  180.         else {
  181.             Node* pparent = parent->_parent;
  182.             subL->_parent = pparent;
  183.             if (pparent->_left == parent)
  184.                 pparent->_left = subL;
  185.             else
  186.                 pparent->_right = subL;
  187.         }
  188.         parent->_parent = subL;
  189.     }
  190.     //最左节点
  191.     Node* leftMost() {
  192.         Node* cur = _header->_parent;
  193.         while (cur && cur->_left) {
  194.             cur = cur->_left;
  195.         }
  196.         return cur;
  197.     }
  198.     //最右节点
  199.     Node* rightMost() {
  200.         Node* cur = _header->_parent;
  201.         while (cur && cur->_right) {
  202.             cur = cur->_right;
  203.         }
  204.         return cur;
  205.     }
  206.     void inorder() {
  207.         _inorder(_header->_parent);
  208.         cout << endl;
  209.     }
  210.     void _inorder(Node* root) {
  211.         if (root) {
  212.             _inorder(root->_left);
  213.             cout << root->_kv.first << "--->" << root->_kv.second << endl;
  214.             _inorder(root->_right);
  215.         }
  216.     }
  217.     //红黑树：
  218.     //1.根：黑色
  219.     //2.每条路径黑色个数相同
  220.     //3.红色不能连续
  221.     bool isBalance() {
  222.         if (_header->_parent == nullptr)
  223.             return true;
  224.         Node* root = _header->_parent;
  225.         if (root->_color == RED)
  226.             return false;
  227.         //统计一条路劲的黑色节点个数
  228.         int bCount = 0;
  229.         Node* cur = root;
  230.         while (cur) {
  231.             if (cur->_color == BLACK)
  232.                 ++bCount;
  233.             cur = cur->_left;
  234.         }
  235.         //遍历每一条路径
  236.         int curBCount = 0;
  237.         return _isBalance(root, bCount, curBCount);
  238.     }
  239.     bool _isBalance(Node* root, int& bCount, int curBCount) {
  240.         //当root为空，一条路径遍历结束
  241.         if(root == nullptr){
  242.         //判断黑色节点个数是否相同
  243.         if (bCount != curBCount)
  244.             return false;
  245.         else
  246.             return true;
  247.         }
  248.         //判断是否为黑节点
  249.         if (root->_color == BLACK)
  250.             ++curBCount;
  251.         //判断红色节点是否有连续
  252.         if (root->_parent && root->_color == RED
  253.             && root->_parent->_color == RED) {
  254.             cout << "data: " << root->_kv.first << "--->" << root->_kv.second << endl;
  255.             return false;
  256.         }
  257.         return _isBalance(root->_left, bCount, curBCount) 
  258.             && _isBalance(root->_right,bCount, curBCount);
  259.     }
  260. private:
  261.     Node* _header;
  262. };
  263. void test()     {
  264.     RBTree<int, int> rbt;
  265.     int n;
  266.     cin >> n;
  267.     for (int i = n; i > 0; --i) {
  268.         rbt.insert(make_pair(i, i));
  269.     }
  270.     rbt.inorder();
  271.     cout << rbt.isBalance();
  272. }
  273. int main() {
  274.     test();
  275.     return 0;
  276. }