目录
前言：
红黑树，二叉搜索树的一种，基于红黑树实现的结构有map 和 set，红黑树是一种近似平衡的结构，也就是没有把高度卡的特别死。这个结构基于原来搜索二叉树优化的点是在于使用颜色，来判断简单路径的长度，从而达到平衡的目的。
既然要通过简单路径来判断平衡，所以红黑树引入了以下的几条规则：
1：节点不是黑色就是红色，2：根节点是黑色的，3：不存在连续的两个红色节点，4：每条简单路径上的黑色节点数目应该相同
只要满足了以上的4个条件，那么就可以达到最短路径的二倍不超过最长路径。
在这个部分呢着重介绍于插入部分的调整以及判断整个树是否满足红黑树的条件，其他函数和AVL树部分基本上没有啥差别。
现在就进入插入部分。
1 插入部分
插入之前，我们不妨先了解红黑树的节点构成，红黑树，有颜色，所以我们需要用变量来表示颜色，这里采用的是使用枚举，定义RED 和 BLACK表示颜色，同样的，红黑树也要使用三叉链结构，在调整的时候parent用得上，其次就是我们使用key-value结构：
enum Colour
{
BLACK,RED
};
//红黑树的节点构成
template<class T, class V>
struct RBTreeNode
{
RBTreeNode<T, V>* _left;
RBTreeNode<T, V>* _right;
RBTreeNode<T, V>* _parent;
Colour _col;
pair<T, V> _kv;
RBTreeNode(const pair<T,V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_col(RED)
{}
};
对于枚举常量的命名来讲，一般的命名约定是全部大写。
初始化和定义变量这里也是没有多大的问题的，就可以过了-》猜猜为什么颜色要初始化为红色而不是黑色呢？
整体红黑树和AVL树没有区别：
template<class T,class V>
class RBTree
{
public:
typedef RBTreeNode<T, V> Node;
private:
Node* _root = nullptr;
};这里给一个缺省值nullptr要方便许多，不然后面会出现越界的问题的。
插入和二叉搜索树 AVL树都是一样的，唯一的区别就是调整部分，AVL树调整的是平衡因子，二叉搜索树调整的，，没有调整，红黑树调整的是颜色，所以调整之前的插入部分，连接部分都是一样的，唯一的区别就是如果插入的是根节点要把颜色给成黑色：
bool Insert(const pair<T, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
//根节点必须为黑色
_root->_col = BLACK;
return true;
}
Node* root = _root;
Node* parent = nullptr;
//判断部分
while (root)
{
if (kv.first > root->_kv.first)
{
parent = root;
root = root->_right;
}
else if (kv.first < root->_kv.first)
{
parent = root;
root = root->_left;
}
else
{
return false;
}
}
Node* cur = new Node(kv);
//连接部分 开始判断大小关系
if (parent->_kv.first > kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
//颜色更替开始
}
return true;
}现在开始就是颜色调整部分了，我们首先思考一个问题：
插入的节点我们应该设置为红色还是黑色？
就这么草率的思考不太容易，这样想，当你犯错之后，你的家庭是严母慈父，你会给谁说？那肯定是慈父对吧？那么红黑树的四条规则，我们插入节点影响的就是第三条规则和第四条规则，所以现在要看的就是第三条规则和第四条规则谁更凶一点。
显然，我们非要得罪一条规则的话，就应该得罪规则3，规则4可得罪不起，因为一旦有一条路径的黑色节点数不一样，那整棵树就报废了，如果只是两个连续的红色节点，我们是可以通过调整的方法，来是颜色符合规则，所以调整规则3容易，规则4可不容易。
那么回到开篇的问题，为什么颜色的节点一开始就初识化成了红色，方便插入呗。
插入的时候，我们大体可以分为两种情况
情况一，u存在且节点颜色为红色，情况2 ，u不存或者u的节点颜色为黑色
这里我们简单理解，g就是grandfather，p就是parent，u就是uncle，cur就是当前节点的意思。
思考一个问题，为什么情况是根据u的颜色来判断的？
我们前面提到了，如果出现两个连续的红色就可以使用调整，使颜色满足条件，但是同时规则4也要满足，对于情况1的调整就是，cur颜色不变，p和u的颜色变黑，g的颜色变红，依次往上调整，如果g是根节点，那么停止，此时颜色情况是g，p，u颜色都为黑色，cur是红色，满足条件。这时就应该有人懂了为什么只规定了不能存在连续的红色节点而不是黑色节点了吧？那么变色到什么程度就结束呢？当调整到没有连续的红色节点，即parent的颜色是黑色的时候就结束，或是调整到了根也就结束，此时根的颜色是红色怎么办？改就完事儿了，没有规定说不能有连续的黑色节点。
那么我们来分析情况2，如果u是黑色或不存在，还能不能使用变色的套路？当然不行，如果cur是红色，变色，p为黑色，u为红色，g为红色，此时u所在的路径的黑色节点少了一个，变色不能满足规则4了，所以这里需要用到旋转，没错，就是AVL树的旋转。
这里再提一个问题，根节点是黑色的母庸质疑，其他的黑色节点怎么来的呢？
结合插入的变色，我们就可以知道黑色节点的来源全都是红色节点变过去的。
现在两个大体情况介绍完了，就可以开始调整了
对于情况一：
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;
//一层一层的遍历 father层遍历完了所以直接到grandparent层
cur = grandfather;
parent = grandfather->_parent;
}
//uncle不存在或者是为黑色
else
{
}
}
//父节点在右边
else
{
//存在 且 为红
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//一层一层的遍历 father层遍历完了所以直接到grandparent层
cur = grandfather;
parent = grandfather->_parent;
}
//不存在 或 为黑色
else
{
}
}
_root->_col = BLACK;
return true;
}大体的判断是cur是parent的哪一边，这样后面就好旋转了，有人会问，parent为空或者根节点颜色为红需要单独判断吗？这完全不需要，只需要在插入的最好给根节点抹上最后一缕黑色就可以了，不管根是不是红，给上了就完全没问题，那么parent如果是空，也就是调整到根节点了，就可以直接break了。
对于情况二：
此时u为黑色，我们就以g为旋转点，进行一个右旋就可以，判断条件就是p是g的左边，心里想着那条V型的线，进行右旋，左旋是同理的，旋转好了之后，就改变颜色，我们要保证每一条路径的黑色节点数目一样，那么，如果cur在p的右边怎么办？那简单，P先左旋，g在右旋，就搞定了：
//不存在 或 为黑色
else
{
//旋转 -> 通过判断 cur的位置来判断是单旋还是双旋
if (cur == parent->_left)
{
RotateR(grandfather);
//即原位置变为黑色
parent->_col = BLACK;
//如果不变红，导致黑色节点多出来一个
grandfather->_col = RED;
}
//双旋
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
//不存在 或 为黑色
else
{
//旋转 -> 通过判断 cur的位置来判断是单旋还是双旋
if (cur == parent->_right)
{
RotateL(grandfather);
//即原位置变为黑色
parent->_col = BLACK;
//如果不变红，导致黑色节点多出来一个
grandfather->_col = RED;
}
//双旋
else
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}这就是剩下的两个else，旋转完之后的树是肯定平衡了的，所以也就不用继续了，break是可加可不加的，毕竟颜色已经改变，也就不会再进循环了，但是加上更好一点，整体的插入代码如下：
bool Insert(const pair<T, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
//根节点必须为黑色
_root->_col = BLACK;
return true;
}
Node* root = _root;
Node* parent = nullptr;
//判断部分
while (root)
{
if (kv.first > root->_kv.first)
{
parent = root;
root = root->_right;
}
else if (kv.first < root->_kv.first)
{
parent = root;
root = root->_left;
}
else
{
return false;
}
}
Node* cur = new Node(kv);
//连接部分 开始判断大小关系
if (parent->_kv.first > kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = 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;
//一层一层的遍历 father层遍历完了所以直接到grandparent层
cur = grandfather;
parent = grandfather->_parent;
}
//uncle不存在或者是为黑色
else
{
//旋转 -> 通过判断 cur的位置来判断是单旋还是双旋
if (cur == parent->_left)
{
RotateR(grandfather);
//即原位置变为黑色
parent->_col = BLACK;
//如果不变红，导致黑色节点多出来一个
grandfather->_col = RED;
}
//双旋
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
//父节点在右边
else
{
//存在 且 为红
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//一层一层的遍历 father层遍历完了所以直接到grandparent层
cur = grandfather;
parent = grandfather->_parent;
}
//不存在 或 为黑色
else
{
//旋转 -> 通过判断 cur的位置来判断是单旋还是双旋
if (cur == parent->_right)
{
RotateL(grandfather);
//即原位置变为黑色
parent->_col = BLACK;
//如果不变红，导致黑色节点多出来一个
grandfather->_col = RED;
}
//双旋
else
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}2 判断部分
判断红黑树是否达标，无非就是4个规则是否完成了，其中根节点是黑色可以一进函数就开始判断，不是红色就是黑色这条件根本就不用判断，我们一共就设置了两个颜色，所以不用管，是否存在两个连续的红色节点，有同学的解决方案是每个节点都和自己的两个孩子进行比较，但是这太麻烦了，还要判空什么的，所以这里我们可以逆向思维，节点和自己的父节点比较即可，判断每条路径的黑色节点的数目是否一样，我们可以创建一个临时变量，某条路径走到头了就和这个基准值比较一下即可：
bool IsBalance()
{
//根节点必须为黑色
if (_root->_col == RED)
{
return false;
}
//创建一个黑色节点基准值
int base = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
{
base++;
}
cur = cur->_left;
}
return Check(_root, 0, base);
}
private:
bool Check(Node* root,int blackNum,const int base)
{
//走到底判断黑色节点是否一样
if (root == nullptr)
{
if (base != blackNum)
{
cout << "存在黑色节点不相同的路径" << endl;
return false;
}
return true;
}
//判断是否存在连续的两个红色节点
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "存在连续的两个红色节点" << endl;
cout << root->_kv.first << endl;
return false;
}
if (root->_col == BLACK)
{
blackNum++;
}
return Check(root->_left, blackNum, base) &&
Check(root->_right, blackNum, base);
}整个红黑树到这里就结束了，相对于AVL树来说，红黑树要简单一点，这里可以多对比一下。
感谢阅读！