C++：红黑树

红黑树的概念

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

如下所示就是一颗红黑树：

红黑树的性质

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

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

根据红黑树的性质，当一颗子树中的节点全部为黑色节点时，路径最短；在另一颗包含红色节点的子树中，由于节点为一黑一红间隔，节点数量最多是全黑子树的两倍，路径最长。

红黑树节点的定义

//颜色
enum color
{RED,BLACK
};//红黑树节点的定义
template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;color _col;//构造函数RBTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};

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

新插入节点的颜色只会影响性质3或者性质4（新插入的节点不是根节点的时候），

如果新插入的节点是黑色的节点，那么一定会破坏性质4，破坏性质4要想让红黑树平衡最坏的情况需要将整颗树的节点都动一遍，很难维护。

如果新插入的节点是红色的节点，可能会破坏性质3（红色节点的孩子一定是黑色，黑色节点的孩子不一定是红色），即使破坏了性质3，最坏的情况也就不过只要更改三个节点的颜色。

红黑树的插入

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

按照二叉搜索的树规则插入新节点
检测新节点插入后，红黑树的性质是否造到破坏

（注意：由于红黑树的插入也会涉及旋转等问题，所以随着高度的增加红黑树树子树的情况就会变得非常复杂，所以采用和AVL树一样的处理方法，使用具象图来表示）

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

（cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点）

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

cur和p均为红，违反了性质三，此处能否将p直接改为黑？

切记不可，否则就会违反性质4，处理起来会很棘手。

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

如果p是红色，由于新插入的节点默认是红色的，就会出现连续的红色节点，违反性质三，处理完后保证了性质四不会变。

如果g是根节点，调整完成后，需要将g改为黑色（根节点一定为黑色）

如果g是子树，一定有双亲，且g的双亲如果是红色，需要继续向上调整，如下图：

经调整后是可能会出现上图情况，即本来g的p是红色的，所以需要继续往上调整，以上是当cur是新插入节点的情况，同理，我们调整的这部分也可能是下面调整上来导致，即a，b，c，d，e都不为0的情况，当在a或b新插入节点导致的连续红色节点，一路向上调整这，需要纵观全局，图上可能是一棵树的全部，或者是一棵树的顶部，也可能是一颗树的中部，甚至是一颗树的底部

无论是哪一部分，无论是在哪颗子树，只要按处理方式处理，往上更新即可。

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

u的情况有两种：

如果u节点不存在，则cur一定是新插入节点，因为如果cur不是新插入节点，则cur和p一定有一个节点的颜色是黑色，就不满足性质4
如果u节点存在，则其一定是黑色的，那么cur节点原来的颜色一定是黑色的，现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色

处理方式：

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

情况1——u不存在

当u不存在&&p是g的左&&cur是p的左，abcde子树都不应该存在（de肯定不存在，c若存在那么cur插入前就应该旋转过来了，cur不可能插在p的这个位置，cur若不是新插入节点p应该是黑色，那么违反红黑树性质4。），如下图：

单纯的左子树的左高，以g为旋转点进行右单旋，旋转完成后，p变黑色g变红色：

即平衡，就不用再做处理，不再往上更新

当u不存在&&p是g的右&&cur是p的右，与上面同理，如下图：

单纯的右子树的右高，以g为旋转点进行左单旋，旋转完成后，p变黑色g变红色：

即平衡，就不用再做处理，不再往上更新

情况2——u存在且为黑

为什么cur节点原来的颜色一定是黑色的，现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色？

分析如下：

cur为红色有两种情况：

一种情况是cur本来是红色，即cur为新插入的红色节点，但是新插入红色cur节点的情况不可能存在，因为如果是新插入红色cur节点无论如何都会违反红黑树的性质。

一种情况由子树往上更新来导致cur变成红色，即由情况一向上更新演变到cur为红，u为黑

由此分析发现只能是第二种情况。

以下更新情况都是由情况一向上更新演变到cur为红u为黑高度最少的情况即相差一层高度：

（如果再少一层，即少cur下面一层（cur是新插入的红色节点），则该树一定违反红黑树性质）

u存在&&u为黑&&p是g的左&&cur是p的左：

