红黑树的概念

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

红黑树的性质

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

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

最短路径为全黑，最长路径就是红黑节点交替（因为红色节点不能连续），每条路径的黑色节点相同，则最长路径、刚好是最短路径的两倍。

最优情况：全黑或每条路径都是一黑一红的满二叉树，高度logN
最差情况：每颗子树左子树全黑，右子树一黑一红。高度2*logN。

红黑树的插入操作（核心）

为什么新插入的节点必须给红色？
新节点给红色，可能会违反上面说的红黑树性质3；如果新节点给黑色，必定会违反性质4。

根据插入节点后会破坏红黑树的结构，将其分为三种情况

情况一：uncle存在且为红

cur、parent、grandfather都是确定颜色的，uncleu存在且为红

将p,u改为黑，g改为红，然后把g当成cur，继续向上调整

理解：cur为红那么就需要将parent变为黑；parent变黑需要控制每条路径上黑色节点的数量相同，那么就要把uncle变黑；如果grandfather不是根，需要反转为红，用以控制路径黑节点数量相同。继续向上调整即可

情况二：uncle不存在/存在且为黑（在同一侧）

第一种：uncle不存在，则cur为插入节点，单旋即可

第二种：uncle存在且为黑，是有第一种情况一变化而来的

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

情况三：uncle不存在/存在且为黑（在两侧）

第一种：uncle不存在，则cur为插入节点，左右双旋

第二种：uncle存在且为黑

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，
p为g的右孩子，cur为p的左孩子，则针对p做右单旋转，则转换成了情况2

总结

插入新节点时，父节点为红，看叔叔的颜色。

1. 叔叔存在且为红，变色，向上调整（可能变为三种情况中的任意一种）

2. 叔叔不存在或存在且为黑，同侧。单旋+变色

3. 叔叔不存在或存在且为黑，异侧，两次单旋+变色

红黑树的简单实现

#pragma once
#include<assert.h>
#include<time.h>
enum Color
{Red,Black,
};
template<class K, class V>
struct RBTreenode
{pair<K, V> _kv;RBTreenode<K, V>* _left;RBTreenode<K, V>* _right;RBTreenode<K, V>* _parent;Color _col;RBTreenode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr),_col(Red){}
};template<class K, class V>
struct RBTree
{typedef RBTreenode<K, V> Node;
public:bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = Black;return true;}//找插入位置Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first>kv.first){parent = cur;cur = cur->_left;}else if(cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else//存在与插入结点相同的结点key{return false;}}cur = new Node(kv);cur->_col = Red;if (parent->_kv.first<kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}//红黑树的调整while (parent&&parent->_col==Red){//祖父节点Node* grandfather = parent->_parent;if (parent==grandfather->_left){Node* uncle = grandfather->_right;//一：uncle存在且为红if (uncle && uncle->_col==Red){parent->_col = uncle->_col = Black;grandfather->_col = Red;//如果祖父节点同时是子节点，考虑双红，需要//继续向上调整cur = grandfather;//考虑parent是否为空parent = cur->_parent;}else{//情况二:cur为红，p红，g黑// uncle存在且为黑/不存在// 祖孙三代全在同一侧//左单选或右单旋if (cur==parent->_left){RotateR(grandfather);parent->_col = Black;grandfather->_col = Red;}else{//情况三：// c,p为红色，g为黑// u不存在/存在且为黑//需要进行双旋操作RotateL(parent);RotateR(grandfather);cur->_col = Black;grandfather->_col = Red;}break;}}else//parent==grandfather->_right{Node* uncle = grandfather->_left;if (uncle&&uncle->_col==Red){parent->_col = uncle->_col = Black;grandfather->_col = Red;cur = grandfather;parent = cur->_parent;}else{//   g                //      p//         cif (cur==parent->_right){RotateL(grandfather);parent->_col = Black;grandfather->_col = Red;}else{//   g                //		   p//    cRotateR(parent);RotateL(grandfather);cur->_col = Black;grandfather->_col = Red;}break;}}}_root->_col = Black;return true;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (ppNode == nullptr){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subLR->_parent = parent;}Node* ppNode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (ppNode == nullptr){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}void Inorder(){_Inorder(_root);}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_Inorder(root->_right);}//判断是否有连续红结点和路径上黑色节点数量是否一致bool Check(Node* root,int BlackNum,const int ref){//这里用传值（不用引用）BlackNum,//递归返回上一层的时候BlackNum不会被改变//每个节点都有一个BlackNumif (root==nullptr){if (BlackNum != ref){cout << "违反规则，本条路径结点与基准不一致" << endl;return false;}return true;}if (root->_col==Red && root->_parent->_col==Red){cout << "违反规则：出现连续红结点" << endl;return false;}if (root->_col==Black){++BlackNum;}return Check(root->_left, BlackNum, ref) &&Check(root->_right, BlackNum, ref);}bool IsRBTree(){if (_root==nullptr){return true;}if (_root->_col != Black){return false;}//所有路径黑色节点数相同，以最左侧路径黑色节点数为基准//递归查看是否匹配int ref = 0;Node* left = _root;while (left){if (left->_col==Black){++ref;}left = left->_left;}return Check(_root,0,ref);}
private:Node* _root = nullptr;
};