【C++】从零开始构建红黑树
1 🖤红黑树
红黑树是一种特殊的二叉树，它遵循一套独特的规则：
- ⚠️每个节点要么是红色，要么是黑色。
- ⚠️根节点必须是黑色的。
- ⚠️如果一个节点是红色的，则它的两个子节点必须是黑色的。
- ⚠️对于任意一个节点，从该节点到其所有后代叶子节点的简单路径上，必须包含相同数目的黑色节点。
- ⚠️每个叶子节点都是黑色的。这里的叶子节点指的是为空的节点。
❗注意 ❗：红黑树的规则并不要求红黑节点严格交替出现。黑色节点可以连续，但红色节点不能连续。这是规则的设定。
通过这些规则，红黑树可以保持接近平衡的状态。虽然它不像AVL树那样可以维持严格的平衡状态，但是它可以保证搜索的效率。需要记住的是：红黑树每条路径（从根节点到空节点）上的黑色节点数量相同。
红黑树的应用场景十分广泛，其中之一是在很多高性能的C++ STL库中被广泛采用，比如map和set。这是因为红黑树具有平衡性能较好的特性，能够保持树的高度较低，从而保证了在插入、删除和查找操作上的较高效率。除此之外，它还常用于实现范围查询和有序遍历等功能。 之后我们将来实现map与set的封装！！！
红黑树的平衡性质使其在数据库系统中也得到了广泛的应用，特别是在实现索引结构时。在数据库系统中，红黑树可以用于实现基于范围的查询，如在B+树的实现中，通常使用红黑树来维护叶子节点的有序性。
2 🖤红黑树的模拟实现
✅了解了红黑树的定义与规则，接下来我们就来实现红黑树✅
2.1 ❤️红黑树的节点设计
红黑树的节点设计基于二叉搜索树的节点增加了一个表示颜色的变量，用来标识该节点的颜色;
//枚举变量来定义颜色
enum color
{
Black,
Red
};
// 节点结构体
template<class K , class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
pair<K, V> _kv;
color _col;
RBTreeNode(pair<K , V> kv)
:_left(nullptr),
_right(nullptr),
_parent(nullptr),
_kv(kv),
_col(Red)
{}
};我们按照三叉结构来构建节点，方便进行后续操作（寻找父节点，寻找爷爷节点）。键值对来储存key和key 值对应的value值，_col来储存颜色，默认创建的节点是红色。
2.2 ❤️红黑树的插入函数
🎄 整体框架
现在我们来进行红黑树核心函数的实现，在这个插入函数中，会深刻体会到红黑树的抽象程度，也会大大加强代码能力！！！
首先依旧是最常规的操作：寻找插入位置：
//插入函数
void Insert( pair<K , V> kv)
{
//如果根节点为空
if (_root == nullptr)
{
Node* node = new Node(kv);
node->_col = Black;
_root = node;
return;
}
//不是根节点 就找到合适位置进行插入
else
{
Node* cur = _root;
Node* parent = nullptr;
while (cur != nullptr)
{
parent = cur;
if (kv.first < cur->_kv.first)
{
cur = cur->_left;
}
else
{
cur = cur->_right;
}
}
//找到位置进行插入
}寻找到合适的位置可以进行插入了，这里要进行一个思考：新插入的节点是什么颜色？？？
红色还是黑色？？？我们来分类讨论一下：
- 新插入黑色节点：如果我们新插入一个黑色节点，那么毋庸置疑会违反规则4 ：
对于任意一个节点，从该节点到其所有后代叶子节点的简单路径上，必须包含相同数目的黑色节点。这个是红黑树最为关键的规则，插入一个黑色节点，红黑树立刻就不是红黑树了！！！ - 新插入红色节点：如果我们新插入一个红色节点，那么规则4肯定是不会违反的了，但是规则3
如果一个节点是红色的，则它的两个子节点必须是黑色的。是有可能违反的：- 如果父节点是黑色，插入一个红色节点刚刚好，没有破坏红黑树的规则！！！
- 如果父节点是红色，插入一个红色节点就违反了规则3。
这么一看，还是插入红色节点比较好，因为插入黑色节点一定破坏原本的红黑树结构，插入红色节点不一定会破坏红黑树结构！！！
所以新节点的颜色我们设置为红色。
插入一个新的节点之后，我们就要进行调整了：
- 如果父节点是黑色，插入一个红色节点刚刚好，没有破坏红黑树的规则！！！
- 如果父节点是红色，插入一个红色节点就违反了规则3。
我们只需要对父节点是红色进行处理了，为了保证满足规则4:对于任意一个节点，从该节点到其所有后代叶子节点的简单路径上，必须包含相同数目的黑色节点。我们需要对叔叔节点进行分类讨论：
- 如果叔叔节点是红色，那么说明爷爷节点的两个子树中黑色节点个数一致，此时只需要进行变色处理。 父节点和叔叔节点都变成黑色，爷爷节点变成红色，然后继续向上进行（爷爷节点变成红色，类似“插入了一个红色节点”）。直到根节点结束（最后根节点还要变回黑色，此时相当于全体增加了一个黑色节点）
- 如果叔叔节点是黑色，那么说明爷爷节点的两个子树中黑色节点个数不一致，单纯依靠变色是不能达到要求的，这时候就要进行旋转。 此时旋转的本质是将树的高度变低，再通过变色使其两边的黑色节点个数一致。但是无论如何，黑色节点的增加只可以再根节点进行！
所以我们先把处理的逻辑写好，稍后再来写旋转：
//插入函数
void Insert( pair<K , V> kv)
{
//如果根节点为空
if (_root == nullptr)
{
Node* node = new Node(kv);
node->_col = Black;
_root = node;
return;
}
//不是根节点 就找到合适位置进行插入
else
{
Node* cur = _root;
Node* parent = nullptr;
while (cur != nullptr)
{
parent = cur;
if (kv.first < cur->_kv.first)
{
cur = cur->_left;
}
else
{
cur = cur->_right;
}
}
//找到位置进行插入
Node* node = new Node(kv);
//新节点的颜色默认为红色
//不要违反规则4 规则4很严厉
node->_col = Red;
if (kv.first < parent->_kv.first)
{
parent->_left = node;
node->_parent = parent;
}
else
{
parent->_right= node;
node->_parent = parent;
}
cur = node;
//开始进行判断
//调整红黑树的平衡 -- 父节点如果为黑色就不需要调整
//注意父节点要存在才可以！！！
while (parent && parent->_col == Red && parent->_parent)
{
//爷爷节点
Node* grandfather = parent->_parent;
//根据父节点与爷爷节点的关系进行分类
if (parent == grandfather->_left)
{
//叔叔节点是关键
Node* uncle = grandfather->_right;
//如果叔叔也为红色，只需要一同变色处理即可
if (uncle && uncle->_col == Red)
{
parent->_col = uncle->_col = Black;
grandfather->_col = Red;
//继续向上处理
cur = grandfather;
parent = cur->_parent;
}
//如果叔叔不存在 / 叔叔为黑色 ， 此时需要旋转
else
{
//这里需要旋转
//旋转之后不可能再出现连续两个红色节点
//直接break
break;
}
}
//parent == grandfather->_right
//一样的道理
else
{
//叔叔节点是关键
Node* uncle = grandfather->_left;
//如果叔叔也为红色，只需要一同变色处理即可
if (uncle && uncle->_col == Red)
{
parent->_col = uncle->_col = Black;
grandfather->_col = Red;
//继续向上处理
cur = grandfather;
parent = cur->_parent;
}
//如果叔叔不存在 / 叔叔为黑色 ， 此时需要旋转
else
{
//这里需要旋转
//旋转之后不可能再出现连续两个红色节点
//直接break
break;
}
}
}
//无论如何根节点都是黑色的！
_root->_col = Black;
}
}🎄 旋转处理
旋转的可以参考从零开始构建AVL树！ 这里我们简单讲解一下右单旋：
右单旋的情况是：父节点是红色，叔叔节点是黑色 , 插入的位置是父节点的左边。这是就要对爷爷节点进行右单旋。
右单旋很简单：
- 先记录
subL subLR parent节点，方便后续操作 - 右单旋是将
parent变为subL的右节点，subLR变为parent的左节点。 - 注意还要处理
_parent指针哦!
旋转后还要进行颜色的处理，我们看图进行处理即可：grandfather变为红色，parent 变为黑色
//右单旋
void RotateR(Node* parent)
{
//进行旋转
Node* SubL = parent->_left;
Node* SubLR = SubL->_right;
Node* pparent = parent->_parent;
SubL->_right = parent;
parent->_parent = SubL;
parent->_left = SubLR;
if (SubLR != nullptr)
SubLR->_parent = parent;
//处理爷爷节点
if (parent == _root)
{
_root = SubL;
SubL->_parent = nullptr;
}
else
{
//保证指向正确
SubL->_parent = pparent;
if (parent == pparent->_left)
{
pparent->_left = SubL;
}
else
{
pparent->_right = SubL;
}
}
}左单旋是一样的道理，看图：
接下来我们来看双旋的情况，左右双旋如图：
可以看到经过旋转变色处理，每个子树的黑色节点个数依然一致。
//左右双旋
void RotateLR(Node* parent)
{
//直接化用右单旋 左单旋
Node* SubL = parent->_left;
//先对SubL 进行左单旋 使其方向一致
RotateL(SubL);
//在对parent进行右单旋
RotateR(parent);
//不需要调整平衡因子
}右左双旋套路一样！
这样我们就写好了我们的插入函数
🎄 完成插入函数
//插入函数
void Insert( pair<K , V> kv)
{
//如果根节点为空
if (_root == nullptr)
{
Node* node = new Node(kv);
node->_col = Black;
_root = node;
return;
}
//不是根节点 就找到合适位置进行插入
else
{
Node* cur = _root;
Node* parent = nullptr;
while (cur != nullptr)
{
parent = cur;
if (kv.first < cur->_kv.first)
{
cur = cur->_left;
}
else
{
cur = cur->_right;
}
}
//找到位置
//进行插入
Node* node = new Node(kv);
//新节点的颜色默认为红色
//不要违反规则4 规则4很严厉
node->_col = Red;
if (kv.first < parent->_kv.first)
{
parent->_left = node;
node->_parent = parent;
}
else
{
parent->_right= node;
node->_parent = parent;
}
cur = node;
//开始进行判断
//调整红黑树的平衡 -- 父节点如果为黑色就不需要调整
while (parent && parent->_col == Red && parent->_parent)
{
//爷爷节点
Node* grandfather = parent->_parent;
//根据父节点与爷爷节点的关系进行分类
if (parent == grandfather->_left)
{
//叔叔节点是关键
Node* uncle = grandfather->_right;
//如果叔叔也为红色，只需要一同变色处理即可
if (uncle && uncle->_col == Red)
{
parent->_col = uncle->_col = Black;
grandfather->_col = Red;
//继续向上处理
cur = grandfather;
parent = cur->_parent;
}
//如果叔叔不存在 / 叔叔为黑色 ， 此时需要旋转
else
{
if (cur == parent->_left)
{
//此时进行右单旋
RotateR(grandfather);
//旋转完成需要进行变色
parent->_col = Black;
grandfather->_col = Red;
}
else
{
//此时进行左右双旋
RotateLR(grandfather);
grandfather->_col = Red;
cur->_col = Black;
}
//旋转之后不可能再出现连续两个红色节点
//直接break
break;
}
}
//parent == grandfather->_right
//一样的道理
else
{
//叔叔节点是关键
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)
{
//此时进行左单旋
RotateL(grandfather);
parent->_col = Black;
grandfather->_col = Red;
}
else
{
//此时进行右左双旋
RotateRL(grandfather);
grandfather->_col = Red;
cur->_col = Black;
}
//旋转之后不可能再出现连续两个红色节点
//直接break
break;
}
}
}
//无论如何根节点都是黑色的！
_root->_col = Black;
}
}2.3 ❤️ 红黑树的测试
我们什么大写特写一顿，是时候来检验一下我们写的红黑数是否满足条件了。 测验的方法就是检查每一条路径的黑色节点个数是否一致。对于这样二叉树的遍历处理，我们很自然的就可以想到DFS深度优先算法。直接暴力遍历一般就好了： 下面是测试一：
void IsBalance()
{
//dfs检查每一条路径的黑色节点个数
int num = 0;
_IsBalance(_root, num);
}
void _IsBalance(Node* root , int num)
{
if (root == nullptr)
{
cout << "黑色节点个数->" << num << endl;
}
else
{
_IsBalance(root->_left, root->_col == Red ? num : num + 1);
_IsBalance(root->_right, root->_col == Red ? num : num + 1);
}
}我来来运行看看：
可以看到我们使用一个小数组进行的检查是没有问题的，那么接下来我们来一千万个数据来检查一下，我们的检查函数也要进行调整： 测试二
bool IsBalance()
{
if (_root->_col == Red)
{
return false;
}
int refNum = 0;
//计算一个参考值
Node* cur = _root;
while (cur)
{
if (cur->_col == Black)
{
++refNum;
}
cur = cur->_left;
}
//检查每个路径的黑色节点个数是否一致
return Check(_root, 0, refNum);
}
bool Check(Node* root, int blackNum, const int refNum)
{
if (root == nullptr)
{
//cout << blackNum << endl;
if (refNum != blackNum)
{
cout << "存在黑色节点的数量不相等的路径" << endl;
return false;
}
return true;
}
if (root->_col == Red && root->_parent->_col == Red)
{
cout << root->_kv.first << "存在连续的红色节点" << endl;
return false;
}
if (root->_col == Black)
{
blackNum++;
}
return Check(root->_left, blackNum, refNum)
&& Check(root->_right, blackNum, refNum);
}这样就可以来进行大数据的检查哩：
一千万的数据我们进行检查后依然是满足红黑树的规则！！！ nice!!!
这样我们就完成了红黑树的构建！！！ 😎😎😎😎😎😎😎
Thanks♪(･ω･)ﾉ谢谢阅读！！！
下一篇文章见！！！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-05-26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录