红黑树的概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过 对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩 倍，因而是近似平衡的。
红黑树的性质
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的，则它的两个孩子结点是黑色的;//两个红节点不能相邻;
- 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
- 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
推出结论：红黑树的最短路径为全是黑色结点，最长路径为一红一黑交替的路径。如此即可保证红黑树的最长路径不超过最短路径的两倍。
红黑树节点的定义
//与AVL树差不多，多了节点的颜色，用枚举定义;
enum Color
{
BLACK,
RED
};
template <class K, class V>
struct RBTreeNode
{
typedef RBTreeNode<K, V> Node;//K-V
Node* _left;
Node* _right;
Node* _parent;//方便插入时调整;
pair<K, V> _kv;
Color _color;
RBTreeNode(const pair<K, V> kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
//,_data(data)
,_kv(kv)
,_color(RED)
{}
};
在这里结点颜色默认设置为红色，是为了方便后续插入，在保证红黑树性质的情况下，通过插入红色结点可以更好的保证性质四不被破坏，而如果插入黑色结点，那么保证每条路径的黑色结点数量相等操作将非常繁琐。
红黑树的结构
template <class K, class V>
class RBTree
{
public:
typedef RBTreeNode<K,V> Node;
RBTree()
:_root(nullptr)
{}
private:
Node* _root;
};
STL中的红黑树其实还有个头结点，左连min，右连max;我们简单学习，不引入了:
红黑树的插入操作
- 黑树是在二叉搜索树的基础上加上其平衡限制条件(RB)，因此红黑树的插入可分为两步:
- 按照二叉搜索的树规则插入新节点;
- 按照红黑树规则调整节点;
情况1
将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。
情况2
此时如果cur在p左侧（如上图），那就对g右单旋转+swap p和g的颜色
此时如果cur在p右侧(想象cur和c交换了位置),那就是先对p左单旋（就转换为了上一种需要单旋的情况），再对g右单旋的 左右双旋，再调整旋转后的颜色即完成，break;
以上情况是p再g的左侧情况，p再g的右侧情况同理，只是uncle和parent的位置左右变换+旋转方向的变换，一个道理！
这两个情况满足了红黑树的所有特点，不信的可以仔细画图分析，注意，情况2可能是情况1发生以后，向上调整得到的，需要两次结合判断黑色节点数相不相同;
插入代码
bool Insert(pair<K,V>& kv)
{
if (!_root) {
_root = new Node(kv);
_root->_color = BLACK;
return true;
}
Node* cur = _root;
Node* parent = cur;
while (cur)
{
if (cur->_kv.first > kv.first) {
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first) {
parent = cur;
cur = cur->_right;
}
else return false; //数据冗余;
}
cur = new Node(kv);
cur->_parent = parent;
if (parent->_kv.first<kv.first) {
parent->_right = cur;
}
else {
parent->_left = cur;
}
//调整
while (parent && parent->_color == RED)//父节点为红才需要调整;
{
//由于parent存在且颜色为红，故panret一定不为根 --》那么grandfather一定存在
Node* grandparent = parent->_parent;
Node* uncle;
if (grandparent->_left == parent) {//牵扯旋转方向
uncle = grandparent->_right;
//只变色:1.p u存在且为红，g为黑;--> p u变黑g变红，向上调整;
if (uncle&&uncle->_color == RED) {
parent->_color = BLACK;
uncle->_color = BLACK;
grandparent->_color = RED;
//向上调整;
cur = grandparent;//红的子root
parent = cur->_parent;//用于while进一步判断
}
else {//2单旋+变色 uncle不存在or为黑
if (parent->_left == cur) {
RotateR(grandparent);
grandparent->_color = RED;
parent->_color = BLACK;
cur->_color = RED;
}
else {//3双旋+变色
RotateL(parent);
RotateR(grandparent);
grandparent->_color = RED;
parent->_color = RED;
cur->_color = BLACK;
}
break;//直接满足性质了 break；
}
}
else{
uncle = grandparent->_left;
if (uncle && uncle->_color == RED)//case 1
{
parent->_color = BLACK;
uncle->_color = BLACK;
grandparent->_color = RED;
//向上调整;
cur = grandparent;
parent = cur->_parent;
}
else {
if (parent->_right == cur) {//case2 单xuan
RotateL(grandparent);
parent->_color = BLACK;
cur->_color = RED;
grandparent->_color = RED;
}
else {//case2 双xuan
RotateR(parent);
RotateL(grandparent);
grandparent->_color = RED;
parent->_color = RED;
cur->_color = BLACK;
}
break;
}
}
}
_root->_color = BLACK;//不论如何，直接将根节点颜色置为黑色 因为有种跳的过程中 根会变红!
return true;
}
红黑树的验证
//验证根节点是黑色
bool IsRBTree()
{
if (_root == nullptr)//空树也是红黑树
return true;
//检测性质二：根节点是黑色
if (_root->_color != BLACK)
{
cout << "违反规则二，根结点为红色" << endl;
return false;
}
}
//验证两个红色节点不能挨着
bool Check_RED_RED(Node* root)
{
//由于在调用函数中已经检测了根节点的合法性
//故此处的root结点必不为红色
if (root == nullptr)
return true;
if (root->_color == RED && root->_parent->_color == RED)
{
cout << "违反规则三，有连续的红色结点" << endl;
return false;
}
return Check_RED_RED(root->_left) && Check_RED_RED(root->_right);
}
//验证每条路径黑色节点数相同;
bool Check_BlackNum(Node* root, int benchMark, int blacknum)
{
if (root == nullptr)//到空结点，此时blacknum为该条路径的黑色结点数量
{
if (blacknum == benchMark)
return true;
else
return false;
}
if (root->_color == BLACK)
blacknum++;
return Check_BlackNum(root->_left, benchMark, blacknum)&&Check_BlackNum(root->_right, benchMark, blacknum);
}
//前几个函数的综合;
bool IsRBTree()
{
if (_root == nullptr)//空树也是红黑树
return true;
//检测性质二：根节点是黑色
if (_root->_color != BLACK)
{
cout << "违反规则二，根结点为红色" << endl;
return false;
}
//计算最左路径上黑色结点的数量作为基准值
int benchMark = 0;
Node* cur = _root;
while (cur)
{
if (cur->_color == BLACK)
benchMark++;
cur = cur->_left;
}
int blacknum = 0;
return Check_RED_RED(_root) && Check_BlackNum(_root, benchMark, blacknum);
}
红黑树和AVL树比较
红黑树与AVL树都是平衡的二叉树（一个相对平衡不超过2倍，一个绝对平衡）：
- AVL树是严格平衡的，而红黑树是近似平衡的\
- AVL树和红黑树的查找时间复杂度都是O(log2N)
- 但是:由于红黑树的设计使得旋转次数更少，因此在增删过程中性能较优
这也是stl中的map和set底层封装红黑树的原因，同事操作系统内核中的很多设计也都是封装红黑树;eg:epoll的fd红黑树节点，就绪以后快速找到，回调去就绪链表；
扫一扫
1976
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
