✅<1>主页：我的代码爱吃辣

📃<2>知识讲解：数据结构——红黑树

☂️<3>开发环境：Visual Studio 2022

💬<4>前言：红黑树也是一颗二叉搜索树，其作为map，set的底层容器，具有非常好的搜索性能，仅仅通过控制颜色和位置就能达到一种，近似平衡的效果，大大减少了旋转的次数。

一.红黑树的概念

二. 红黑树的性质

三.红黑树节点及其整体的定义

编辑

一.红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或

Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路
径会比其他路径长出俩倍，因而是接近平衡的。

编辑

二. 红黑树的性质

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

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

答案：因为性质3限制了，一条路径上，不可能出现连续的两个红色结点。又因为性质4，每条路径上黑色结点数目相同，那么最短路径就一定是全是黑色结点的路径，最长路径一定是红黑交错的路径，因为根节点一定是黑色，那么最长路径上红黑结点树一定是相等的，所以最长路径最多是最短路径的两倍。

三.红黑树节点及其整体的定义

//枚举
enum Color
{
  RED,//红色
  BLACK//黑色
};
template<class K,class V>
struct _RBTreeNode
{
  _RBTreeNode(pair<K,V> kv)
    :_kv(kv),
    _col(RED),//默认红色
    _left(nullptr),
    _right(nullptr),
    _parent(nullptr)
  {
  }
  pair<K, V> _kv;              //存储数值
  Color _col;                  //颜色
  _RBTreeNode<K, V>* _left;    //左孩子
  _RBTreeNode<K, V>* _right;   //右孩子
  _RBTreeNode<K, V>* _parent;  //父亲
};

#pragma once
#include<iostream>
using namespace std;
template<class K,class V>
class RBTRee
{
  typedef _RBTreeNode<K, V> Node;//结点
public:
  Node* find(const K key)
  {
    //....
  }
  bool insert(pair<K, V> kv)
  {
    //....
  }
  void Inorder()
  {
    //...
  }
  ~RBTRee()
  {
    //...
  }
private:
  Node* _root = nullptr;//根节点
};

思考：在节点的定义中，为什么要将节点的默认颜色给成红色的？

答案：新创建的结点，妖色要么红色，要么黑色，除了颜色区别之外，就是在插入时对整个树的影响不同，如果插入的是黑色，会影响整颗树，所有路径上的黑色结点说就会不同，必然违反性质4。如果插入的是红色结点，仅仅是局部的影响，可能会影响性质3，一定不会影响性质4。

编辑

四.红黑树的插入操作

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

1. 按照二叉搜索的树规则插入新节点。

bool insert(pair<K, V> kv)
  {
    if (_root == nullptr)
    {
      _root = new Node(kv);
      _root->_col = BLACK;
      return true;
    }
    Node* cur = _root;
    Node* parent = nullptr;
    while (cur)
    {
      if (kv.first < cur->_kv.first)
      {
        parent = cur;
        cur = cur->_left;
      }
      else if (kv.first > cur->_kv.first)
      {
        parent = cur;
        cur = cur->_right;
      }
      else
      {
        return false;
      }
    }
        //找到了合适的位置
    cur = new Node(kv);
    if (kv.first < parent->_kv.first)
    {
      parent->_left = cur;
    }
    else
    {
      parent->_right = cur;
    }
    cur->_parent = parent;
        //....  
}

因为性质2，所以我们每一次插入数据都想根节点变成黑色。

2.检测新节点插入后，红黑树的性质是否造到破坏，若满足直接退出，否则对红黑树进行旋转着色处理。

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何
性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连
在一起的红色节点，此时需要对红黑树分情况来讨论：

约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点。

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

编辑

解决方式：将 p , u 改为黑，g 改为红，然后把 g 当成 cur，继续向上调整。

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑

编辑

p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，
p、g变色--p变黑，g变红

情况三：cur为红，p为红，g为黑，u不存在/u存在且为黑

编辑

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；

编辑

p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，
p、g变色--p变黑，g变红

