【C++进阶学习】第八弹——红黑树的原理与实现——探讨树形结构存储的最优解

🕗 发布于 2024-07-22 20:22 学习算法 数据结构 c++

二叉搜索树：【C++进阶学习】第五弹——二叉搜索树——二叉树进阶及set和map的铺垫-CSDN博客

AVL树：

【C++进阶学习】第七弹——AVL树——树形结构存储数据的经典模块-CSDN博客

前言：

在前面，我们已经学习了二叉搜索树和它的改进AVL树，今天，我们来学习另一种由二叉搜索树改进而来的树形结构——红黑树

一、红黑树的概念

红黑树是一种特殊的二叉树，它的每个节点都增加一个存储为表示颜色，要么是黑色，要么是白色。并且通过对每条路径上添加节点时节点的颜色限制，来确保每个路径上的黑色节点数量一致，且最长路径长度最多是最短路径长度的两倍，因此达到平衡。

二、红黑树的性质

红黑树有以下五个性质：

节点是红色或黑色：每个节点都有一个颜色属性，颜色可以是红色或黑色。

根节点是黑色：树的根节点必须是黑色。

红色节点的子节点是黑色：如果一个节点是红色，则它的两个子节点必须是黑色（即不能有两个连续的红色节点）。

每个节点到其每个叶子节点的路径都包含相同数量的黑色节点：从任何节点到其每个叶子节点的路径上，经过的黑色节点的数量必须相同。

叶子节点是黑色：红黑树的叶子节点（通常是指空节点）被视为黑色。

三、红黑树的节点结构

template<class K, class V>
struct BSTreeNode
{
BSTreeNode<K, V>* _left;    //左子树
BSTreeNode<K, V>* _right;   //右子树
BSTreeNode<K, V>* _parent;  //父亲
pair<K, V> _kv;       //存放节点值的
string _col;    //颜色（通过这个可以直到左右子树存在情况）

//构造函数
BSTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col("RED")     //默认颜色为红色
{}
};

红黑树的节点结构与二叉搜索树和AVL树差别不大，最大的差别就是加入了一个新的存储点——颜色

四、红黑树的操作

红黑树的基本操作包括插入、删除和查找。以下是这些操作的简要说明：

插入：

将新节点插入到树中，初始时将其标记为红色。
可能会破坏红黑树的性质，需要通过旋转和重新着色来恢复性质。

删除：

删除节点后，可能会破坏红黑树的性质。
需要进行调整，包括旋转和重新着色，以恢复红黑树的性质。

查找：

查找操作与普通的二叉搜索树相同，通过比较节点值来决定向左或向右子树查找。

在这几个操作中，插入是红黑树的关键，因为这是构造红黑树的关键，怎样插入才能保证红黑树的节点颜色、路径长度符合规定，下面我们就来重点讲解一下红黑树的节点插入操作：

首先我们要先清楚一点，红黑树也是二叉搜索树，所以它肯定是符合二叉搜索树的性质的——左边子树值小于根，右边子树值大于根

问题的关键是如何保证插入后结构的颜色符合规定，要做到这一点，我们首先就先要摸清插入节点会遇到的所有情况，然后我们再分析如何解决这些情况：

（强调一下：一定要把前面AVL树中讲的左右旋先弄明白）

假设：cur表示当前节点，p表示父节点，g表示祖父节点，u为叔叔节点

情况一：cur为红，p为黑

情况二: cur为红，p为红，g为黑，u存在且为红

解决方法：把p、u变成黑，g变为红，然后让g变为cur继续向上处理

情况三：cur为红，p为红，g为黑，u不存在

解决方法：把p变为黑，g变为红，然后进行左旋/右旋

情况四：cur为红，p为红，g为黑，u存在且为黑

解决方法：把p变为黑，g变为红，同时右旋/左旋

特殊情况：如果当cur的插入位置形似AVL树中的RL型或LR型时，要先进行旋转转换成上面几种情况

五、红黑树的实现代码

RBTree.h

//红黑树
#include<iostream>
using namespace std;

template<class K, class V>
struct BSTreeNode
{
BSTreeNode<K, V>* _left;    //左子树
BSTreeNode<K, V>* _right;   //右子树
BSTreeNode<K, V>* _parent;  //父亲
pair<K, V> _kv;       //存放节点值的
string _col;    //颜色（通过这个可以直到左右子树存在情况）

//构造函数
BSTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col("RED")     //默认颜色为红色
{}
};

template<class K, class V>
class BSTree
{
typedef BSTreeNode<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;
}


//按搜索二叉树规则插入到指定位置后，再检验一下是否符合红黑树的规则进行相关调整
while (parent && parent->_col == "RED")    //当父节点存在且父节点为红时，进行相关调整
{
Node* grandfather = parent->_parent;
if(parent==grandfather->_left)       //p为g的左孩子时
{
//     g
//   p       
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == "RED")    //u存在且为红
{
//       g
//    p      u
// cur
parent->_col = uncle->_col = "BLACK";
grandfather->_col = "RED";

//继续往上更新
cur = grandfather;
parent = cur->_parent;
}
else                               //u不存在/u存在且为黑
{
//       g
//     p
//  cur
if (cur == parent->_left)
{
RotateR(grandfather);
grandfather->_col = "RED";
parent->_col = "BLACK";
}
else
{
//LR型
RotateL(parent);
RotateR(grandfather);
cur->_col = "BLACK";
grandfather->_col = "RED";
}
break;
}
}
else                      //p为g的右孩子时，与上面的相反即可
{
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)
{
//       g
//     u    p
//            c
RotateL(grandfather);
grandfather->_col = "RED";
parent->_col = "BLACK";
}
else
{
//       g
//     u   p
//        c
//RL型
RotateR(parent);
RotateL(grandfather);
cur->_col = "BLACK";
grandfather->_col = "RED";
}
break;
}
}
}
_root->_col = "Black";
return true;
}

