二叉搜索树：【C 进阶学习】第五弹——二叉搜索树——二叉树进阶及set和map的铺垫-CSDN博客
AVL树：
【C 进阶学习】第七弹——AVL树——树形结构存储数据的经典模块-CSDN博客
前言：
在前面，我们已经学习了二叉搜索树和它的改进AVL树，今天，我们来学习另一种由二叉搜索树改进而来的树形结构——红黑树
一、红黑树的概念
红黑树是一种特殊的二叉树，它的每个节点都增加一个存储为表示颜色，要么是黑色，要么是白色。并且通过对每条路径上添加节点时节点的颜色限制，来确保每个路径上的黑色节点数量一致，且最长路径长度最多是最短路径长度的两倍，因此达到平衡。
二、红黑树的性质
红黑树有以下五个性质：
- 节点是红色或黑色：每个节点都有一个颜色属性，颜色可以是红色或黑色。
- 根节点是黑色：树的根节点必须是黑色。
- 红色节点的子节点是黑色：如果一个节点是红色，则它的两个子节点必须是黑色（即不能有两个连续的红色节点）。
- 每个节点到其每个叶子节点的路径都包含相同数量的黑色节点：从任何节点到其每个叶子节点的路径上，经过的黑色节点的数量必须相同。
- 叶子节点是黑色：红黑树的叶子节点（通常是指空节点）被视为黑色。
三、红黑树的节点结构
代码语言：javascript复制template<class K, class V>
struct BSTreeNode
{
BSTreeNode<K, V>* _left; //左子树
BSTreeNode<K, V>* _right; //右子树
BSTreeNode<K, V>* _parent; //父亲
pair<K, V> _kv; //存放节点值的
string _col; //颜色（通过这个可以直到左右子树存在情况）
//构造函数
BSTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col("RED") //默认颜色为红色
{}
};红黑树的节点结构与二叉搜索树和AVL树差别不大，最大的差别就是加入了一个新的存储点——颜色
四、红黑树的操作
红黑树的基本操作包括插入、删除和查找。以下是这些操作的简要说明：
- 插入：
- 将新节点插入到树中，初始时将其标记为红色。
- 可能会破坏红黑树的性质，需要通过旋转和重新着色来恢复性质。
- 删除：
- 删除节点后，可能会破坏红黑树的性质。
- 需要进行调整，包括旋转和重新着色，以恢复红黑树的性质。
- 查找：
- 查找操作与普通的二叉搜索树相同，通过比较节点值来决定向左或向右子树查找。
在这几个操作中，插入是红黑树的关键，因为这是构造红黑树的关键，怎样插入才能保证红黑树的节点颜色、路径长度符合规定，下面我们就来重点讲解一下红黑树的节点插入操作：
首先我们要先清楚一点，红黑树也是二叉搜索树，所以它肯定是符合二叉搜索树的性质的——左边子树值小于根，右边子树值大于根
问题的关键是如何保证插入后结构的颜色符合规定，要做到这一点，我们首先就先要摸清插入节点会遇到的所有情况，然后我们再分析如何解决这些情况：
（强调一下：一定要把前面AVL树中讲的左右旋先弄明白）
假设：cur表示当前节点，p表示父节点，g表示祖父节点，u为叔叔节点
情况一：cur为红，p为黑
情况二: cur为红，p为红，g为黑，u存在且为红
解决方法：把p、u变成黑，g变为红，然后让g变为cur继续向上处理
情况三：cur为红，p为红，g为黑，u不存在
解决方法：把p变为黑，g变为红，然后进行左旋/右旋
情况四：cur为红，p为红，g为黑，u存在且为黑
解决方法：把p变为黑，g变为红，同时右旋/左旋
特殊情况：如果当cur的插入位置形似AVL树中的RL型或LR型时，要先进行旋转转换成上面几种情况
五、红黑树的实现代码
RBTree.h
代码语言：javascript复制//红黑树
#include<iostream>
using namespace std;
template<class K, class V>
struct BSTreeNode
{
BSTreeNode<K, V>* _left; //左子树
BSTreeNode<K, V>* _right; //右子树
BSTreeNode<K, V>* _parent; //父亲
pair<K, V> _kv; //存放节点值的
string _col; //颜色（通过这个可以直到左右子树存在情况）
//构造函数
BSTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col("RED") //默认颜色为红色
{}
};
template<class K, class V>
class BSTree
{
typedef BSTreeNode<K, V> Node;
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)
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
cur->_col = "RED"; //插入节点颜色为红色
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
//按搜索二叉树规则插入到指定位置后，再检验一下是否符合红黑树的规则进行相关调整
while (parent && parent->_col == "RED") //当父节点存在且父节点为红时，进行相关调整
{
Node* grandfather = parent->_parent;
if(parent==grandfather->_left) //p为g的左孩子时
{
// g
// p
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == "RED") //u存在且为红
{
// g
// p u
// cur
parent->_col = uncle->_col = "BLACK";
grandfather->_col = "RED";
//继续往上更新
cur = grandfather;
parent = cur->_parent;
}
else //u不存在/u存在且为黑
{
// g
// p
// cur
if (cur == parent->_left)
{
RotateR(grandfather);
grandfather->_col = "RED";
parent->_col = "BLACK";
}
else
{
//LR型
RotateL(parent);
RotateR(grandfather);
cur->_col = "BLACK";
grandfather->_col = "RED";
}
break;
}
}
else //p为g的右孩子时，与上面的相反即可
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == "RED")
{
parent->_col = uncle->_col = "BLACK";
grandfather->_col = "RED";
//继续往上更新
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
// g
// u p
// c
RotateL(grandfather);
grandfather->_col = "RED";
parent->_col = "BLACK";
}
else
{
// g
// u p
// c
//RL型
RotateR(parent);
RotateL(grandfather);
cur->_col = "BLACK";
grandfather->_col = "RED";
}
break;
}
}
}
_root->_col = "Black";
return true;
}
//进行旋转调整（旋转操作与AVL树中的完全一样，不明白的可以看我之前的文章）
void RotateL(Node* parent) //左单旋
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentParent = parent->_parent;
parent->_right = subRL;
subR->_left = parent;
if(subRL)
subRL->_parent = parent;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
parent->_parent = subR;
}
void RotateR(Node* parent) //右单旋
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentParent = parent->_parent;
parent->_left = subLR;
subL->_right = parent;
if (subLR)
{
subLR->_parent = parent;
}
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
parent->_parent = subL;
}
//中序打印
void Inorder()
{
_Inorder(_root);
cout << endl;
}
void _Inorder(Node* root)
{
if (root == nullptr)
return;
_Inorder(root->_left);
cout << root->_kv.first << " ";
_Inorder(root->_right);
}
//检查是否为BS树（检查两点）
//一：是否有连续的红节点
//二：各个路径上的黑色节点个数是否相等
bool Check(Node* root,int blacknum,const int refVal)
{
if (root == nullptr)
{
if (blacknum != refVal)
{
cout << "存在黑色节点个数不相等的路径" << endl;
return false;
}
return true;
}
if (root->_col == "RED"&&root->_parent->_col=="RED")
{
cout << "有连续的红色节点" << endl;
return false;
}
if (root->_col == "BLACK")
blacknum;
return Check(root->_left, blacknum, refVal) //红黑树的左右子树也是红黑树
&& Check(root->_right, blacknum, refVal); //所以要用递归对左右子树也进行判断
}
bool IsBalance()
{
if (_root == nullptr)
return true;
if (_root->_col == "RED")
return false;
int refVal = 0; //参考值
Node* cur = _root;
while (cur)
{
if (cur->_col == "BLACK")
{
refVal;
}
cur = cur->_left;
}
int blacknum = 0; //根节点到当前节点黑色节点数量
return Check(_root, blacknum,refVal);
}
private:
Node* _root = nullptr;
};RBTree.c
代码语言：javascript复制//红黑树
int main()
{
int a[] = { 4,2,6,1,3,5,15,7,16,14 };
//int a[] = { 790,760,969,270,31,424,377,24,702 };
BSTree<int, int> t;
for (auto e : a)
{
t.Insert(make_pair(e, e));
}
t.Inorder();
cout << "是否是红黑树（1/0）："<<t.IsBalance() << endl;
return 0;
}运行结果：
六、总结
以上就是红黑树的全部内容，红黑树因为其自平衡的特性，及通过节点颜色来操作其树形结构的特点，极大的提高了数据存储及处理的效率，需要我们好好掌握
感谢各位大佬观看，创作不易，还请各位大佬一键三连！！！
