目录
1. 红黑树的设计方式
- 除开AVL树之外，又一种平衡二叉搜索树，相较于AVL树它对平衡状态的要求相对松散，搜索效率略微劣势，单影响不大。
- 红黑树相对AVL树而言其对平衡状态的要求比较松散，正因其在旋转调整次数上，有了显著的降低，所以在构建效率上更加高。
- 综合而言，红黑树的结构优于AVL树，所以大部分C++库中，容器底层封装的数据结构都为红黑树。
1.1 红黑树的结构规则
- 红黑树的这种平衡搜索二叉树形式，对于平衡状态的定义为，对于树中的每一个结点，其到一个叶子结点的最长路径不超过最短路径的二倍。
- 那么，红黑树是通过怎样的构建方式，使得整颗树得以处于上述的平衡状态呢？红黑树有一套结构规则，只要使得整颗树都符合这套规则，就可以将整棵树控制在平衡状态，具体如下：
- 红黑树的结构规则：
<1> 红黑树中的结点，只能为红色，或黑色
<2> 红黑树的根结点必须为黑色
<3> 红黑树中的红色结点不能够连续
<4> 红黑树每个结点到达任意一个叶子结点的所有路径，每条路径上的黑色结点数量相同
1.2 插入场景分析与失衡调整策略
1.2.1 场景分析与逻辑抽象
- 因为红黑树的每个结点的叶子路径上，其的黑色结点数量都必须要相等，若新插入结点为黑色，即使经过调整，此条规则就无法得到保证与满足。
- 所以，向红黑树中新插入的结点，除开根节点外，只能是红色，根节点在插入后，再调整为黑色。
- 插入结点颜色固定为红，根据插入结点的父节点颜色，可以将插入场景现粗略分为2种，针对不同的插入场景有不同的处理方式，具体如下：
<1> 父节点为黑色，新插入一个红色结点后，不会破坏红黑树原本的平衡状态，因此，插入后直接结束
<2> 父结点为红色，先插入一个红色结点后，会出现两个连续的红色结点，破坏了红黑树的构建规则，因此，需要进行相应的调整处理
- 当插入结点的父结点为红时，红黑树就出现了两个连续的红色结点，必须要经过相应的变色处理，才能够使得红黑树重新符合平衡规则。
- 在变色的过程中，不得违反其他的平衡规则，由此，我们要将父节点为红的这一插入场景再次细分，从而来使用不同的平衡调整策略。
- 父节点为红色时，红黑树的模拟计算抽象模型：
- 当parent结点为红色时，插入场景根据调整策略的不同，可以分为两类：
<1> uncle结点为红色
<2> uncle结点为黑色或为空
- uncle结点为红时的调整策略：
<1> parent结点与uncle结点变黑
<2> grandparent结点变红
<3> grandparent结点变为新的cur结点，重复上两个步骤
<4> 直至cur的parent结点为黑色结束，或遍历至根结点，若遍历至根结点，最后再将根结点变黑
<5> 在此过程中，uncle结点为红色才能进行如上处理
1.2.2 uncle结点为红时的插入场景枚举：
红黑树计算模型
抽象子树abcde为空
抽象子树cde中每条路径都包含一个黑色结点
抽象子树结构cde中每条路径中有两个黑色结点
1.2.3 uncle结点为黑色/空的调整策略
- 左高，parent为grandparent的左孩子，cur为parent的左孩子，对grandparent进行右单旋
- 右高，parent为grandparent的右孩子，cur为parent的右孩子，对grandparent进行左单旋
- 变色：进行单旋后，parent变为黑色，grandparent变为红色
- 左右高，parent为grandparent的左孩子，cur为parent的右孩子，对cur先进行左单旋，再对grandparent进行右单旋
- 右左高，parent为grandparent的右孩子，cur为parent的左孩子，对cur先进行右单旋，再对grandparent进行左单旋
- 变色：进行双旋后，cur变为黑色，grandparent变为红色
2. 红黑树的简单实现
2.1 红黑树与结点的结构
enum colour
{
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;
colour _col;
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_col(Red)
{}
};
template<class K, class V>
class RBTree
{
public:
//查找
bool Find(K key);
//插入
bool Insert(const pair<K, V>& kv);
//中序遍历
void InOrder();
//平衡检测
bool IsBalance();
private:
RBTreeNode<K, V>* _root = nullptr;
};
2.2 查找
//查找
bool Find(K key)
{
RBTNode* cur = _root;
while (cur)
{
if (key < cur->_kv.first)
{
cur = cur->_left;
}
else if (key > cur->_kv.first)
{
cur = cur->_right;
}
else
{
return true;
}
}
return false;
}
2.3 插入
2.3.1 插入主体逻辑
//插入
bool Insert(const pair<K, V>& kv)
{
//找到插入位置
RBTNode* cur = _root;
RBTNode* parent = nullptr;
while (cur)
{
if (kv.first < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
//有相同值，插入失败
return false;
}
}
//插入
cur = new RBTNode(kv);
if (_root == nullptr)//根结点
{
_root = cur;
_root->_col = Black;
return true;
}
else
{
if (kv.first < parent->_kv.first)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
}
//判断与调整
while (parent)
{
//父亲结点为黑色
if (parent->_col == Black)
{
break;
}
else//父结点为红色
{
RBTNode* grandparent = parent->_parent;
RBTNode* uncle = grandparent->_left;
if (parent == grandparent->_left)
{
uncle = grandparent->_right;
}
//叔叔结点存在且为红色
if (uncle && uncle->_col == Red)
{
parent->_col = uncle->_col = Black;
grandparent->_col = Red;
cur = grandparent;
//注，父节点存放变量也需重置
parent = cur->_parent;
}
else//叔叔结点为黑色/不存在
{
if (parent == grandparent->_left)//左外高
{
if (cur == parent->_left)//右单旋
{
// g
// p u
//c
RotateR(grandparent);
parent->_col = Black;
grandparent->_col = Red;
}
else//左右双旋
{
// g
// p u
// c
RotateLR(grandparent);
cur->_col = Black;
grandparent->_col = Red;
}
}
else//右外高
{
if (cur == parent->_right)//左单旋
{
// g
//u p
// c
RotateL(grandparent);
parent->_col = Black;
grandparent->_col = Red;
}
else//右左双旋
{
// g
//u p
// c
RotateRL(grandparent);
cur->_col = Black;
grandparent->_col = Red;
}
}
break;
}
}
}
_root->_col = Black;
return true;
}
2.3.2 左单旋
//左单旋
void RotateL(RBTNode* parent)
{
Rotate_count++;
RBTNode* SubR = parent->_right;
RBTNode* SubRL = SubR->_left;
//SubRL变为parent的右孩子
parent->_right = SubRL;
//SubRL的父节点指针处理，SubRL可能为空
if (SubRL)
SubRL->_parent = parent;
//parent变为SubR的左孩子
SubR->_left = parent;
//SubR的父结点指针处理
RBTNode* ppnode = parent->_parent;
SubR->_parent = ppnode;
if (ppnode == nullptr)//parent为根
{
_root = SubR;
}
else//parent不为根
{
if (parent == ppnode->_left)
{
ppnode->_left = SubR;
}
else
{
ppnode->_right = SubR;
}
}
//parent的父结点指针处理
parent->_parent = SubR;
}
2.3.3 右单旋
//右单旋
void RotateR(RBTNode* parent)
{
Rotate_count++;
RBTNode* SubL = parent->_left;
RBTNode* SubLR = SubL->_right;
//SubLR变为parent的左孩子
parent->_left = SubLR;
//处理父指针
if (SubLR)
SubLR->_parent = parent;
//parent变为SubL的右孩子
SubL->_right = parent;
//处理父指针
RBTNode* ppnode = parent->_parent;
SubL->_parent = ppnode;
if (ppnode == nullptr)
{
_root = SubL;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = SubL;
}
else
{
ppnode->_right = SubL;
}
}
parent->_parent = SubL;
}
2.3.4 左右双旋
void RotateLR(RBTNode* parent)
{
RBTNode* SubL = parent->_left;
RBTNode* SubLR = SubL->_right;
RotateL(SubL);
RotateR(parent);
}
2.3.4 右左双旋
//右左双旋
void RotateRL(RBTNode* parent)
{
RBTNode* SubR = parent->_right;
RBTNode* SubRL = SubR->_left;
//右旋
RotateR(SubR);
RotateL(parent);
}
2.4 中序遍历与平衡检测
2.4.1 中序遍历
void _InOrder(RBTNode* cur)
{
if (cur == nullptr)
{
return;
}
_InOrder(cur->_left);
cout << cur->_kv.first << ":" << cur->_kv.second << " ";
_InOrder(cur->_right);
}
//中序遍历
void InOrder()
{
_InOrder(_root);
cout << endl;
}
2.4.2 平衡检测
//没有相连的红色结点，向上比对
//每条路径上的黑色结点数相同，先求一条路径
bool _IsBalance(RBTNode* cur, int count)
{
if (cur == nullptr)
{
if (count)
{
cout << "黑色结点数量不同" << endl;
return false;
}
return true;
}
if (cur->_col == Black)
{
count--;
}
if (cur->_col == Red && cur->_parent->_col == Red)
{
cout << "存在连续的红色结点" << endl;
return false;
}
return _IsBalance(cur->_left, count) && _IsBalance(cur->_right, count);
}
//平衡检测
bool IsBalance()
{
int count = 0;
RBTNode* cur = _root;
while (cur)
{
if (cur->_col == Black)
{
count++;
}
cur = cur->_left;
}
return _IsBalance(_root, count);
}