| 高阶数据结构 | 相关知识点 | 可以通过点击 | 以下链接进行学习 | 一起加油！ |
|---|---|---|---|---|
| 二叉搜索树 | AVL树 |
大家好，我是店小二，欢迎来到本篇内容！今天我们将一起探索红黑树的工作原理及部分功能实现。红黑树的概念相对抽象，但只要我们一步步深入，定能慢慢揭开它的神秘面纱
🌈个人主页：是店小二呀
🌈C语言专栏：C语言
🌈C++专栏： C++
🌈初阶数据结构专栏： 初阶数据结构
🌈高阶数据结构专栏： 高阶数据结构
🌈Linux专栏： Linux
🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅
文章目录
一、红黑树概念
红黑树，是一种二叉搜索树，但在每个节点上增加一个存储位表示节点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。
红黑树的性质：
每个节点不是红色就是黑色
根节点是黑色的
如果一个节点是红色的，则它的两个孩子节点是黑色
对于每个节点，从该节点到其后代节点的简单路径上，均包含相同数目的黑色节点
每个叶子节点都是黑色的(此处的叶子节点指的是空节点)
满足上面的性质，红黑树就能保证:其最长路径中节点个数不会超过最短路径节点个数的两倍，但是不能保证满足这样的条件就是红黑树，具体还是往下看吧，这里重点关注的是规则3、4。
1.1 最短和最长路径
最短:全黑
最长:一黑一红
虽然有最短和最长路径，但是不一定存在最短或最长路径
具体说明:
- 对于红黑树满足最长路径中节点个数不会超过最短路径节点个数的两倍结论，是根据红黑树规则及其最短和最长路径得来的。
- 规则四:对于每个节点，从该节点到其后代节点的简单路径上，均包含相同数目的黑色节点。保证了每条路径黑色节点数量相同的。如果我们想要延长某一条路径，插入黑色节点不能达成目的，对此我们需要插入红色节点，碍于规则三:如果一个节点是红色的，则它的两个孩子节点是黑色的限制，对此只能在两个黑色节点之间插入一个红色节点或者在最后黑色节点插入一个红色节点。导致了最短为全黑，最长一黑一红，大致形成两倍的关系，但是不一定存在最短或最长路径(路径相同)。
- 红黑树的平衡维护在这微妙的关系中，如果不能保证其最长路径中节点个数不会超过最短路径节点个数的两倍就是不是红黑树，就是能保证也不一定是红黑树，不充分必要条件
- 使用枚举常量代替红色和黑色的含义。就是跟全部黑色节点或者全部黑色节点配合红色节点
二、红黑树的节点部分
enum Color
{
RED, BLACK
};
template<class K, class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _parent;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
pair<K, V> _kv;
Color _color;
RBTreeNode(const pair<K, V>& kv)
:_parent(nullptr)
,_left(nullptr)
,_right(nullptr)
,_kv(kv)
,_color(RED)
{}
};
三、关于红黑树的插入
节点的插入无非两种颜色，要么红色要么黑色。如果使用严母慈父来说规则3、4的严格程度，规则3是慈父，规则4是严母。如果插入节点为黑色，必然会违法规则4，每条都会收到影响;如果插入的节点为红色，可能会违法规则3(存在连续的两个红色节点)
这样子不管插入啥颜色都会违法规则，如果一定要插入优选红色节点(慈父身份)，接下来让我们来看，如果处理插入为红色节点，出现连续红色的问题吧。
3.1 对某个红黑树进行分析(难点)
前文(主要是给自己看，不懂可以评论区见)
关于这一点还是挺晕的，以下是我的看法：
- 出现问题情况就是发生在cur和parent为红色情况下，至于为什么是在cur和parent为红色情况下。我们进行红黑树插入节点到红黑树调整结构，都是从下到上的。要么parent是黑的，cur是红的，插入没有问题；要么parent是红的，cur是黑的，插入违法规则四，不如违法规则三。所以就需要考虑cur和parent是红色的就行。
- 既然cur和parent及其grandfather颜色是确定，问题在于uncle颜色上，所以我们分出了很多种情况，去特殊处理。
- 规则四只是保证每条路径黑色节点数量相同，没有保证在同一层，对此在调整过程中，u就是未知的颜色，u是黑色还是不存在，我们需要根据规则去还源之前的场景，是第一种情况基础上打造了第二种情况合并为一整棵红黑树，这也是属于众多红黑树的部分。将这些特殊红黑树处理好，面对不同场景，特殊进行处理。
- 也就是说，也是整棵红黑树的一部分
正文
这里我们可以确定c\p\g颜色是确定的，关键在于u颜色是不确定，从而影响整棵树的平衡
这里将情况分为两种：
情况一:cur为红，p为红，g为黑，u存在且为红
情况二:cur为红，p为红，g为黑，u不存在/u存在且为黑
情况一
处理办法:将p、u改为黑，g改为红。具体流程在图中(将cur赋值给g)
关于红黑树分析将采取抽象图进行分析，其实这里也可以看出具体图。还是以小部分组成为大部分的思想，可以根据下图理解这个思想，就是这个结构在上面重演了。
如果在一颗高度很高红黑树中，我们可以看见红黑树在调整过程中会不断重复熟悉的场景，所以抽象图中的具体部分就被包含在其中。
第二种情况
对于这两种情况，就是在变色过程中，违法了规则四(严母)。如果p变色了u还是黑色或者不存在，会导致每条路径上的黑色节点个数不相等，对此跟插入黑色节点一样。
接下来，需要建立在这两张图进行说明，不然很容易晕的（重点）
- 如果u节点不存在，则cur一定是新节点。假设u节点存在，颜色为黑色，cur和p为了维护规则四，要么cur是黑色，后面跟着两个红色节点，要么p是黑色，规则四成立。然后将u节点拿出去，cur如果不是新节点，一切全部不成立，规则四直接违法。
- 如果u节点存在，则其一定是黑色的，那么cur节点原来的颜色一定黑色，为了遵守规则四。现在看到其是红色的原因是由于cur子树在调整的过程中将cur节点的颜色由黑色改为红色。
上面两种情况是根据u变量无法确认是红色还是黑色，导致影响不同。
在第二种情况的基础上，还有一个小问题就是连续红色节点不是一边独红，需要先旋转进行处理，调整到一边连续红色节点。
这里将根据思路和不同功能罗列代码了，这里旋转后的节点的颜色需要自己根据图单独进行处理的。红黑树也是属于二叉搜索树，对此我们这里可以CV下代码。
右旋代码
void RotateR(Node* parent)
{
Node* SubL = parent->_left;
Node* SubLR = SubL->_right;
parent->_left = SubLR;
if (SubLR)
SubLR->_parent = parent;
SubL->_right = parent;
Node* ppNode = parent->_parent;
parent->_parent = SubL;
if (parent == _root)
{
SubL = _root;
SubL->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = SubL;
}
else if (ppNode->_right == parent)
{
ppNode->_right = SubL;
}
SubL->_parant = ppNode;
}
}
左旋代码
void RotateL(Node* parent)
{
Node* SubR = parent->_right;
Node* SubRL = SubR->_left;
parent->_right = SubRL;
if (SubRL)
SubR->_parent = parent;
SubR->_left = parent;
Node* ppNode = parent->_parent;
parent->_parent = SubR;
if (parent == _root)
{
SubR = _root;
SubR->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = SubR;
}
else if (ppNode->_right == parent)
{
ppNode->_right = SubR;
}
SubR->_parant = ppNode;
}
}
3.2 红黑树插入逻辑(重点)
typedef RBTreeNode<K, V> Node;
public:
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
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
{
assert(!cur);
}
}
//需要将这个节点连接起来
cur = new Node(kv);
cur->_color = RED;
cur->_parent = parent;
if (parent->kv.first > cur->_kv.first)
{
parent->_left = cur;
}
else if (parent->kv.first < cur->_kv.first)
{
parent->_right = cur;
}
//根据不同情况就行调整,父亲节点是黑色就是走到根了
while (parent && parent->_color == RED)
{
Node* grandfather = parent->_parent;
//这里默认插入都是红色，这里需要进行调整
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
if (uncle && uncle == RED)
{
parent->_color = uncle->_color = BLACK;
grandfather = RED;
cur = grandfather;
parent = cur->_parent;
}
//uncle不存在或者为黑色，需要旋转
else
{
if (cur = parent->_left)//一边红的情况
{
RotateR(grandfather);
parent->_color = BLACK;
grandfather->_color = RED;
}
else
{
RotateL(parent);
RotateR(grandfather);
cur = BLACK;
parent->_color = grandfather->_color = RED;
}
}
}
else
{
// 情况二：叔叔不存在或者存在且为黑
// 旋转+变色
// g
// u p
// c
if (cur == parent->_right)//一边红的情况
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
//不管根是什么颜色，都修改一遍为黑色
_root->_col = BLACK;
return true;
}
四、遍历红黑树
如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
void InOder()
{
_InOder(_root);
cout << endl;
}
private:
void _InOder(Node* _root)
{
_InOder(_root->_left);
cout << endl;
_InOder(_root->_right);
}
这里将中序遍历实现逻辑封装到私有成员函数中隐藏它的具体实现细节，使得外部用户无法直接访问该函数，提高了代码的安全性和可维护性，符合面向对象编程的封装性原则。这里外部访问中序遍历接口，只是传递了节点指针的副本，而不修改任何节指针的实际值。
五、判断是否满足红黑树
可以根据红黑树的规则来进行判断，具体细节在代码块注释。其中规则四就是判断每条路径的黑色节点个数是否相同，那么可以提前记录好一条路径的黑色节点个数去比较，当_root == nullptr说明这条路径遍历完毕，需要就行判断
bool IsBalance()
{
//规则一:根节点颜色为黑色
if (_root->_color == RED)
{
return false;
}
int refNum = 0;
//记录单独一边黑色节点个数
Node* cur = _root;
while (cur)
{
refNum++;
cur = cur->_left;
}
return Check(_root, 0, refNum);
}
private:
bool Check(Node* root, int blackNum, const int refNum)
{
//接下就是遍历每条路径了
if (_root == nullptr)
{
//规则4
if (blackNum != refNum)
{
cout << "不满足每条路径相同黑色节点" << endl;
return false;
}
return true;
}
//规则3
if (root->_col == RED && root->_parent->_col == RED)
{
cout << root->_kv.first << "存在连续的红色节点" << endl;
return false;
}
//记录每条路径的黑色节点
//可行的原因是该blackNum传递形参
//每个节点记录一个值:根到当前节点路径中黑色节点的数量
if (root->_col == BLACK)
{
blackNum++;
}
return Check(root->_left , blackNum,refNum) && Check(root->_right, blackNum, refNum)
}
关于规则3这里判断逻辑设计，是根找父亲，而不是根找儿子。如果是根找儿子，需要去左右孩子去找又分为多种情况，不然选择一条单一的路线，根找父亲，反正都是遍历每个节点。
问题:
- 为什么不能通过其最长路径中节点个数不会超过最短路径节点个数的两倍来判断是否为红黑树呢？
答:
- 这里是不充分必要条件，比如下图12左边这条路径不满足规则4，当插入时就会出现问题。(路径是指某条路径空节点到根节点)
六、红黑树的删除
红黑树的删除本节不做讲解，有兴趣的可参考：《算法导论》或者《STL源码剖析》。以下提供相关链接:红黑树删除
七、红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(logn)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多
八、RBTree.h
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
enum Color
{
RED, BLACK
};
template<class K, class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _parent;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
pair<K, V> _kv;
Color _color;
RBTreeNode(const pair<K, V>& kv)
:_parent(nullptr)
, _left(nullptr)
, _right(nullptr)
, _kv(kv)
, _color(RED)
{}
};
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
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
{
assert(!cur);
}
}
//需要将这个节点连接起来
cur = new Node(kv);
cur->_color = RED;
cur->_parent = parent;
if (parent->kv.first > cur->_kv.first)
{
parent->_left = cur;
}
else if (parent->kv.first < cur->_kv.first)
{
parent->_right = cur;
}
//根据不同情况就行调整,父亲节点是黑色就是走到根了
while (parent && parent->_color == RED)
{
Node* grandfather = parent->_parent;
//这里默认插入都是红色，这里需要进行调整
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
if (uncle && uncle == RED)
{
parent->_color = uncle->_color = BLACK;
grandfather = RED;
cur = grandfather;
parent = cur->_parent;
}
//uncle不存在或者为黑色，需要旋转
else
{
if (cur = parent->_left)
{
RotateR(grandfather);
parent->_color = BLACK;
grandfather->_color = RED;
}
else
{
RotateL(parent);
RotateR(grandfather);
cur = BLACK;
parent->_color = grandfather->_color = RED;
}
}
}
else
{
// 情况二：叔叔不存在或者存在且为黑
// 旋转+变色
// g
// u p
// c
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
void RotateR(Node* parent)
{
Node* SubL = parent->_left;
Node* SubLR = SubL->_right;
parent->_left = SubLR;
if (SubLR)
SubLR->_parent = parent;
SubL->_right = parent;
Node* ppNode = parent->_parent;
parent->_parent = SubL;
if (parent == _root)
{
SubL = _root;
SubL->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = SubL;
}
else if (ppNode->_right == parent)
{
ppNode->_right = SubL;
}
SubL->_parant = ppNode;
}
}
void RotateL(Node* parent)
{
Node* SubR = parent->_right;
Node* SubRL = SubR->_left;
parent->_right = SubRL;
if (SubRL)
SubR->_parent = parent;
SubR->_left = parent;
Node* ppNode = parent->_parent;
parent->_parent = SubR;
if (parent == _root)
{
SubR = _root;
SubR->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = SubR;
}
else if (ppNode->_right == parent)
{
ppNode->_right = SubR;
}
SubR->_parant = ppNode;
}
}
bool IsBalance()
{
if (_root->_color == RED)
{
return false;
}
int refNum = 0;
//记录单独一边黑色节点个数
Node* cur = _root;
while (cur)
{
refNum++;
cur = cur->_left;
}
return Check(_root, 0, refNum);
}
void InOder()
{
_InOder(_root);
cout << endl;
}
private:
bool Check(Node* root, int blackNum, const int refNum)
{
//接下就是遍历每条路径了
if (_root == nullptr)
{
if (blackNum != refNum)
{
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)
}
void _InOder(Node* _root)
{
_InOder(_root->_left);
cout << endl;
_InOder(_root->_right);
}
private:
Node* _root = nullptr;
};
感谢大家的观看！以上就是本篇文章的全部内容。我是店小二，希望这些高阶数据结构笔记能为你在学习旅途中提供帮助！