上图经过情况一演变到下图：

单纯的左子树的左高，以g为旋转点进行右单旋，旋转完成后，p变成黑色，g变成红色，如下图：

经过旋转+变色以后该红黑树就平衡了，不用往上更新

u存在&&u为黑&&p是g的右&&cur是p的右：

上图经过情况一演变到下图：

单纯的右子树的右高，以g为旋转点进行左单旋，旋转完成后，p变成黑色，g变成红色，如下图：

经过旋转+变色以后该红黑树就平衡了，不用往上更新

u存在&&u为黑&&p是g的左&&cur是p的左的模板：

abdemnxy等子树是包含相同数量黑色节点的红黑子树，从xymn几个位置中某个位置子树插入红色节点，引发cur从黑变成红，进而引发左子树左高导致的右单旋

u存在&&u为黑&&p是g的右&&cur是p的右的模板：

abdemnxy等子树是包含相同数量黑色节点的红黑子树，从xymn几个位置中某个位置子树插入红色节点，引发cur从黑变成红，进而引发右子树右高导致的左单旋

旋转+变色以后，这颗子树不违反红黑树规则，和插入前比较，黑色节点数量不变，不会影响上层，处理结束。

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

情况三和情况二其实是一样的，只不过引发的双旋，除了处理旋转，其他都按情况二方式处理

处理方式：

p为g的左孩子，cur为p的右孩子，针对p做左单旋转，再针对g做右单旋；
p为g的右孩子，cur为p的左孩子，针对p做右单旋转，再针对g做左单旋；
cur、g变色—>cur变黑，g变红

以下直接给出模板：

u存在&&u为黑&&p是g的左&&cur是p的右的模板：

abdemnxy等子树是包含相同数量黑色节点的红黑子树，从ab两个位置中某个位置子树插入红色节点，引发cur从黑变成红，进而引发左子树右高导致的左右单双旋

u存在&&u为黑&&p是g的右&&cur是p的左的模板：

abdemnxy等子树是包含相同数量黑色节点的红黑子树，从ab两个位置中某个位置子树插入红色节点，引发cur从黑变成红，进而引发右子树左高导致的右左单双旋

和情况二同理，旋转+变色以后，这颗子树不违反红黑树规则，和插入前比较，黑色节点数量不变，不会影响上层，处理结束

插入代码实现如下：

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){parent = cur;if (cur->_kv.first < kv.first)cur = cur->_right;else if (cur->_kv.first > kv.first)cur = cur->_left;elsereturn false;}//将节点插入cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < cur->_kv.first)parent->_right = cur;elseparent->_left = cur;cur->_parent = parent;//连续的红色while (parent && parent->_col == RED){Node* grandparent = parent->_parent;assert(grandparent);//parent是grandparent的左if (parent == grandparent->_left){Node* uncle = grandparent->_right;//unlce存在且为红if (uncle && uncle->_col == RED){//更新parent和uncle的颜色为黑色，grandparent为红色parent->_col = uncle->_col = BLACK;grandparent->_col = RED;//向上更新cur = grandparent;parent = cur->_parent;}//uncle不存在或者为黑else{//cur是parent的左，左高，右单旋，以grandparent为旋转点if (cur == parent->_left){RotateR(grandparent);grandparent->_col = RED;parent->_col = BLACK;}//cur是parent的右，左右双旋的情况else{RotateL(parent);RotateR(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;//旋转调整颜色后一定平衡，只是更改颜色未旋转不一定平衡}}//parent是grandparent的右else{Node* uncle = grandparent->_left;//uncle存在且为红if (uncle && uncle->_col == RED){//更新parent和uncle的颜色为黑色，grandparent为红色parent->_col = uncle->_col = BLACK;grandparent->_col = RED;//向上更新cur = grandparent;parent = cur->_parent;}//uncle不存在或者为黑else{//cur是parent的右，右高，左单旋if (cur == parent->_right){RotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}//cur是parent的左，右左双旋else{RotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;//旋转调整颜色后一定平衡，只是更改颜色未旋转不一定平衡}}}_root->_col = BLACK;//根节点必须为黑色//插入成功return true;}
private://右边高左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;//将根的右子树的左子树赋值给根的右子树parent->_right = subRL;//subRL为空不能访问if (subRL)subRL->_parent = parent;//将根节点变成根的右子树的左子树subR->_left = parent;//更新根的右子树的父节点subR->_parent = parent->_parent;//如果parent是根节点需要更新根节点if (parent == _root){_root = subR;subR->_parent = nullptr;}//如果parent上面还有祖先节点，需要更新祖先节点的左节点/右节点else{if (parent->_parent->_left == parent)parent->_parent->_left = subR;elseparent->_parent->_right = subR;}//更新根的父节点parent->_parent = subR;}//左边高右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;//根节点的左指针指向左子树的右子树parent->_left = subLR;//如果根节点的左子树的右子树不为空则更新_parentif (subLR)subLR->_parent = parent;//根节点的左子树的右指针指向parentsubL->_right = parent;//更新subL的_parentsubL->_parent = parent->_parent;//处理parent是根节点和不是根节点的情况//如果parent是根节点，则赋值给_rootif (parent == _root){_root = subL;subL->_parent = nullptr;}//否则链接上祖先节点else{//确定是祖先节点的左还是右，并链接上if (parent->_parent->_left == parent)parent->_parent->_left = subL;elseparent->_parent->_right = subL;}//更新parent的_parentparent->_parent = subL;}

