一、红黑树的概念
红黑树是一颗二叉搜索树，它的节点增加一个存储位置来表示节点的颜色，可以是红色或黑色。
需达成的约束：确保没有一条路径会比其他路径长出2倍，因此接近平衡。
二、红黑树的规则
1.节点颜色不是红色就是黑色。
2.根节点是黑色的。
3.当前节点是红色的，两个孩子必须是黑色的，任何一条路径不会有连续的红色节点。
4.对于任⼀结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的黑色结点。
因此，从根开始每条路径（走到空）黑色结点数量相等。
约束解析：
极端场景：
假设每条路径有x个黑色结点：
最短路径：全都是黑色结点，路径长度为x
最长情况：一黑一红（因为规则2限制没有连续红色节点），路径长度为2x
达成了约束，没有一条路径会比其他路径长出2倍。
红黑树的效率：
假设N是红黑树中结点数量，h最短路径的长度，那么 2^h-1<=N<2^(2h)-1，h约等于logN，最坏情况要走2*logN，数量级还是logN，因此红黑树增删查改的效率是O(logN)。
三、红黑树的插入
红黑树的情况比较难于直接分类讨论，但只要符合规则就能保证一棵树是红黑树，因此分类时根据规则来分情况讨论。
红黑树插入的情况分析：
1）对规则1，红黑树颜色是枚举值，非红即黑，符合
2）对规则2，只需对根节点特殊处理，将根节点颜色置成黑色，易解决
3）对规则3和规则4：
规则4首先要保证任一节点走到空的黑色结点数量一致，就要使插入的节点必须是红色节点，如果是黑色结点，会使从根走到空的其他路径黑色结点数量不一样。
规则3要验证每一个红色节点的孩子都是黑色结点不好判断，自身对子树判断有四种情况（左右孩子都有，只有左孩子，只有右孩子，左右孩子都没有），因而传化成：判断是否有连续的红色节点（即判断新增节点的父节点是否为红色），只要没有了连续的红色节点，插入就完成了，因为保证了四条规则。
因而现在只需要判断是否有连续的红色节点及其处理就行了。
对于判断是否连续的红色节点，可以拆分出以下几种情况
1）新增节点的父节点是黑色，不需要调整，没有了连续的红色节点。
2）新增节点的父节点是红色，此时需要调整。
注：新增节点的父节点为空，新增节点为新的根，在insert最开始处理，不计入调整。
新增节点的父节点是红色的情况分析：
当前可确定的情况如上图所示，即cur为红色，parent为红色，grandparent为黑色。
原因：cur为新增节点，必为红色（为了满足规则4）；现在条件是parent为红色；插入前是红黑树，grandparent必为黑色（为了满足规则3）。
此时，不确定的情况为uncle节点，有三种子情况：
1）uncle存在且为红色
2）uncle不存在
3）uncle存在且为黑色
对uncle的三种情况进行分类讨论：
情况1，uncle存在且为红色
解决方法：变色
分析：首先parent一定要变为黑色，因为要同时满足规则3和规则4。但这样做以grandparent为根，经过parent的走到空的路径的黑色节点数量会比grandparent的右子树路径多一个。
因此要将grandparent变为红色节点，同时uncle变为黑色结点，这样grandparent左右子树黑色节点就一样多了，parent左右子树的黑色节点也一样多。
形象描述：grandparent的黑色下放给parent和uncle，grandparent变为红色。
注意有特殊情况：
若grandparent为根节点，处理完后cur变为根节点，parent为空指针，由于最外层循环条件为parent->_col为红色，要处理空指针解引用的问题，以及cur此时为根节点，根节点为红色的问题。
解决方法：循环条件改为while(parent && parent->_col==RED)；出循环后直接将根节点的颜色置为黑色，这种做法成本最低。
总结处理方法：将parent和uncle变为黑色，grandparent变为红色。grandparent赋值给cur，cur的parent赋值给parent，继续向上调整。
情况2：uncle不存在或者uncle存在且为黑色，且cur与parent的关系与grandparent与parent的关系一致（即同左同右，单纯的一边高）
解决方法：单旋加变色
cur在parent左边，uncle存在且为黑色情况
分析：uncle不能分担grandparent的黑色了，因此右单旋，grandparent变红，parent变黑，达到走uncle路径的黑色节点数量不变，同时走cur路径的黑色节点数量也不变。
cur为parent的左边，uncle不存在情况：
分析：若uncle为空，那么cur的左右孩子都为空，cur就是新增节点。parent的右孩子也必是空。
原因：cur的左右孩子若不是空，不能是黑色节点否则就违背规则4；不能是红色节点否则就违背规则3；但既不能是红色节点又不能是黑色节点就违背了规则1，因此只能是空。parent同理。
可以发现，uncle存在且为黑和uncle为空的处理方式一模一样，因此可以把它们归为一种情况。
总结处理方法：对grandparent进行右单旋，parent变为黑色，grandparent变为红色，调整结束。
情况3：uncle不存在或者uncle存在且为黑色，且cur与parent的关系与grandparent与parent的关系不一致（即非同左同右，不是单纯的一边高）
解决方法：双旋加变色
parent在grandparent左边，但cur在parent右边
总结处理方法：对parent进行左单旋，转化成一边高，再对grandparent进行右单旋。cur变为黑，grandparent变为红。
插入代码实现：
bool insert(const pair<K,V>& data) { if (_root == nullptr) { _root = new Node(data); _root->_col = BLACK; return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { //比cur小，往左走 if (cur->_kv.first > data.first) { parent = cur; cur = parent->_left; } //比cur大，往右走 else if (cur->_kv.first < data.first) { parent = cur; cur = parent->_right; } else { return false; } } cur = new Node(data); //比parent小，链接在左边,否则链接在右边 if (data.first < parent->_kv.first) { parent->_left = cur; } else { parent->_right = cur; } cur->_parent = parent; //调整部分 //parent不为空 且 parent的颜色为红色就还要继续调整 while (parent && parent->_col==RED) { //grandparent一定非NULL， // 因为如果parent如果是根节点，parent就是黑色的 //parent是黑色的进不来循环 Node* grandparent = parent->_parent; if (parent == grandparent->_left) { // g g // p u 或 p u // c c Node* uncle = grandparent->_right; //无论cur在左还是右都不影响 //uncle存在且为红 if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandparent->_col = RED; //还要向上处理 cur = grandparent; parent = cur->_parent; } //uncle不存在 或者 uncle存在且为黑 else { // g // p u // c //cur为parent的左 if (cur == parent->_left) { rotateR(grandparent); parent->_col = BLACK; grandparent->_col = RED; //旧的parent现在的grandparent // 已经为黑色了，不需要向上处理 break; } //cur为parent的右，不是单纯一边高 //双旋加变色 else { // g // p u // c rotateL(parent); rotateR(grandparent); cur->_col = BLACK; grandparent->_col = RED; //旧的cur现在的grandparent //已经变为黑色了，不需要向上处理 break; } } } else { // g // u p // c Node* grandparent = parent->_parent; Node* uncle = grandparent->_left; //无论cur在左还是右，不影响 if (uncle && uncle->_col == RED) { grandparent->_col = RED; uncle->_col = parent->_col = BLACK; //此时grandparent为红色，需要向上更新 cur = grandparent; parent = cur->_parent; } // uncle存在且为黑 或者 uncle为空 else { // g // u p // c //单纯一边高，单旋加变色 if (cur == parent->_right) { rotateL(grandparent); parent->_col = BLACK; grandparent->_col = RED; //旧parent新grandparent //此时已经为黑，停止更新 break; } // g // u p // c //不是单纯一边高，双旋加变色 else { rotateR(parent); rotateL(grandparent); cur->_col = BLACK; grandparent->_col = RED; //旧cur新grandparent //此时已经为黑，停止更新 break; } } } } _root->_col = BLACK; return true; }
判断一颗树是否为红黑树
根据规则来走：
规则1，满足，枚举类型非红即黑。
规则2，将根特殊处理就行了
规则3，如果当前结点是红色，左右孩子只能是黑色，即不能有连续的红色节点。判断当前节点不好判断，四种情况，改为判断若当前节点是红色，那么父节点不能是红色。
规则4，前序遍历，从根走到空，每次走到空时和基准值（遍历一遍最左路径，记录黑色节点的数量）比较，若相等则是，反之则不是。
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 << "存在连续的红色结点" << endl; return false; } if (root->_col == BLACK) { blackNum++; } return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum); }