1. 红黑树的概念
红黑树也属于二叉树搜索树的一种，但是不同于AVL树使用平衡节点来控制平衡的方法，红黑树采用了颜色的概念，即一个节点不是红色就是白色，并通过一系列规则进行约束，使其趋于平衡。
1.1 红黑树的规则
1.每个节点不是黑色就是白色
2.根节点是黑色的
3.如果一个节点是红色的，其两个孩子节点都必须是黑色节点。（这也就保证了一条路径上不会有连续的红色节点）
4.对于任意一个节点，从该节点开始的到NULL节点的每一条路径上的黑色节点数量相同。
注：《算法导论》等书籍上补充了⼀条每个叶子结点都是黑色的规则。此处的叶子节点指的是空节点，也就是NULL节点。这条规则是是为了方便准确的标识出所有路径，我们了解即可。
以下为红黑树实例
1.2 红黑树如何确保最长路径不超过最短路径的两倍？
首先，由规则4可知，从根节点出发的每条路径上黑色节点的数目相同，而红黑树只有红和黑两种颜色，极端情况下最短路径为全是黑色节点的路径，我们设其有bh(black height)个节点。
而由规则三可知，红色节点的孩子必为黑色节点，使用最长路径上的情况也只能是一黑一红交替，由于规则4的束缚，因此最长路径上只能有bh给黑色节点，又由于其是一黑一红交替，因此红黑节点数量一致，使用其最长路径的节点为 2bh。
最长节点的总长范围x 在 bh <= x <= 2bh。
1.3 红黑树的效率
假设N是红⿊树树中结点数量，h最短路径的⻓度，那么由1.2可得：
由此推出红⿊树增删查改最坏也就是⾛最⻓路径 2*logN ，那么时间复杂度还是O（logN）
2. 红黑树的实现
2.1 红黑树的结构
红黑树的节点结构
和AVL树类似，唯一区别是其需要一个Color类型来定义其颜色，因此我们使用联合体来定义出我们的Color
enum Color{RED,BLACK};template<class K,class V>struct RBTreeNode{pair<K, V> _kv;RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;Color _color;RBTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}};template<class K, class V>class RBTree{ typedef RBTreeNode<K, V> Node;public:private: Node* _root = nullptr;};这里选择我们不再初始化列表初始化节点的颜色，而是在后续插入操作时对节点颜色进行赋值。
2.2 红黑树的插入
2.2.1 大致过程
1. 按照搜索树的规则遍历找到插入的位置，插入之后只需要判断是否符合红黑树的规则4。
2.若是空树插入，那么根据性质2，插入节点应初始化为黑色。若是非空树插入，那么插入节点因初始化为红色，因为根据规则4，每条路径黑色节点数目一致，因此若插入黑色节点会导致一条路径上的黑色节点变多，破坏了性质4.
3.非空树插入后，由于新增节点必为红色，若其父亲节点为黑色，那么仍旧符合红黑树的规则，因此插入结束。
4.非空树插入后，由于新增节点必为红色，若其父亲节点为红色，那么破坏了规则4，因此我需要进行一系列操作使其恢复红黑树的规则。
那么在此条件下已知其插入节点及其父亲节点为红色，而在节点插入前的树应该是完整的红黑树，因此插入节点的父亲的父亲为黑色，所以变数便是舅舅节点。
5.不管是哪种操作，只要出现连续的红色节点（插入节点及其父亲节点为黑色），那么我们的总体思想就是将父亲节点变为黑色，因为只有这样才能保证其遵从红黑树的规则，在此基础上，由于我们将一个红色节点变为了黑色，破坏了规则4，那么接下来我们的思想，便是通过一系列的操作，使得每条路径上的黑色节点数量回复一致。
下图中假设我们把插入结点标识为c(cur)，c的⽗亲标识为p(parent)，p的⽗亲标识为 g(grandfather)，p的兄弟标识为u（uncle）。
2.2.2 情况1:变色
若c为红，p为红，u存在且为红，那么只需进行变色操作即可。
将g变为黑色，p和u变为红色，这样保证了从g位置出发的所有路径黑色节点数量不变，维护了红黑树的性质。
当然u节点不一定是g的右子树，也可能是左子树，因此需要分类讨论，不过进行的操作大致类似，因此我们只讨论u为g右子树的情况（当然在代码中两种情况都不会漏写滴）。
还有一点需要注意的是，既然我们进行了变色操作，导致了g变成了红色，那若g的父亲节点为黑色还好，要是g的父亲节点为红色，显然还是违背了红黑树的性质，因此我们的变色操作因是一个循环，在更新完当前节点后，将p赋值给c，从而进行向上更新。
2.2.3 单旋+变色
若c为红，p为红，g为黑，u不存在或存在且为黑，则需要进行旋转了。
若c为p的左节点，p是g的左节点，则进行的是单旋+变色.
根据插入思想，p是一定要变黑色的，那么p变黑之后路径上多出了一给黑色节点，怎么办呢？，我们将g和u(若u存在的话)变为红色，在对g节点进行右旋，这样p就成了新的父亲节点，并且每条路径上的黑色节点数量也一致。
2.2.4 双旋+变色
若c为红，p为红，g为黑，u不存在或存在且为黑，则需要进行旋转，并且c为p的右节点，但p是g的左节点，则进行的是双旋+变色。
将p节点变黑，g，u节点变红，对p节点进行左单旋，再对g节点进行右单旋
2.2.5 代码实现
bool Insert(const pair<K,V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_color = BLACK;return true;}Node* parent = _root;Node* cur = _root;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);cur->_parent = parent;cur->_color = RED;if (kv.second < parent->_kv.second){parent->_left = cur;}else{parent->_right = cur;}//父亲节点为红，出现了连续的红色节点，需要进行处理//循环处理，直到头节点或父节点为黑while (parent && parent->_color == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){// g// p uNode* uncle = grandfather->_right;if (uncle && uncle->_color == RED)//舅舅存在且为红{parent->_color = uncle->_color = BLACK;grandfather->_color = RED;//继续向上更新cur = grandfather;parent = grandfather->_parent;}else//舅舅不存在或舅舅为黑{// g// p u//c//单旋+变色if (parent->_left == cur){RotateR(grandfather);parent->_color = BLACK;grandfather->_color = RED;}// g// p u// c//双旋+变色else{RotateL(parent);RotateR(grandfather);cur->_color = BLACK;grandfather->_color = RED;}}}else{// g// u pNode* uncle = grandfather->_left;if (uncle && uncle->_color == RED)//舅舅存在且为红{parent->_color = uncle->_color = BLACK;grandfather->_color = RED;//继续向上更新cur = grandfather;parent = grandfather->_parent;}else//舅舅不存在或舅舅为黑{// g// u p// c//单旋+变色if (parent->_right == cur){RotateL(grandfather);parent->_color = BLACK;grandfather->_color = RED;}// g// u p// c//双旋+变色else{RotateR(parent);RotateL(grandfather);cur->_color = BLACK;grandfather->_color = RED;}}}}//保证了根节点一定为黑_root->_color = BLACK;return true;}注意，最后为了防止接连的变色污染根节点，我们只需在最后将根节点再赋值一遍黑色，这是代价最小也最方便的办法。
2.3 红黑树的查找
按⼆叉搜索树逻辑实现即可，此处不再过多赘述
Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}2.4 红黑树的检查
对于红黑树检查，我们需要检查其是否符合红黑树的4个规则
1. 规则1我们的联合体就定义了两种颜色，不会出错。
2. 规则2我们的根节点在插入操作末尾强制赋值了黑色，也没有问题。
3. 规则3我们采用前序遍历的方法不好检查，因为每个节点有一个或者两个孩子，相反，我们可以检查其父亲节点，因为每个孩子对应的只有一个父亲。
4.规则4我们可以先遍历最左路径，记录哎黑色节点数量，再定义一个局部遍历，通过前序遍历判断是否为黑色节点，是则++，通过比较其左侧路径和右侧路径的值是否相同判断。
bool Check(){if (_root == nullptr)return true;if (_root->_color == RED)return false;int refNum = 0;Node* cur = _root;while (cur){if (cur->_color == BLACK){refNum++;}cur = cur->_left;}return _Check(_root, 0, refNum);} bool _Check(Node* root, int blackNum, int refNum){if (root == nullptr){//一条路径走完了if (refNum != blackNum){cout << "存在黑色结点的数量不相等的路径" << endl;return false;}return true;}//检查孩子不方便，因为孩子有两个，所以反过来检查父亲if (root->_color == RED && root->_parent->_color == RED){cout << root->_kv.first << "存在连续的红色结点" << endl;return false;}if (root->_color == BLACK){blackNum++;}return _Check(root->_left, blackNum, refNum)&& _Check(root->_right, blackNum, refNum);}3.源码
3.1 RBTree.h
#pragma once#include<iostream>#include<vector>using namespace std;enum Color{RED,BLACK};template<class K,class V>struct RBTreeNode{pair<K, V> _kv;RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;Color _color;RBTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}};template<class K,class V>class RBTree{using Node = RBTreeNode<K,V>;public:void RotateR(Node* parent){Node* SubLNode = parent->_left;Node* SubLRNode = SubLNode->_right;parent->_left = SubLRNode;SubLNode->_right = parent;//定义PPNode保存parent的父亲节点，避免其被后续操作覆盖导致avl断开Node* PPNode = parent->_parent;parent->_parent = SubLNode;//防止parent为头节点，导致该操作造成空指针的解引用if (SubLRNode)SubLRNode->_parent = parent;if (PPNode == nullptr){_root = SubLNode;SubLNode->_parent = nullptr;}else{if (PPNode->_left == parent){PPNode->_left = SubLNode;}else{PPNode->_right = SubLNode;}SubLNode->_parent = PPNode;}}void RotateL(Node* parent){Node* SubRNode = parent->_right;Node* SubRLNode = SubRNode->_left;Node* PPNode = parent->_parent;SubRNode->_left = parent;parent->_parent = SubRNode;parent->_right = SubRLNode;if (SubRLNode)SubRLNode->_parent = parent;if (PPNode == nullptr){_root = SubRNode;SubRNode->_parent = nullptr;}else{if (PPNode->_left == parent)PPNode->_left = SubRNode;elsePPNode->_right = SubRNode;SubRNode->_parent = PPNode;}}bool Insert(const pair<K,V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_color = BLACK;return true;}Node* parent = _root;Node* cur = _root;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);cur->_parent = parent;cur->_color = RED;if (kv.second < parent->_kv.second){parent->_left = cur;}else{parent->_right = cur;}//父亲节点为红，出现了连续的红色节点，需要进行处理//循环处理，直到头节点或父节点为黑while (parent && parent->_color == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){// g// p uNode* uncle = grandfather->_right;if (uncle && uncle->_color == RED)//舅舅存在且为红{parent->_color = uncle->_color = BLACK;grandfather->_color = RED;//继续向上更新cur = grandfather;parent = grandfather->_parent;}else//舅舅不存在或舅舅为黑{// g// p u//c//单旋+变色if (parent->_left == cur){RotateR(grandfather);parent->_color = BLACK;grandfather->_color = RED;}// g// p u// c//双旋+变色else{RotateL(parent);RotateR(grandfather);cur->_color = BLACK;grandfather->_color = RED;}}}else{// g// u pNode* uncle = grandfather->_left;if (uncle && uncle->_color == RED)//舅舅存在且为红{parent->_color = uncle->_color = BLACK;grandfather->_color = RED;//继续向上更新cur = grandfather;parent = grandfather->_parent;}else//舅舅不存在或舅舅为黑{// g// u p// c//单旋+变色if (parent->_right == cur){RotateL(grandfather);parent->_color = BLACK;grandfather->_color = RED;}// g// u p// c//双旋+变色else{RotateR(parent);RotateL(grandfather);cur->_color = BLACK;grandfather->_color = RED;}}}}//保证了根节点一定为黑_root->_color = BLACK;return true;}void Print(){_Print(_root);}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}bool Check(){if (_root == nullptr)return true;if (_root->_color == RED)return false;int refNum = 0;Node* cur = _root;while (cur){if (cur->_color == BLACK){refNum++;}cur = cur->_left;}return _Check(_root, 0, refNum);}private:void _Print(Node* root){if (root == nullptr){return;}_Print(root->_left);cout << root->_kv.first << " " << root->_kv.second << endl;_Print(root->_right);}bool _Check(Node* root, int blackNum, int refNum){if (root == nullptr){//一条路径走完了if (refNum != blackNum){cout << "存在黑色结点的数量不相等的路径" << endl;return false;}return true;}//检查孩子不方便，因为孩子有两个，所以反过来检查父亲if (root->_color == RED && root->_parent->_color == RED){cout << root->_kv.first << "存在连续的红色结点" << endl;return false;}if (root->_color == BLACK){blackNum++;}return _Check(root->_left, blackNum, refNum)&& _Check(root->_right, blackNum, refNum);}Node* _root = nullptr;};3.2 RBTree.c
#define _CRT_SECURE_NO_WARNINGS 1#include"RBTee.h"void TestRBTree1(){RBTree<int, int> t;// 常规的测试⽤例 //int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的带有双旋场景的测试⽤例 int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){t.Insert({ e, e });}t.Print();cout << t.Check() << endl;}void TestRBTree2(){const int N = 100000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand() + i);}size_t begin2 = clock();RBTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));}size_t end2 = clock();cout << "Insert:" << end2 - begin2 << endl;cout << t.Check() << endl;}int main(){TestRBTree2();return 0;}