一、红黑树概念与性质
【概念】
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或
Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路
径会比其他路径长出俩倍，因而是接近平衡的。AVL树是严格平衡。
【红黑树的性质】
1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
二、红黑树节点定义
enum Colour
{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;Colour _col;RBTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) // 颜色默认给成红色{}
};思考：在节点的定义中，为什么要将节点的默认颜色给成红色的？
答：优先插入红色不一定能破坏红黑树的性质，如果破坏性质可以通过调整红黑树的颜色来进行修改，但是插入黑色直接破坏红黑树的性质。
三、红黑树的插入操作
1. 按照二叉搜索的树规则插入新节点(左子树<根<右子树）
2.检测新节点插入后，红黑树的性质是否造到破坏
因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何
性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连
在一起的红色节点，此时需要对红黑树分情况来讨论：
cur为当前节点，p(parent)为父节点，g(grandfather)为祖父节点，u(uncle)为叔叔节点.
template<class K, class V>
class 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->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);// 新增节点。颜色红色给红色cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//............// 维护新增节点private:Node* _root = nullptr;
}情况一: cur为红，p为红，g为黑，u存在且为红
如果g变为红色节点，若g是根节点，则将g调整为黑色，若不是根节点，则g变cur继续向上调整
情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑 (单旋)
1、如果u节点不存在，则cur一定是新插入节点，因为如果cur不是新插入节点，则cur和p一定有一个节点的颜色是黑色，就不满足性质4：每条路径黑色节点个数相同。
2、如果u节点存在，则其是黑色的，那么cur节点原来的颜色一定是黑色的因为性质4，现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色
p为g的左孩子，cur为p的左孩子，则进行右单旋；相反，p为g的右孩子，cur为p的右孩子，则进行左单旋。
情况二、无论u存不存在是不是黑色，p、g变色--p变黑，g变红
情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑(双旋)
p为g的左孩子，cur为p的右孩子，则针对p做左单旋转，针对g进行右单旋，cur变黑，g变红；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转 ，针对g为左单旋，cur变黑，g变红。
代码实现：
// 维护节点while (parent && parent->_col == RED){//1. parent 存在且为黑，则停止循环//2. parent 存在且为红，继续循环//3. parent 不存在，cur就为根了，出去后把根变成黑色Node* grandfather = parent->_parent;// 左子树// g// p uif (parent == grandfather->_left){Node* uncle = grandfather->_right;// u 存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}else{// u存在且为黑或不存在 -> 旋转+变色if (cur == parent->_left){// g// p u//c// 单旋RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g// p u// c// 双旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}//右子树// g// u pelse {Node* uncle = grandfather->_left;//情况一、u存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}//情况二、u不存在或且为黑else{// g// u p// cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}// g// u p// celse{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}//情况一，都把根变黑_root->_col = BLACK;return true;}四、红黑树的验证
1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
2. 检测其是否满足红黑树的性质
// 先找一个基准值bool IsBalance(){if (_root == nullptr){return true;}if (_root->_col == RED){return false;}int refNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refNum;}cur = cur->_left;}return Check(_root, 0, refNum);}bool Check(Node* root, int blackNum, const int refNum){if (root == nullptr){cout << blackNum << endl;if (refNum != blackNum){cout << "存在黑色节点的数量不相等的路径" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "存在连续的红色节点" << '\n';return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);}