这里的cur的也有可能是新增的结点，如果是cur本身就是新增节点那么u结点就是不存在的，否则违反规则 4，也有可能是因为cur下面的结点变黑导致 cur 变红色。

编辑

编辑代码：

while (parent && parent->_col == RED)
  {
    Node* grandfather = parent->_parent;
    //           g(B)                     g(R)
    //     p(R)       u(R)  -->     p(B)       u(B)
    //c(R)                     c(R)
    if (grandfather->_left == parent)
    {
      Node* uncle = grandfather->_right;
      if (uncle && uncle->_col == RED)
      {
        parent->_col = BLACK;
        uncle->_col = BLACK;
        grandfather->_col = RED;
        //继续向上调整
        cur = grandfather;
        parent = cur->_parent;
      }
      else //u不存在/u存在且为黑，旋转+变色
      {
        //           g(B)                   p(R)
        //     p(R)       u(B)   -->  u(B)        g(B)
        //c(R)                         u(B)
        if (cur == parent->_left)
        {
          //右单旋
          RotateR(grandfather);
          parent->_col = BLACK;
          //cur->_col = RED;
          grandfather->_col = RED;
        }
        else
        {
          //            g(B)                   P(B)   
          //     p(R)         u(B)  --> c(R)          g(R)
          //         c(R)                                     u(B)
          // 左右双旋
          RotateL(parent);
          RotateR(grandfather);
          cur->_col = BLACK;
          grandfather->_col = RED;
        }
        break;
      }
    }
    else //grandfather->_right == parent,与上述情况相反
    {
      Node* uncle = grandfather->_left;
      if (uncle && uncle->_col == RED)
      {
        parent->_col = BLACK;
        uncle->_col = BLACK;
        grandfather->_col = RED;
        cur = grandfather;
        parent = cur->_parent;
      }
      else //u不存在/u存在且为黑，旋转+变色
      {
        if (cur == parent->_right)
        {
          //左单旋
          RotateL(grandfather);
          parent->_col = BLACK;
          grandfather->_col = RED;
        }
        else
        {
          // 右左双旋
          RotateR(parent);
          RotateL(grandfather);
          cur->_col = BLACK;
          grandfather->_col = RED;
        }
        break;
      }
    }
  }

旋转：

void RotateL(Node* parent)
  {
    Node* curR = parent->_right;
    Node* curRL = curR->_left;
    //调整结点，并且修改其父亲结点指针
    parent->_right = curRL;
    if (curRL)//可能为空
    {
      curRL->_parent = parent;
    }
    //在修改子树根节点之前，保存子树根节点的父亲
    Node* pparent = parent->_parent;
    //修改子树根节点
    curR->_left = parent;
    parent->_parent = curR;
    //子树根节点有可能是整棵树的根节点
    if (pparent == nullptr)
    {
      _root = curR;
      _root->_parent = nullptr;
    }
    else//子树根节点不是整棵树的根节点
    {
      //还要看子树是它父亲的左孩子还是右孩子
      if (pparent->_left == parent)
      {
        pparent->_left = curR;
      }
      else
      {
        pparent->_right = curR;
      }
      curR->_parent = pparent;
    }
  }
  void RotateR(Node* parent)
  {
    Node* curL = parent->_left;
    Node* curLR = curL->_right;
    parent->_left = curLR;
    if (curLR)
    {
      curLR->_parent = parent;
    }
    Node* pparent = parent->_parent;
    curL->_right = parent;
    parent->_parent = curL;
    if (parent == _root)
    {
      _root = curL;
      _root->_parent = nullptr;
    }
    else
    {
      if (pparent->_left == parent)
      {
        pparent->_left = curL;
      }
      else
      {
        pparent->_right = curL;
      }
      curL->_parent = pparent;
    }
  }

红黑树顺序插入：

编辑

红黑树随机插入：

编辑

五.红黑树 find

根据二叉搜索树特性去查找：

