红黑树总结(RbTree)——C++版
目录
红黑树的五大规则
这些规则的作用
插入和删除中的规则修正(简单了解一下)
代码实现
单纯的变色
左旋+变色
右旋+变色
双旋+变色
其他细节
简单的数据测试
set/map进行封装
红黑树是一种自平衡的二叉搜索树，它通过一组规则来确保树在插入或删除操作后保持平衡。这些规则保证了红黑树的高度是 O(logn)，从而使得基本操作的时间复杂度也维持在O(logn)。以下是红黑树的基本规则：
红黑树的五大规则
-
节点要么是红色，要么是黑色：
- 这是红黑树的基础，红黑树中的每个节点都被涂上红色或黑色。
-
根节点是黑色：
- 根节点始终是黑色的。这一规则保证了红黑树在插入或删除操作时，从根节点开始的路径符合红黑树的性质。
-
所有叶子节点（NIL节点）是黑色的：
- 红黑树中的叶子节点实际上是指向
NIL（空节点）的指针，这些叶子节点在红黑树中都被视为黑色。这样做是为了在树的末端保持一致性。所以每个开头祖父结点到nullptr才算一条完整的路径。
- 红黑树中的叶子节点实际上是指向
-
红色节点的子节点必须是黑色（即红色节点不能有红色的子节点）：
- 这一规则限制了红色节点的连通性，避免了连续的红色节点，这样可以防止树的某些路径变得过长而导致不平衡。
-
从任意节点到其每个叶子节点的路径上都必须具有相同数量的黑色节点（称为黑色高度）：
- 黑色高度指的是从某一节点到其叶子节点的路径上，黑色节点的数量。这个规则保证了树的平衡性，因为在所有路径上的黑色节点数量相同，从而避免了树的某些分支比其他分支明显更深。
这些规则的作用
-
规则1和规则4: 通过颜色的约束，保证没有路径会比其他路径长出两倍，因此限制了树的高度，确保了树是“近似平衡”的。
-
规则2和规则3: 根节点为黑色和所有叶子节点为黑色，确保了树的基础结构的稳定性。
-
规则5: 保证了所有路径的黑色节点数量一致，这一性质非常关键，它确保了树的平衡性，不会有某一条路径比另一条长得太多。
插入和删除中的规则修正(简单了解一下)
在红黑树中，当进行插入或删除操作时，可能会违反上述规则。为了修正这些违规情况，红黑树会进行重新着色和旋转操作，以恢复平衡并满足所有规则。
-
插入修正: 插入一个新节点后，如果这个节点的父节点是红色的，那么可能会违反红黑树的规则。这时需要通过左旋、右旋以及重新着色来恢复规则的平衡。
-
删除修正: 删除一个节点可能会导致路径上的黑色节点数量不一致，这时通过一系列旋转和重新着色来修正。
这些规则和修正机制使得红黑树在进行插入和删除操作后，能够有效地保持自身的平衡性，从而确保其高效的查找、插入和删除操作。
代码实现
enum color
{
RED,
BLACK
};
笔记：因为红黑树只有两种颜色所以可以使用枚举类型color进行表示。
template<class K, class V>
struct RBTreeNode
{
pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
color _col;
RBTreeNode(const pair<K, V>& kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
{}
};
笔记：由于红黑树的本质还是搜索树，所以每个结点还是三叉链的形式即左右结点和父亲结点，用pair(K，V)模型记录每个结点存的数据形式。_col由于不知道要初始化成什么就不进行初始化了。
接着我们看Rbtree这个类，我们实现红黑树还是主要实现insert，还有一些比较次要的东西比如copy，find什么的。
插入结点还是和原本搜索树一样，由于红黑树的特殊规则，头节点必须是黑色的，每条路径的黑结点个数都是一样的，所以我们每次无论在那条路径新插入结点都必须是红色的，这样是为了不破坏当条路径的黑结点个数。
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;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
但是依照规则4红黑树的红色子节点必须是黑色吗，如果插入的是红色但是其父亲结点也是红色那怎么办呢，这就需要进行根据不同情况进行单纯变色，左旋，右旋，双旋了。
单纯的变色
请看下图：
首先要变色首先每个结点的颜色是我们首要关注的点，g肯定是黑色的，不然p就不可能再是红色的并且还能存在，cur为新插入的结点所以必须是红色的，那其实在考虑变色和是否需要旋转的时候就只需要考虑u的颜色和是不是存在了。
如上图，我们可以看到当u存在且为红色时只需要单纯的依上图完成变色就可以完成平衡了。
node* uncle = grandfather->_right;//由于p和u的位置是相对的，所以会额外有两种情况
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;//由于之前说g之前为黑色的，如果g不是头结点的话，需要接着向上调整
parent = cur->_parent;
}
/
node* uncle = grandfather->_left;
if (uncle->_col == RED)
{
uncle->_col = parent->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
下面展示自制的图(其实会自己画图出来就非常简单了)
左旋+变色
前面展示的是u为红色的情况，当u为黑色和为空的时候我们会发现单纯的变换颜色已经不管用了，因为这样会使得换完后有一边会多出一个黑色结点，所以就需要考虑旋转了。
旋转的规则和之前AVl树的规则一模一样的。
单旋转规则：如果cur插入在p的左边，这个时候单纯的左边高了，就以g为旋转轴往右旋，如果cur插入在p的右边，这个时候单纯的右边边高了，就以g为旋转轴往左旋。
变色规则：p变黑，g变红，这样左旋就旋转完成了，接着还是需要变色的，因为p注定是要变成黑色的，旋转完后，p变黑色，
由于p为黑色，这时g被旋到p的左边，会使得左边的黑色结点比右边多一个，所以将g变红色，这样一层红色一层黑色就合理了
if (cur == parent->_right)
{
//左旋
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
void RotateL(node* parent)
{
node* subr = parent->_right;
node* subrl = subr->_left;
parent->_right = subrl;
if (subrl)
{
subrl->_parent = parent;
}
node* parentP = parent->_parent;
subr->_left = parent;
parent->_parent = subr;
if (parentP == nullptr)
{
_root = subr;
subr->_parent = nullptr;
}
else
{
if (parentP->_left == parent)
{
parentP->_left = subr;
subr->_parent = parentP;
}
if (parentP->_right == parent)
{
parentP->_right = subr;
subr->_parent = parentP;
}
}
}
右旋+变色
由于左旋和右旋的逻辑差不多，所以就不做过多的解释了，详细的请看上面左旋的逻辑，还是那句话要学会画图！！！
if (cur == parent->_left)
{
//右旋
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
void RotateR(node* parent)
{
node* subL = parent->_left;
node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
node* grandfatherP = parent->_parent;//先存下来
subL->_right = parent;
parent->_parent = subL;
if (grandfatherP == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
subL->_parent = grandfatherP;//
if (parent == grandfatherP->_left)
{
grandfatherP->_left = subL;
}
if (parent == grandfatherP->_right)
{
grandfatherP->_right = subL;
}
}
}
双旋+变色
双旋又可以分为左右双旋和右左双旋，其逻辑和AVl树的双旋逻辑是完全一样的，其实也和单旋的逻辑完全一样(不证明了)就是在变色上和单旋上有区别。
else if (cur == parent->_left)
{
//右左双旋
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;//由于经过旋转这个树肯定趋于平衡的了所以可以直接break了(AVl树的理论)。
else if (cur == parent->_right)
{
//左右双旋
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
如上图可以看出由于先经过一个旋转使得变成单纯的一边高，此时cur结点变到了p的上面，所以第二次旋转之后，cur变成了头节点，p变成cur的左边或者右边，所以cur->_col=BLACK;grandfather->_col = RED，就这里和单旋不一样，需要注意。
其他细节
由于单纯的变色需要不断的向上调整，直到cur为根节点时停止，也就是说p结点为空时就停止，但是当p为黑时也没有继续循环的必要了，所以while循环的条件为：parent && parent->_col == RED
简单的数据测试
这里由于篇幅原因就简单的用一组数据进行测试：
int main()
{
Rbtree<int, int> sb;
int a[10] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto e : a)
{
if (e == 7)
{
cout << "fgg" << endl;
}
sb.Insert(make_pair(e, e));
}
sb.InOrder();
//cout << sb.Height();
return 0;
}
InOrder函数如下：
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private：
void _InOrder(node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
为什么将函数体部分放成私有呢，是为了不让外部成员访问，私有函数类里面也可以访问，起到包含代码的作用。
发现我们写的红黑树逻辑没什么问题！！！
set/map进行封装
欲知后事如何，请听下文介绍！！！
关注博主，解锁更多C++小知识！！！