C++红黑树

个人名片：

作者简介：一名乐于分享在学习道路上收获的大二在校生

个人主页：GOTXX

个人WeChat：ILXOXVJE

本文由GOTXX原创，首发CSDN

系列专栏：零基础学习C语言----- 数据结构的学习之路----C++的学习之路

每日一句：如果没有特别幸运，那就请特别努力！

————————————————

文章目录

• 1.红黑树的概念
• 2 红黑树的性质
• 3 红黑树节点的定义
• 4.红黑树的插入操作（分类详解）
• 5.红黑树与AVL树的比较

  1.红黑树的概念

  红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

  2 红黑树的性质

  性质：

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

  思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？

  首先，要满足黑色节点数目相同，则当只有黑色节点的时候，路径最短，因为红色节点不能连续出现，所以当黑色节点与红色节点交替的时候，路径最长，并且为最短的两倍。

  3 红黑树节点的定义

  enum color                      //颜色{RED,BLACK};templatestruct AVLNode{AVLNode* _left;AVLNode* _right;AVLNode* _parent;pair _kv;color _col;                 //记录节点颜色AVLNode(pair& kv)      :_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED)           //新节点的颜色默认为红色{}};

  新插入节点的颜色为红色的原因？

  原因：因为红黑树有一条规则，就是每条路径的黑色节点数目相等，插入前每条路径的黑色数目是相等的，但是如果插入的是黑色节点的话，那么该条路径的黑色节点的数目就多了一个，直接违反规则，所以插入新节点为红色节点；

  4.红黑树的插入操作（分类详解）

  红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

  1. 按照二叉搜索的树规则插入新节点
  2. 检测新节点插入后，红黑树的性质是否造到破坏

     因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；

     但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

  含义解析：

  cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

  情况一：cur为红色，p为红色，g为黑色，u存在并且为红色

  根据上图进行分析：

  解析：

  这里p与cur都为红色，违反规则，我们不能直接将p的颜色改为黑色，如果直接改为黑色的话，则每条路径的黑色节点数目就变化了，违反规则。

  我们应该将p与u变为红色，g变为黑色，如果g是子树，还需向上调整（比如上图中的下面一种情况），如果g是根节点，则需要变回黑色，因为规则里根节点必须为黑色；

  代码实现

      //这里是一个while循环，只展示了循环体里面的代码//情况一：uncle存在并且为红色if (uncle && uncle->_col == RED){uncle->_col = BLACK;parent->_col = BLACK;grandfather->_col = RED;parent = grandfather;          //如果为子树，则继续向上调整cur = parent; if (_root == grandfather)      //如果g为根节点，则改回黑色{grandfather->_col = BLACK;}}

  情况二：u不存在或则u存在并且为黑色

  下面的分类与AVL树的旋转的分类很类似；

  分析一：u不存在/存在且黑色，并且p为g的左，c为p的左 或则 p为g的右，c为p的右（p，g，c在一条线上）

  当u不存在时：处理方法：单旋+变色

  当u存在时：处理方法：也是单旋+变色

  总结：

  当u存在为黑色或则不存在时，都需要旋转+变色（这里的旋转与上章AVL旋转一样）

  如果c为p的左，并且p为g的左，则右旋

  如果c为p的右，并且p为g的右，则左旋

  变色： 都是p变成黑色，g变为红色

  代码实现

  //p为g左，c为p左if (parent==grandfather->_left && cur==parent->_left){ rotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//p为g右，c为p右else if (parent == grandfather->_right && cur == parent->_right){rotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}

  分析三：u不存在或则存在为黑色，但是p为g的左，c为p的右边 或则 p为g的右，c为p的左（p，g，c不在一条线上）

  当u不存在时：处理方法：双旋+变色

  当u存在时：处理方法：双旋+变色

  总结：

  当g，p，c不在一条街直线上时，需要双旋+变色处理

  旋转方向的判定和AVL树的旋转一样；（上章讲过）

  代码实现：

  //一左一右else if(parent == grandfather->_left && cur == parent->_right){rotateL(parent);rotateR(grandfather);cur->_col = BLACK;parent->_col = BLACK;break;}else if (parent == grandfather->_right && cur == parent->_left){rotateR(parent);rotateL(grandfather);cur->_col = BLACK;parent->_col = BLACK;break;}

  插入总代码

  bool insert(pair& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;}//找插入点Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv > kv){parent = cur;cur = cur->_left;}else if (cur->_kv _right;}else{return false;}}//插入if (cur == parent->left){cur = new Node(kv);parent->_left = cur;cur->_parent = parent;}else if (cur == parent->right){cur = new Node(kv);parent->_right = cur;cur->_parent = parent;}//调节颜色/调节使其满足规则while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent = grandfather->_left){Node* uncle = grandfather->_right;}else{Node* uncle = grandfather->_left;}//情况一：uncle存在并且为红色if (uncle && uncle->_col == RED){uncle->_col = BLACK;parent->_col = BLACK;grandfather->_col = RED;parent = grandfather;          //如果为子树，则继续向上调整cur = parent; if (_root == grandfather)      //如果g为根节点，则改回黑色{grandfather->_col = BLACK;}}//uncle不存在或则存在为黑色else{//p为g左，c为p左if (parent==grandfather->_left && cur==parent->_left){ rotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;break;}//p为g右，c为p右else if (parent == grandfather->_right && cur == parent->_right){rotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;break;}//一左一右else if(parent == grandfather->_left && cur == parent->_right){rotateL(parent);rotateR(grandfather);cur->_col = BLACK;parent->_col = BLACK;break;}else if (parent == grandfather->_right && cur == parent->_left){rotateR(parent);rotateL(grandfather);cur->_col = BLACK;parent->_col = BLACK;break;}}}}//左单旋void rotateL(Node* parent){Node* pparent = parent->_parent;     //记录所旋转根节点的父亲Node* pNodeR = parent->_right;Node* pNodeRL = pNodeR->_left;if (pNodeRL)                         //如果该旋转节点的右节点的左孩子存在parent->_right = pNodeRL;pNodeR->_left = parent;//新的父节点的链接if (parent == _root){_root = pNodeR;pparent = nullptr;}else{if (pparent->_left == parent){pparent->_left = pNodeR;}else{pparent->_right = pNodeR;}}}//右单旋void rotateR(Node* parent){Node* pparent = parent->_parent;Node* pNodeL = parent->_left;Node* pNodeLR = pNodeL->_right;if (pNodeLR)parent->_left = pNodeLR;pNodeL->_right = parent;if (parent == _root){_root = pNodeL;pparent = nullptr;}else{if (pparent->_left == parent){pparent->_left = pNodeL;}else{pparent->_right = pNodeL;}}}

  5.红黑树与AVL树的比较

  红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( l o g 2 N log_2 N log2​N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。