Node* find(const K key)
  {
    Node* cur = _root;
    while (cur)
    {
      if (key < cur->_kv.first)
      {
        cur = cur->_left;
      }
      else if (key > cur->_kv.first)
      {
        cur = cur->_right;
      }
      else
      {
        return cur;
      }
    }
    return nullptr;
  }

六.析构函数

后续遍历析构树：

~RBTRee()
  {
    _Destrory(_root);
    _root = nullptr;
  }
  void _Destrory(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    _Destrory(root->_left);
    _Destrory(root->_right);
    delete root;
  }

七.红黑树的验证

红黑树的检测分为两步：

检测其是否满足二叉搜索树(中序遍历是否为有序序列)
检测其是否满足红黑树的性质

其中是否满足搜索树我们只要对其中序遍历是否有序即可。

完整代码：

#pragma once
#include<iostream>
using namespace std;
enum Color
{
  RED,
  BLACK
};
template<class K,class V>
struct _RBTreeNode
{
  _RBTreeNode(pair<K,V> kv)
    :_kv(kv),
    _col(RED),
    _left(nullptr),
    _right(nullptr),
    _parent(nullptr)
  {
  }
  pair<K, V> _kv;
  Color _col;
  _RBTreeNode<K, V>* _left;
  _RBTreeNode<K, V>* _right;
  _RBTreeNode<K, V>* _parent;
};
template<class K,class V>
class RBTRee
{
  typedef _RBTreeNode<K, V> Node;
public:
  Node* find(const K key)
  {
    Node* cur = _root;
    while (cur)
    {
      if (key < cur->_kv.first)
      {
        cur = cur->_left;
      }
      else if (key > cur->_kv.first)
      {
        cur = cur->_right;
      }
      else
      {
        return cur;
      }
    }
    return nullptr;
  }
  bool insert(pair<K, V> kv)
  {
    if (_root == nullptr)
    {
      _root = new Node(kv);
      _root->_col = BLACK;
      return true;
    }
    Node* cur = _root;
    Node* parent = nullptr;
    while (cur)
    {
      if (kv.first < cur->_kv.first)
      {
        parent = cur;
        cur = cur->_left;
      }
      else if (kv.first > cur->_kv.first)
      {
        parent = cur;
        cur = cur->_right;
      }
      else
      {
        return false;
      }
    }
    cur = new Node(kv);
    //找到了合适的位置
    if (kv.first < parent->_kv.first)
    {
      parent->_left = cur;
    }
    else
    {
      parent->_right = cur;
    }
    cur->_parent = parent;
    while ( parent && parent->_col == RED)
    {
      Node* grandfather = parent->_parent;
      //           g(B)                     g(R)
      //     p(R)       u(R)  -->     p(B)       u(B)
      //c(R)                     c(R)
      if ( grandfather->_left == parent)
      {
        Node* uncle = grandfather->_right;
        if (uncle && uncle->_col == RED)
        {
          parent->_col = BLACK;
          uncle->_col = BLACK;
          grandfather->_col = RED;
          //继续向上调整
          cur = grandfather;
          parent = cur->_parent;
        }
        else //u不存在/u存在且为黑，旋转+变色
        {
          //           g(B)                   p(R)
          //     p(R)       u(B)   -->  u(B)        g(B)
          //c(R)                         u(B)
          if (cur == parent->_left)
          {
            //右单旋
            RotateR(grandfather);
            parent->_col = BLACK;
            //cur->_col = RED;
            grandfather->_col = RED;
          }
          else
          {
            //            g(B)                   P(B)   
            //     p(R)         u(B)  --> c(R)          g(R)
            //         c(R)                                     u(B)
            // 左右双旋
            RotateL(parent);
            RotateR(grandfather);
            cur->_col = BLACK;
            grandfather->_col = RED;
          }
          break;
        }
      }
      else //grandfather->_right == parent,与上述情况相反
      {
        Node* uncle = grandfather->_left;
        if (uncle && uncle->_col == RED)
        {
          parent->_col = BLACK;
          uncle->_col = BLACK;
          grandfather->_col = RED;
          cur = grandfather;
          parent = cur->_parent;
        }
        else //u不存在/u存在且为黑，旋转+变色
        {
          if (cur == parent->_right)
          {
            //左单旋
            RotateL(grandfather);
            parent->_col = BLACK;
            grandfather->_col = RED;
          }
          else
          {
            // 右左双旋
            RotateR(parent);
            RotateL(grandfather);
            cur->_col = BLACK;
            grandfather->_col = RED;
          }
          break;
        }
      }
    }
    _root->_col = BLACK;
    return true;
  }
  void Inorder(vector<K> & v)
  {
    _inorder(_root,v);
    cout << endl;
  }
  ~RBTRee()
  {
    _Destrory(_root);
    _root = nullptr;
  }
private:
  void _Destrory(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    _Destrory(root->_left);
    _Destrory(root->_right);
    delete root;
  }
    void _inorder(Node* root, vector<K>& v)
  {
    if (root == nullptr)
    {
      return;
    }
    _inorder(root->_left,v);
    v.push_back(root->_kv.first);
    _inorder(root->_right,v);
  }
  void RotateL(Node* parent)
  {
    Node* curR = parent->_right;
    Node* curRL = curR->_left;
    //调整结点，并且修改其父亲结点指针
    parent->_right = curRL;
    if (curRL)//可能为空
    {
      curRL->_parent = parent;
    }
    //在修改子树根节点之前，保存子树根节点的父亲
    Node* pparent = parent->_parent;
    //修改子树根节点
    curR->_left = parent;
    parent->_parent = curR;
    //子树根节点有可能是整棵树的根节点
    if (pparent == nullptr)
    {
      _root = curR;
      _root->_parent = nullptr;
    }
    else//子树根节点不是整棵树的根节点
    {
      //还要看子树是它父亲的左孩子还是右孩子
      if (pparent->_left == parent)
      {
        pparent->_left = curR;
      }
      else
      {
        pparent->_right = curR;
      }
      curR->_parent = pparent;
    }
  }
  void RotateR(Node* parent)
  {
    Node* curL = parent->_left;
    Node* curLR = curL->_right;
    parent->_left = curLR;
    if (curLR)
    {
      curLR->_parent = parent;
    }
    Node* pparent = parent->_parent;
    curL->_right = parent;
    parent->_parent = curL;
    if (parent == _root)
    {
      _root = curL;
      _root->_parent = nullptr;
    }
    else
    {
      if (pparent->_left == parent)
      {
        pparent->_left = curL;
      }
      else
      {
        pparent->_right = curL;
      }
      curL->_parent = pparent;
    }
  }
  Node* _root = nullptr;
};