红黑树的验证

红黑树的检测分为两步：

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

分别从层序遍历（查看每层节点），中序遍历（二叉搜索树是有序的），树的最低高度和最高高度（红黑树的性质），是否平衡（红黑树的性质）四个角度判断，都满足即是红黑树。

public://层序遍历vector<vector<int>> levelOrder() {vector<vector<int>> vv;if (_root == nullptr)return vv;queue<Node*> q;int levelSize = 1;q.push(_root);while (!q.empty()){// levelSize控制一层一层出vector<int> levelV;while (levelSize--){Node* front = q.front();q.pop();levelV.push_back(front->_kv.first);if (front->_left)q.push(front->_left);if (front->_right)q.push(front->_right);}vv.push_back(levelV);for (auto e : levelV){cout << e << " ";}cout << endl;// 上一层出完，下一层就都进队列levelSize = q.size();}return vv;}//中序遍历void InOrder(){_InOrder(_root);cout << endl;}//求高度差void Height(){cout << "最长路径:" << _maxHeight(_root) << endl;cout << "最短路径:" << _minHeight(_root) << endl;}//判断是否平衡bool IsBalanceTree(){// 检查红黑树几条规则Node* pRoot = _root;// 空树也是红黑树if (nullptr == pRoot)return true;// 检测根节点是否满足情况if (BLACK != pRoot->_col){cout << "违反红黑树性质二：根节点必须为黑色" << endl;return false;}// 获取任意一条路径中黑色节点的个数 -- 比较基准值size_t blackCount = 0;Node* pCur = pRoot;while (pCur){if (BLACK == pCur->_col)blackCount++;pCur = pCur->_left;}// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数size_t k = 0;return _IsValidRBTree(pRoot, k, blackCount);}
private://求最大高度int _maxHeight(Node* root){if (root == nullptr)return 0;int lh = _maxHeight(root->_left);int rh = _maxHeight(root->_right);return lh > rh ? lh + 1 : rh + 1;}//求最小高度int _minHeight(Node* root){if (root == nullptr)return 0;int lh = _minHeight(root->_left);int rh = _minHeight(root->_right);return lh < rh ? lh + 1 : rh + 1;}//中序遍历void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}//是否是合法的红黑树bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount){//走到null之后，判断k和black是否相等if (nullptr == pRoot){if (k != blackCount){cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;return false;}return true;}// 统计黑色节点的个数if (BLACK == pRoot->_col)k++;// 检测当前节点与其双亲是否都为红色if (RED == pRoot->_col && pRoot->_parent && pRoot->_parent->_col == RED){cout << "违反性质三：存在连在一起的红色节点" << endl;return false;}return _IsValidRBTree(pRoot->_left, k, blackCount) &&_IsValidRBTree(pRoot->_right, k, blackCount);}