//进行旋转调整（旋转操作与AVL树中的完全一样，不明白的可以看我之前的文章）
void RotateL(Node* parent)   //左单旋
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentParent = parent->_parent;

parent->_right = subRL;
subR->_left = parent;

if(subRL)
   subRL->_parent = parent;

if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
parent->_parent = subR;
}
void RotateR(Node* parent)   //右单旋
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentParent = parent->_parent;

parent->_left = subLR;
subL->_right = parent;

if (subLR)
{
subLR->_parent = parent;
}
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
parent->_parent = subL;
}

//中序打印
void Inorder()
{
_Inorder(_root);
cout << endl;
}
void _Inorder(Node* root)
{
if (root == nullptr)
return;
_Inorder(root->_left);
cout << root->_kv.first << " ";
_Inorder(root->_right);
}

//检查是否为BS树（检查两点）
//一：是否有连续的红节点
//二：各个路径上的黑色节点个数是否相等
bool Check(Node* root,int blacknum,const int refVal)
{
if (root == nullptr)
{
if (blacknum != refVal)
{
cout << "存在黑色节点个数不相等的路径" << endl;
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 refVal = 0;      //参考值
Node* cur = _root;
while (cur)
{
if (cur->_col == "BLACK")
{
++refVal;
}
cur = cur->_left;
}
int blacknum = 0;    //根节点到当前节点黑色节点数量
return Check(_root, blacknum,refVal);
}

private:
Node* _root = nullptr;
};

RBTree.c

//红黑树
int main()
{
int a[] = { 4,2,6,1,3,5,15,7,16,14 };   
//int a[] = { 790,760,969,270,31,424,377,24,702 };
BSTree<int, int> t;
for (auto e : a)
{
t.Insert(make_pair(e, e));
}
t.Inorder();
cout << "是否是红黑树（1/0）："<<t.IsBalance() << endl;
return 0;
}

运行结果：

六、总结

以上就是红黑树的全部内容，红黑树因为其自平衡的特性，及通过节点颜色来操作其树形结构的特点，极大的提高了数据存储及处理的效率，需要我们好好掌握

感谢各位大佬观看，创作不易，还请各位大佬一键三连！！！

原文地址：https://blog.csdn.net/2301_80220607/article/details/140610404

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：照片怎么改大小kb？分享5个改小图片的工具
下一篇：最优化方法求解-圆环内传感器节点最大最小距离分布

DSC+DW实时+异步搭建部署
配置 DMDSC+双节点节点数据守护。
阅读更多2024-09-24
uni-app快速入门
uni-app 是一个使用 Vue.js 开发所有前端应用的框架，开发者编写一套代码，可发布到iOS、Android、Web（响应式）、以及各种小程序（微信/支付宝/百度/头条/飞书/QQ/快手/钉钉
阅读更多2024-09-24
【网络安全】TCP和UDP
流控（3）应该算是传输可靠性（2）中的一环，流量发的快一点或者慢一点，主要目的是保证对方能够正常收到这些信息，能够正常地处理这些信息，并且保证传输效率。我们发数据的时候，这个数据包有可能很大，因为里面
阅读更多2024-09-24
基于TCP协议的网络通信
本文实现基于TCP协议的网络传输的服务器和客户端
阅读更多2024-09-24
系统架构设计师教程第10章 10.7 软件架构维护笔记
侧重于软件开发和实现过程所涉及的架构静态演化，从架构文档等信息来源中捕捉架构知识，进而提供架构的质量属性及其设计依据以进行记录和评价。架构知识管理要涵盖架构的解决方案，产生该方案的架构设计决策、设计依
阅读更多2024-09-24
网络安全：守护数字世界的第一道防线
网络安全是指通过一系列技术、管理和法律手段，保护计算机网络及其数据免受恶意攻击、损坏或未经授权访问的过程。它不仅涉及计算机和网络设备的安全性，还涵盖了数据的保护、用户的隐私以及网络服务的可用性。随着互
阅读更多2024-09-24
002.从零开始实现softMax回归(pytorch)
动手从零实现神经网络softMax回归
阅读更多2024-09-24
Avalonia第三方UI库Semi.Avalonia用法详解
Semi是一个基于Avalonia的UI库，旨在提供更加现代和灵活的UI组件。Semi Avalonia允许开发者利用更简洁和美观的UI设计来构建跨平台应用程序。下面将介绍Semi Avalonia的
阅读更多2024-09-24
【时时三省】(C语言基础)指针笔试题4
山不在高，有仙则名。水不在深，有龙则灵。----CSDN 时时三省。
阅读更多2024-09-24
Windows11 23H2纯净版免费下载：无广告无捆绑！
今天，系统之家小编带来的是2024年最新发布的Windows11 23H2纯净版系统，该版本系统基于微软官方最新Windows 11 23H2 64位专业版，进行精心地离线制作与优化，将所有捆绑流氓软
阅读更多2024-09-24

【C++进阶学习】第八弹——红黑树的原理与实现——探讨树形结构存储的最优解

一、红黑树的概念

二、红黑树的性质

三、红黑树的节点结构

四、红黑树的操作

五、红黑树的实现代码

六、总结

相关文章