//传参时benchmark是-1，代表还没有基准值，当走完第一条路径时，
  //将第一条路径的黑色节点数作为基准值，后续路径走到null时，就与基准值比较。
  //blacknum记录路径上的黑色节点数
  bool _isRBTree(Node* root, int blacknum, int benchmark)
  {
    if (root == nullptr)
    {
      if (benchmark == -1)
      {
        benchmark = blacknum;
      }
      else
      {
        if (blacknum != benchmark)
        {
          cout << "black Node !=" << endl;
          return false;
        }
      }
      return true;
    }
    if (root->_col == BLACK)
    {
      blacknum++;
    }
        //判断时候出现两个连续的红色结点
    if (root->_col == RED && root->_parent && root->_parent->_col == RED)
    {
      cout << "red connect " << endl;
      return false;
    }
    return _isRBTree(root->_left, blacknum, benchmark) && _isRBTree(root->_right, blacknum, benchmark);
  }

main.cpp

#include<vector>
#include<cassert>
#include"RB_Tree.hpp"
int main()
{
  RBTRee<int, int> rb;
  int i = 100000;
  while(i--)
  {
    int num = rand() + i;
    rb.insert(make_pair(num,num));
  }
  vector<int> v;
  rb.Inorder(v);
  for (int i = 0; i < v.size() - 1; i++)
  {
    if (v[i] > v[i + 1])
    {
      assert(0);
    }
  }
  cout << rb.isRBTree() << endl;
  return 0;
}