注：本文的是在理解AVL树的基础上进行讲解的！
1. 红黑树的概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
2. 红黑树的性质
1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？
- 红黑树中的性质确保了任意路径上的黑色节点数量相等，这是红黑树能够保持平衡的关键。根据这个性质，我们可以证明红黑树的最长路径中的节点个数不会超过最短路径的节点个数的两倍。
- 假设红黑树的最短路径上的黑色节点数量为k。由于性质5，任意路径上的黑色节点数量相等，所以最长路径上的黑色节点数量不能少于k个。
- 现在我们来看最长路径上的节点个数。由于性质4，红色节点的两个子节点都是黑色的，因此最长路径上不能有连续的红色节点。而对于红黑树而言，最长路径上的红色节点数量最多为k，因为最长路径上的黑色节点数量不能少于k个。所以最长路径上的节点个数最多为2k，其中k个是黑色节点，k个是红色节点。
- 综上所述，红黑树的最长路径中的节点个数不会超过最短路径的节点个数的两倍，即最长路径上的节点个数最多为2k，其中k为最短路径上的黑色节点数量。
- 这个性质保证了红黑树的高度始终保持在较小的范围内，从而保持了树的平衡性。因为红黑树的高度与最长路径上的节点个数成正比，所以最长路径的节点个数的上限为最短路径的节点个数的两倍，确保了红黑树的平衡性和高效性。
3. 红黑树节点的定义
template<class K, class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
pair<K, V> _kv;
Colour _col;
int _bf;
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr)//左孩子
, _right(nullptr)//右孩子
, _parent(nullptr)//父亲
, _kv(kv)//存储键值对的成员变量
, _col(RED)//默认红色
{}
};
具体解释如下：
4. 红黑树结构
为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为根节点必须为黑色，为了与根节点进行区分，将头结点给成黑色，并且让头结点的 pParent 域指向红黑树的根节点，pLeft域指向红黑树中最小的节点，_pRight域指向红黑树中最大的节点。
如下：
5. 红黑树的插入操作
红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：
5.1 按照二叉搜索的树规则插入新节点
#pragma once
#include <iostream>
using namespace std;
//枚举类型变量
enum Colour
{
RED, //红
BLACK //黑
};
template<class K, class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
pair<K, V> _kv;
Colour _col;
int _bf;
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(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);
_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;
}
红黑树开整
//1.cur为红，parent为红，grandfather为黑，uncle存在且为红
//解决方法：p,u变成黑，g变成红，c=g，继续向上调整
//2.cur为红，parent为红，grandfather为黑,uncle不存在 or 存在且为黑
//解决方法: 单旋：p变红，g变黑，//双旋：c变黑，g变红
private:
Node* _root = nullptr;
};
5.2 检测新节点插入后，红黑树的性质是否造到破坏
因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：
约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点
5.2.1 情况一: cur为红，p为红，g为黑，u存在且为红
解决方法：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。
5.2.2 情况二: cur为红（此时只需要单旋），p为红，g为黑，u不存在/u存在且为黑
解决方法：
p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，
p为g的右孩子，cur为p的右孩子，则进行左单旋转
p、g变色–p变黑，g变红
5.2.3 情况三: cur为红（此时需要进行双旋变成情况二），p为红，g为黑，u不存在/u存在且为黑
解决方法：
完整代码
#pragma once
#include <iostream>
using namespace std;
//枚举类型变量
enum Colour
{
RED, //红
BLACK //黑
};
template<class K, class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
pair<K, V> _kv;
Colour _col;
int _bf;
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(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);
_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;
}
红黑树开整
//1.cur为红，parent为红，grandfather为黑，uncle存在且为红
//解决方法：p,u变成黑，g变成红，c=g，继续向上调整
//2.cur为红，parent为红，grandfather为黑,uncle不存在 or 存在且为黑
//解决方法: 单旋：p变红，g变黑，//双旋：c变黑，g变红
//parent不为空，且parent->_col==RED（这样保证肯定有祖先，也就是grandfather不为空）
while (parent && parent->_col == RED)
{
// g
// p u
//c
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
// g
// p u
//c
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续往上更新处理
cur = grandfather;
parent = cur->_parent;//这儿parent更新完之后可能为空，为空就结束
}
else//uncle不存在 or 存在且为黑
{ //单旋
// g
// p u
//c
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;//p变黑
grandfather->_col = RED;//g变红
}
else if (cur == parent->_right)
{
//双旋
// g
// p u
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
// g
// u p
// c
else// parent == grandfather->_left
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续往上更新处理
cur = grandfather;
parent = cur->_parent;
}
else//(uncle不存在 or 存在且为黑)
{ //单旋
// g
// u p
// c
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;//p变黑
grandfather->_col = RED;//g变红
}
else//cur == parent->_left
{
//双旋
// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
//管你根节点更新成啥了，管你个求，直接把_root->_col改成黑色
_root->_col = BLACK;
return true;
}
//左单旋
//（1.父亲节点的右边等于右孩子的左边; 2.右孩子的左边等于父亲节点）
//【把右孩子的左边给给父亲节点的右边; 2.再把父亲节点给给右孩子的左边】
void RotateL(Node* parent)
{
Node* SubR = parent->_right;
Node* SubRL = SubR->_left;
//旋转链接
parent->_right = SubRL;
SubR->_left = parent;
Node* Parent_Parent = parent->_parent;
parent->_parent = SubR;
if (SubRL)
{
SubRL->_parent = parent;
}
//和父节点的父节点链接
if (_root == parent)
{
_root = SubR;
SubR->_parent = nullptr;
}
else
{
if (Parent_Parent->_left == parent)
{
Parent_Parent->_left = SubR;
}
else
{
Parent_Parent->_right = SubR;
}
SubR->_parent = Parent_Parent;
}
}
//右单旋
void RotateR(Node* parent)
{
Node* SubL = parent->_left;
Node* SubLR = SubL->_right;
//旋转链接
//动一个节点就把他的父亲也变动
parent->_left = SubLR;
if (SubLR)//SubLR可能为空
{
SubLR->_parent = parent;
}
Node* Parent_Parent = parent->_parent;
SubL->_right = parent;
parent->_parent = SubL;
//和父节点的父节点链接
if (_root == parent)
{
_root = SubL;
SubL->_parent = nullptr;
}
else
{
if (Parent_Parent->_left == parent)
{
Parent_Parent->_left = SubL;
}
else
{
Parent_Parent->_right = SubL;
}
SubL->_parent = Parent_Parent;//链接
}
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
//根节点到当前这条路径的黑色节点个数
bool Check(Node *root,int blacknum,const int RefVal)
{
if (root == nullptr)
{
if (blacknum != RefVal)
{
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 blacknum = 0;//记录每条路径的黑色节点个数
int RefVal = 0;//定一个标准
Node* cur = _root;
while (cur)//改了一个bug ，之前这儿脑子抽抽了，写成了if
{
if (cur->_col == BLACK)
{
++RefVal;
}
cur = cur->_left;
}
return Check(_root, blacknum,RefVal);
}
private:
Node* _root = nullptr;
};
6. 红黑树的验证
红黑树的检测分为两步：
1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
#include <vector>
#include "RBTree.h"
int main()
{
int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
RBTree<int, int> a;
for (auto e : arr)
{
a.insert(make_pair(e, e));
}
a.InOrder();
return 0;
}
2. 检测其是否满足红黑树的性质
我们可以通过递归地遍历红黑树的节点，并统计根节点到每个叶子节点路径上的黑色节点个数来进行检查。
//根节点到当前这条路径的黑色节点个数
bool Check(Node *root,int blacknum,const int RefVal)
{
if (root == nullptr)
{
if (blacknum != RefVal)
{
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 blacknum = 0;//记录每条路径的黑色节点个数
int RefVal = 0;//定一个标准
Node* cur = _root;
while (cur)//改了一个bug ，之前这儿脑子抽抽了，写成了if
{
if (cur->_col == BLACK)
{
++RefVal;
}
cur = cur->_left;
}
return Check(_root, blacknum,RefVal);
}
函数讲解
Check 函数是一个递归函数，用于检查从当前节点到叶子节点的路径上的黑色节点个数是否与参考值 RefVal 相等。参数 root 表示当前节点指针，blacknum 表示根节点到当前节点的路径上的黑色节点个数，RefVal 是参考值。
IsBalance 函数用于检查整个红黑树是否符合红黑树的性质。
#include <vector>
#include "RBTree.h"
int main()
{
const int N = 30;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; i++)
{
v.push_back(rand()%100 );
}
RBTree<int, int> t;
for (auto e : v)
{
if (e == 0)
{
int i = 0;
}
t.insert(make_pair(e, e));
cout << "Insert" << e << "->" << t.IsBalance() << endl;
}
t.InOrder();//中序打印
if (t.IsBalance())
{
cout << "是平衡二叉树" << endl;
}
else
{
cout << "不是平衡二叉树" << endl;
}
return 0;
}
7. 红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(
l
o
g
2
N
log_2 N
log2N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
8. 红黑树的应用
-
C++ STL库 – map/set、mutil_map/mutil_set
C++ STL中的std::map和std::set：这些容器类通常使用红黑树作为底层数据结构，提供了高效的查找、插入和删除操作。 -
数据库系统：红黑树常被用作数据库索引结构，例如在关系型数据库中，可以使用红黑树来实现B+树索引，提供高效的数据检索和排序功能。
-
线程调度器：操作系统中的线程调度器通常需要高效地管理和调度线程，红黑树可用于实现定时器和任务调度器，以快速查找和处理就绪的线程。
（本章完）
原文地址:https://blog.csdn.net/originalHSL/article/details/134635899
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_1377.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
