【C++笔记】红黑树(RBTree)深度剖析和AVL树的对比分析
🔥个人主页：大白的编程日记
🔥专栏：C++笔记
文章目录
- 【C++笔记】红黑树(RBTree)深度剖析和AVL树的对比分析
- 前言
- 一.红黑树的定义
- 1.1 红黑树的概念
- 1.2红黑树的规则
- 1.3 红黑树对比AVL树
- 二.红黑树的插入
- 2.1插入分析
- 2.1变色
- 2.2 旋转+变色
- 2.3 代码实现
- 三.红黑树的查找
- 四.红黑树的验证
- 4.1 思路分析
- 4.2 代码实现
- 后言
前言
哈喽，各位小伙伴大家好!上期我们讲了反向迭代器和计算器。今天我们来讲一下红黑树的深度剖析。话不多说，我们进入正题！向大厂冲锋
一.红黑树的定义
1.1 红黑树的概念
红黑树是⼀棵⼆叉搜索树，他的每个结点增加⼀个存储位来表示结点的颜色，可以是红色或者黑色。通过对任何⼀条从根到叶子的路径上各个结点的颜色进行约束，红黑树确保没有⼀条路径会比其他路径长出2倍，因而是接近平衡的。
1.2红黑树的规则
-
每个结点不是红色就是黑色
-
根节点是黑色的
-
如果⼀个结点是红色的，则它的两个孩子结点必须是黑色的，也就是说任意⼀条路径不会有连续的红色结点。
-
对于任意⼀个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的黑色结点
这些都是红黑树。
-
说明：《算法导论》等书籍上补充了⼀条每个叶⼦结点(NIL)都是黑色的规则。他这里所指的叶子结点不是传统的意义上的叶子结点，而是我们说的空结点，有些书籍上也把NIL叫做外部结点。NIL是为了方便准确的标识出所有路径，《算法导论》在后续讲解实现的细节中也忽略了NIL结点，所以我们知道⼀下这个概念即可。
这棵树我们看可能以为是四条路径。
但是其实他是八条路径。
规定空节点是黑的符合红黑树的规则并且方便我们观察红黑树的路径。
由中这几点规则我们可以推出红黑树的性质：
- 最长路径<=2*最短路径
1.3 红黑树对比AVL树
红黑树的性能不如AVL树因为他没有那么严格地控制高度差。但是他的性能也不会太差，因为他控制最长路径<=2*最短路径。所以他的性能还是在logN的量级
红黑树的表达相对AVL树要抽象⼀些，AVL树通过高度差直观的控制了平衡。红黑树通过4条规则的颜色约束，间接的实现了近似平衡，他们效率都是同⼀档次，但是相对而言，插入相同数量的结点，红黑树的旋转次数是更少的，因为他对平衡的控制没那么严格。
总结：
-
查找
红黑树的性能稍逊一筹AVL树
因为他的高度控制没那么严格但都是logN量级。 -
插入
红黑树的性能要比AVL树好
虽然红黑树多了变色操作，但是变色操作简单，代价小。 并且红黑树高度控制没那么严格大量插入时旋转的调整次数比AVL树要少。所以插入是红黑树的性能更优秀。
二.红黑树的插入
2.1插入分析
- 插入⼀个值按⼆叉搜索树规则进行插入，插入后我们只需要观察是否符合红黑树的4条规则。
- 如果是空树插入，新增结点是黑色结点。如果是非空树插⼊，新增结点必须红色结点，因为非空树插入，新增黑色结点就破坏了规则4，规则4是很难维护的。
- 非空树插入后，新增结点必须红色结点，如果父亲结点是黑色的，则没有违反任何规则，插⼊结束
- 非空树插入后，新增结点必须红色结点，如果⽗亲结点是红⾊的，则违反规则3。进⼀步分析，c是红色，p为红，g必为黑，这三个颜色都固定了，关键的变化看u的情况，需要根据u分为以下几种情况分别处理。
说明：下图中假设我们把新增结点标识为c (cur)，c的父亲标识为p(parent)，p的父亲标识为g(grandfather)，p的兄弟标识为u（uncle）。
2.1变色
c为红，p为红，g为黑，u存在且为红，则将p和u变黑，g变红。在把g当做新的c，继续往上更新。
分析：因为p和u都是红色，g是黑色，把p和u变黑，左边子树路径各增加⼀个黑色结点，g再变红，相当于保持g所在子树的黑色结点的数量不变，同时解决了c和p连续红色结点的问题，需要继续往上更新是因为，g是红色，如果g的父亲还是红色，那么就还需要继续处理；如果g的父亲是黑色，则处理结束了；如果g就是整棵树的根，再把g变回黑色。
p是右子树也是一样的
所以p和cur在左还是在右我们并不关注。
只要u存在并且为红色我们都按照这种方式处理即可。
2.2 旋转+变色
如果u不存在或u存在为黑。
我们需要根据cur和p的位置分类讨论
- 单旋
c为红，p为红，g为黑，u不存在或者u存在且为黑，u不存在，则c⼀定是新增结点，u存在且为黑，则c⼀定不是新增，c之前是黑色的，是在c的子树中插入，，变色将c从黑色变成红色，更新上来的。
分析：p必须变黑色，才能解决，连续红色结点的问题，u不存在或者是黑色的，这里单纯的变色无法解决问题，需要旋转+变色。
如果p是左子树并cur是左子树
如果p是g的左，c是p的左，那么以g为旋转点进行右单旋，再把p变黑，g变红即可。p变成课这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为p的父亲是黑色还是红色或者空都不违反规则。
如果p是右子树并cur是右子树
如果p是g的右，c是p的右，那么以g为旋转点进行左单旋，再把p变黑，g变红即可。p变成课这颗树新的根，这样i树黑色结点的数量不变，没有连续的红结点了，且不需要往上更新，因为p的父亲是黑色还是红色或者空都不违反规则。
那就是以g进行左单旋 在把g变红 p变黑。
- 双旋
如果p是左子树cur是右子树
如果p是g的左，c是p的右，那么先以p为旋转点进行左单旋，再以g为旋转点进行右单旋，再把c变黑，g变红即可。c变成课这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为c的父亲是黑色还是红色或者空都不违反规则。
如果p是右子树cur是左子树
如果p是g的右，c是p的左，那么先以p为旋转点进行右单旋，再以g为旋转点进行左单旋，再把c变黑，g变红即可。c变成课这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为c的父亲是黑色还是红色或者空都不违反规则。
2.3 代码实现
bool Insert(const k& x, const v& v)
{
if (_root == nullptr)//插入根节点
{
_root = new node(x, v);
return true;
}
node* cur = _root;
node* parent = nullptr;//保留父亲节点
while (cur)
{
/*介质不冗余*/
if (x < cur->_key)
{
parent = cur;
cur = cur->left;
}
else if (x > cur->_key)
{
parent = cur;
cur = cur->right;
}
else
{
return false;
}
}
cur = new node(x, v);
cur->col = RED;
if (x > parent->_key)
{
parent->right = cur;
}
else//相等插入左子树
{
parent->left = cur;
}
cur->parent = parent;
while (parent&&parent->parent&&parent->col == RED)
{
node* grandfather = parent->parent;
if (parent == grandfather->left)
{
node* uncle = grandfather->right;
// g
// p u
// c c
//u存在且为红
if (uncle&&uncle->col==RED)
{
parent->col = uncle->col=BLACK;
grandfather->col = RED;
cur = grandfather;
parent = cur->parent;
}
//u不存在或存在为黑
else
{
// g
// p
// c
if (cur == parent->left)
{
RoRateR(grandfather);
parent->col = BLACK;
grandfather->col = RED;
}
// g
// p
// c
else
{
RoRateL(parent);
RoRateR(grandfather);
cur->col = BLACK;
grandfather->col = RED;
}
break;
}
}
else
{
node* uncle = grandfather->left;
// g
// u p
// c c
//u存在且为红
if (uncle && uncle->col == RED)
{
parent->col = uncle->col = BLACK;
grandfather->col = RED;
cur = grandfather;
parent = cur->parent;
}
//u不存在或存在为黑
else
{
// g
// p
// c
if (cur == parent->right)
{
RoRateL(grandfather);
parent->col = BLACK;
grandfather->col = RED;
}
// g
// p
// c
else
{
RoRateR(parent);
RoRateL(grandfather);
cur->col = BLACK;
grandfather->col = RED;
}
break;
}
}
}
_root->col = BLACK;//循环结束把根变黑
return true;
}
三.红黑树的查找
红黑树的查找和AVL树的规则一样。
对比根节点和目标值的大小再取左子树或右子树查找。
node* Find(const k& x)
{
node* ret = nullptr;
node* cur = _root;
while (cur)
{
if (x < cur->_key)
{
cur = cur->left;
}
else if (x > cur->_key)
{
cur = cur->right;
}
else
{
ret = cur;//保留当前节点
cur = cur->left;//继续向左子树查找中序的第一个
}
}
return ret;
}
四.红黑树的验证
4.1 思路分析
我们检查红黑树主要检查是否满足红黑树的规则即可。
4.2 代码实现
bool check(node* cur,size_t tmp,size_t sum)
{
if (cur == nullptr)
{
if (tmp != sum)
{
cout << "存在⿊⾊结点的数量不相等的路径" << endl;
return false;
}
return true;
}
if (cur->col == RED)
{
if (cur->parent->col == RED)
{
cout << cur->_key << ":" << "存在连续红节点" << endl;
return false;
}
}
else
{
sum++;
}
return check(cur->left, tmp, sum) && check(cur->right, tmp, sum);
}
bool ISRBTree()
{
return _ISRBTree(_root);
}
bool _ISRBTree(node* cur)
{
if (cur == nullptr)
{
return true;
}
if (cur->col == RED)
{
return false;
}
size_t t = 0;
while (cur)
{
if (cur->col == BLACK)
{
t++;
}
cur = cur->left;
}
return check(_root,t,0);
}
这里我们通过几组数据来看一下AVL树和红黑树的性能。
void Test()
{
const int N = 100000;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; i++)
{
v.push_back(rand() + i);
}
size_t begin2 = clock();
AVL::AVLTree<int, int> t;
for (auto e : v)
{
t.Insert(e, e);
}
size_t end2 = clock();
size_t begin3 = clock();
RBTree::RBTree<int, int> t1;
for (auto e : v)
{
t1.Insert(e, e);
}
size_t end3 = clock();
size_t begin1 = clock();
// 确定在的值
/*for (auto e : v)
{
t.Find(e);
}*/
// 随机值
for (size_t i = 0; i < N; i++)
{
t.Find((rand() + i));
}
size_t end1 = clock();
size_t begin4 = clock();
for (size_t i = 0; i < N; i++)
{
t1.Find((rand() + i));
}
size_t end4 = clock();
cout << "AVLInsert:" << end2 - begin2 << endl;
cout << "AVLTree:"<<t.IsBalanceTree() << endl;
cout << "AVLHeight:" << t.Height() << endl;
cout << "AVLSize:" << t.Size() << endl;
cout << "AVLFind:" << end1 - begin1 << endl;
cout << "RBInsert:" << end3 - begin3 << endl;
cout << "RBTree:" << t1.ISRBTree() << endl;
cout << "RBHeight:" << t1.Height() << endl;
cout << "RBSize:" << t1.Size() << endl;
cout << "RBFind:" << end4 - begin4 << endl;
}
- Debug
10万数据
100万数据
1000万数据
- Release
10万数据
100万数据
1000万数据
观察数据可以发现红黑树的查找比AVL要慢一些，
在release下查找效率都一样，因为CPU太快了。
但是红黑树在大量数据插入的情况下比AVL树要不少。
后言
这就是红黑树的深度剖析。大家自己好好消化！今天就分享到这！感谢各位的耐心垂阅！咱们下期见！拜拜~
