目录
引入
为了解决普通二叉搜索树的极端情况——退化为单支树，采用了平衡二叉搜索树，其中包含AVL树和红黑树，关于AVL树的剖析已经有详细介绍，本篇将会对红黑树进行深度剖析。
概念
红黑树根据其名称可以得知：其节点是有颜色的，包含两种节点：红节点和黑节点。红黑树与AVL树异曲同工之妙，红黑树舍弃了AVL树的严格条件（每个节点的平衡因子绝对是不大于1），而使用节点的颜色取而代之。
红黑树保证不会出现普通二叉搜索树极端情况的方法是：让红黑树的最长路径不超过最短路径的二倍，实现近似平衡。而完成这一要求，就需要了解红黑树的插入规则。
红黑树条件：1）每一个节点颜色不是红色就是黑色；
2）根节点必须是黑色；
3）如果一个节点是红色，则其左右节点必须是黑色；
4）对于每一个节点，从该节点到其所有后代叶节点的路径上都包含相同数量的黑节点。
思考：为什么红黑树的条件可以保证红黑树的最长路径不超过最短路径的二倍？？？
根据红黑树规则的第四条：全是黑节点的路径是最短路径。
根据红黑树规则的第三条：任何路径上不会出现连续的红节点，所以最长路径是一红一黑连续的路径。
根据以上两个规则就完美实现了，红黑树最长路径不超过最短路径的两倍。
红黑树没有AVL树平衡，这也意味着每一次插入红黑树调整的次数更少效率更高。但是其没有AVL树平衡，也说明其深度可能更深（实际上也不会太深），搜索效率不如AVL树。
与AVL树严格控制平衡所付出的代价相比，红黑树深度的增加微乎其微。
红黑的的实现
红黑树的节点存储内容：左右子树，父节点，颜色，数据。
enum Col
{
RED,
BLACK
};
template<class K,class V>
struct RBTreeNode
{
//默认构造函数
RBTreeNode(const pair<K, V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)
{ }
pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Col _col;
};
template<class K,class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
private:
Node* _root=nullptr;
};插入实现
红黑树的插入分两大类：1）根节点为空，插入黑色节点代替根节点；2）根节点不为空，创建红色节点，插入....
与AVL树插入显示也有三个步骤：1）找节点插入位置；2）判断是否需要调整；3）进行调整。
注意：在每次插入后，为防止根节点的颜色改变，需要将跟节点至为黑色。
找节点插入位置
找节点的方法与普通二叉树一样，在此不过多赘述了。
bool Insert(const pair<K, V> kv)
{
Node* newnode = new Node(kv);
if (_root == nullptr)
{
_root = newnode; //根节点为空，直接进行赋值
_root->_col = BLACK;
return true;
}
//根节点不为空，找节点插入位置
Node* pcur = _root;
Node* parent = nullptr;
while (pcur)
{
parent = pcur;
if (pcur->_kv.first > kv.first)
{
pcur = pcur->_left;
}
else if (pcur->_kv.first < kv.first)
{
pcur = pcur->_right;
}
else
{
return false; //相等不需要插入
}
}
//找到节点的位置
//进行插入
if (parent->_kv.first > kv.first)
{
parent->_left = newnode;
}
else
{
parent->_right = newnode;
}
newnode->_parent = parent;
//检查节点是否满足要求
//....
}新节点的父节点是黑色
新节点的父节点是黑色，插入成功，该节点满足条件，直接返回。
//检查节点是否满足要求
//....
//父节点是黑色，满足条件
if (parent->_col == BLACK)
{
_root->_col = BLACK;
return true;
}
else //父节点是红色，此时出现连续的红色，需要进行调整
{
}新节点的父节点是红色
新节点是红色则会出现有两种情况，根据uncle(newnode->parent->parent->child：新节点的爷爷节点的另一个子节点)节点进行区分。
1）uncle节点存在且为红色；
2）uncle节点不存在或uncle节点存在且为黑色。
如果新节点的父节点是红色，此时就出现了连续的红色节点，此时需要对红黑树进行调整。
此处处理颜色的关键是：让节点变色或将来连续的红节点分开。
uncle节点是红色
此处统一以cur，parent在左数为例。
对与uncle存在且是红色的处理方法比较简单：将uncle和parent的颜色换成黑色，将grandparent颜色换成红色即可。既保证了cur节点的父节点不在是红色，还让grandparent所在的支树中黑色节点的个数不变。
注意：此处的grandparent如果有父节点，还需要对父节点进行判断，父节点是不是红色。
else //父节点是红色，此时出现连续的红色，需要进行调整
{
pcur = newnode;
while (parent && parent->_col == RED)
{
Node* grandparent = parent->_parent;
if (parent == grandparent->_left) //分类确定uncle节点
{
Node* uncle = grandparent->_right;
if (uncle && uncle->_col == RED)
{
//对节点进行变色
uncle->_col = parent->_col = BLACK;
grandparent->_col = RED;
pcur = grandparent; //继续向上调整
parent = pcur->_parent;
}
else //uncle节点是空或uncle节点是黑色
{
}
}
else //parent=grandparent->_right
{
}
}
}uncle不存在或是黑色
当uncle节点不存在，或是黑色；仅仅变色已经解决不了问题了，此处与AVL树相似，也需要先进行旋转再变色。
关于旋转的具体细节可以看看《AVL树剖析》，此处就直接使用了。
通过旋转使得树的高度降低，跟趋近于平衡，通过变色让树重新成为红黑树。
当然旋转的情况和AVL树相同，也有四种情况：左旋，右旋，左右双旋，右左双旋。此处不再赘述，可移值《AVL树剖析》。
else //uncle节点是空或uncle节点是黑色
{
//判断旋转方式
//上述if条件中已经确定了parent==grandparent->_left
if (pcur == parent->_left)
{
//以grandparent为中心，进行右旋
RotateR(grandparent);
//进行变色
parent->_col = BLACK;
grandparent->_col = RED;
_root->_col = BLACK;
//此处parent是当前子树的根且是黑色，不用继续向上调整了
return true;
}
else //cur==parent->_right
{
//需要进行双旋
RotateL(parent);
RotateR(grandparent);
//调色
pcur->_col = BLACK;
grandparent->_col = parent->_col = RED;
_root->_col = BLACK;
return true;
}
}插入代码汇总
bool Insert(const pair<K, V> kv)
{
Node* newnode = new Node(kv);
if (_root == nullptr)
{
_root = newnode; //根节点为空，直接进行赋值
_root->_col = BLACK;
return true;
}
//根节点不为空，找节点插入位置
Node* pcur = _root;
Node* parent = nullptr;
while (pcur)
{
parent = pcur;
if (pcur->_kv.first > kv.first)
{
pcur = pcur->_left;
}
else if (pcur->_kv.first < kv.first)
{
pcur = pcur->_right;
}
else
{
return false; //相等不需要插入
}
}
//找到节点的位置
//进行插入
if (parent->_kv.first > kv.first)
{
parent->_left = newnode;
}
else
{
parent->_right = newnode;
}
newnode->_parent = parent;
//检查节点是否满足要求
//....
//父节点是黑色，满足条件
if (parent->_col == BLACK)
{
_root->_col = BLACK;
return true;
}
else //父节点是红色，此时出现连续的红色，需要进行调整
{
pcur = newnode;
while (parent && parent->_col == RED)
{
Node* grandparent = parent->_parent;
if (parent == grandparent->_left) //分类确定uncle节点
{
Node* uncle = grandparent->_right;
if (uncle && uncle->_col == RED)
{
//对节点进行变色
uncle->_col = parent->_col = BLACK;
grandparent->_col = RED;
pcur = grandparent; //继续向上调整
parent = pcur->_parent;
}
else //uncle节点是空或uncle节点是黑色
{
//判断旋转方式
//上述if条件中已经确定了parent==grandparent->_left
if (pcur == parent->_left)
{
//以grandparent为中心，进行右旋
RotateR(grandparent);
//进行变色
parent->_col = BLACK;
grandparent->_col = RED;
_root->_col = BLACK;
//此处parent是当前子树的根且是黑色，不用继续向上调整了
return true;
}
else //cur==parent->_right
{
//需要进行双旋
RotateL(parent);
RotateR(grandparent);
//调色
pcur->_col = BLACK;
grandparent->_col = parent->_col = RED;
_root->_col = BLACK;
return true;
}
}
}
else //parent=grandparent->rigth
{
Node* uncle = grandparent->_left;
if (uncle && uncle->_col == RED)
{
//对节点进行变色
uncle->_col = parent->_col = BLACK;
grandparent->_col = RED;
pcur = grandparent; //继续向上调整
parent = pcur->_parent;
}
else //uncle节点是空或uncle节点是黑色
{
//判断旋转方式
//上述if条件中已经确定了parent==grandparent->_right
if (pcur == parent->_right)
{
//以grandparent为中心，进行右旋
RotateL(grandparent);
//进行变色
parent->_col = BLACK;
grandparent->_col = RED;
//此处parent是当前子树的根且是黑色，不用继续向上调整了
_root->_col = BLACK;
return true;
}
else //cur==parent->_left
{
//需要进行双旋
RotateR(parent);
RotateL(grandparent);
//调色
pcur->_col = BLACK;
grandparent->_col = parent->_col = RED;
_root->_col = BLACK;
return true;
}
}
}
}
}
_root->_col = BLACK;
return true;
}对树进行检查
关于红黑树的检查主要检查：1）红节点是否连续；2）每条支路的黑节点个数是否相同。
1）如果一个节点是红节点，通过检查其父节点的颜色来确定是否有连续的红节点。
2）每条路的节点个数的检查：通过先遍历一条支路，统计黑色节点个数，再与其他支路比较。
bool Isbance()
{
int num = 0; //记录根到叶子节点有多少个黑节点
Node* pcur = _root;
while (pcur)
{
if (pcur->_col == BLACK)
{
++num;
}
pcur = pcur->_left;
}
return Isbance(_root,num,0); //num是每条支路黑节点个数的参照
}
private:
bool Isbance(Node* root,int num,int each) //each记录当前之路黑节点个数
{
if (root == nullptr)
{
if (each == num) //每条路的黑色节点数相同
return true;
cout << "黑色节点个数不对" << endl;
return false;
}
if (root->_col == BLACK)
{
each++;
}
else
{
if (root->_parent->_col == RED) //看父节点是不是红色
{
return false;
cout << root->_kv.first << " 红节点连续" << endl;
}
}
return Isbance(root->_left,num,each) && Isbance(root->_right,num,each);
}