[数据结构] RBTree 模拟实现RBTree

标题:[数据结构] RBTree && 模拟实现RBTree

@水墨不写bug



目录

一、红黑树的概念

二、map和set的封装

 三、红黑树的实现

1、红黑树节点的定义

2、红黑树的结构

3、红黑树的插入

1.名称 

 2.插入节点的颜色

红黑树的insert 实现

情况一:不能确定的uncle  为红  

情况二: uncle  不存在/uncle 存在且为黑  


 

 正文开始:

一、红黑树的概念

        普通二叉树结构在存储数据时,相对于链式结构并没有太大优势,于是就出现了搜索二叉树,搜索二叉树的优势在于在查找时,一般情况下复杂度可以控制在O(logN)。但是普通的二叉搜索树无法避免的会出现一种特殊情况当插入近似有序的值时,搜索树会退化为单链表。

        解决二叉树退化为链表的问题,也就是让二叉树尽量平衡,有多重方法:如AVL树,红黑树等。本文就介绍红黑树——一种令二叉搜索树尽量平衡的策略。


        红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。

(红黑树概貌)

 红黑树的规则:

        1、每个节点只有两种颜色(红、黑)。

        2、根节点为固定的颜色:黑色。

        3、如果一个节点是红色的,则它的两个孩子节点是黑色的;(或者说:没有连续的红节点)

        4、对于树上的每一个节点,从该节点到其所有后代叶节点的简单路径上,都包含相同数目的黑色节点。

        5、每个叶节点是黑色的。(此处的叶节点指空节点)

        思考:为什么满足上面的性质,红黑树就能保证:其最长路径中节点个数不会超过最短路径节点个数的两倍?

        由规则4,从根节点出发到达任意一个叶节点的路径上,黑节点的数目是相同的。拉开差别的是红节点。由规则3,红节点只能存在于两个黑节点之间,所以最短路径就是纯黑节点,最长路径就是每两个黑节点之间存在一个红节点,最终叶子节点也是红。当且仅当这时,最短路径长度*2刚好等于最长路径的长度。 于是最长路径中节点个数不会超过最短路径节点个数的两倍。 


二、map和set的封装

        map和set在底层实现的时候,是通过封装红黑树来实现的。set看上去只有一个key,map看上去有一对值<key,val>;但是实际上在实现时,key和数据是分开的:

        set在复用红黑树时,传入的模板参数包括Key和Value,只不过两者相等,都是整形。

        map在复用红黑树时,为了保持一致,传入的模板参数包括Key和Value,只不过Value是自定义的结构体类型,也就是pair<K,V>。

        (也许你在思考后仍然不理解,不过好在我会在后面专门写一篇map/set封装的文章,具体讲解封装的细节)


 三、红黑树的实现

1、红黑树节点的定义

        在此,由于我们暂时不考虑map、set的封装,所以我们的红黑树内部的数据固定写为pair类:(传入的两个模板参数为Key,Value)

enum COLOR
{BLACK,RED
};template<class K,class V>
struct BRTreeNode
{BRTreeNode<K, V>* _parent;BRTreeNode<K, V>* _left;BRTreeNode<K, V>* _right;pair<K, V> _kv;COLOR _col;BRTreeNode(const pair<K,V>& kv = pair<K,V>()):_parent(nullptr),_left(nullptr),_right(nullptr),_kv(kv),_col(RED){}
};

 

2、红黑树的结构

         由于实现红黑树的难点在于插入后的节点颜色控制与极度不平衡时的旋转,所以我们主要实现红黑树的插入逻辑。

template<class K,class V>
class BRTree
{typedef BRTreeNode<K, V> Node;
public:BRTree();bool insert(const pair<K,V>& kv);~BRTree();private://左单旋void RotateL(Node* parent);//右单旋void RotateR(Node* parent);Node* _root;
};

 

3、红黑树的插入

        红黑树的插入分有多种情况,在分情况讨论之前,我们现明确几个概念并达成几个共识:

1.名称 

当插入节点的时候:

        新增节点称为cur;

        父节点称为parent;

        祖父节点称为grandparent;

        祖父节点除父亲节点外另一节点称为uncle;

他们在本文中都用首字母作为简写。

 2.插入节点的颜色

        当我们插入节点的时候,插入节点的颜色是什么呢?

        当插入的是黑节点,那么从根到每一个叶节点的黑节点数目不同,整棵树都不再是红黑树。

        当插入的是红节点,会有两种情况:如果父亲为黑,那么插入后这棵树仍是合法的红黑树。如果父亲为红,违背了不能存在连续的红节点,整棵树不再是红黑树。

        于是,可以得出结论:插入节点的颜色应该为红色,这样对整棵树的影响可以达到最小。

        当我们插入的是红节点时,我们如果父亲是黑,则不需调整;如果父亲是红,这就到了需要调整的时候:

插入为红,父亲为红,可以推知祖父为黑。

         使用假设法,如果祖父为红,则父亲和祖父两个节点在插入新增节点之前就是连续的红节点了,已经违背了红黑树的规则。


        所以到这里,我们可以确定插入节点(cur)为红,父亲(parent)为红,祖父(grandparent)为黑,而唯一不能确定的就是uncle节点的颜色和状态,于是uncle节点的状态和颜色就是分类讨论的依据。

红黑树的insert 实现

情况一:不能确定的uncle  为红  

        这种情况是比较简单的情况,只需要简单的变色就可以解决问题:

变色策略:p和u变为黑,g变为红。

        接下来需要将g看做是cur,继续向上变色调整。 


其实上述情况会有一种变式,具体结构如下:

        红色四边形表示只含有红色节点(其实就是一个红节点),黑色的四边形表示只含有一个黑色节点的红黑树。 

        如果新增节点在红色四边形上,那么就会导致22这个黑色节点变成红色,具体来说如下:

        新插入的节点是黑字的cur

        变色后:导致22节点颜色变为红色

        这个时候,黑色的g当成cur继续向上调整:

        这就间接转化为第一种情况的最简结构了:

        所以,要达到第一种情况,可能是插入后直接达到;也可能是向上调整后达到。第一种情况的最简形态的逻辑已经包含了所有其他形态的逻辑。

 

情况二: uncle  不存在/uncle 存在且为黑  

        uncle不存在:(四种情况)

 情况A:右单旋

旋转后变色:

 


情况B:左右双旋

旋转后变色:

 


情况C:左单旋

旋转后变色:


 情况D:右左双旋

 旋转后变色:

 

       


        旋转已经在AVL树的模拟实现中有详细的讲解,如果你对AVL树不熟悉,参考这篇:

《AVL树详解与模拟实现》

         这四种情况是uncle不存在的情况,也是uncle存在且为黑的情况的最简形态。是的,uncle存在且为黑的逻辑与uncle不存在的逻辑是一致的。


         uncle存在且为黑:

         具体分析我们可以得知:如果d、e为空,那么a、b、c中有一个黑节点。(全部情况以此类推,只要保证每条路径的黑节点数目相同即可)

         在调整过程中,会出现如下四种情况:(可以确定,这些情况就是上述uncle不存在时的四种情况的变式)

 

 

 

 这里不在重复旋转的过程。

        综上,我们要实现红黑树插入的逻辑,就需要分两种大情况来讨论,这两种情况分别是:

        uncle存在且为红;

        uncle不存在,或者存在且为黑;

        这两种情况都有一个最简的形态,最简形态的逻辑与其他形态的逻辑基本一致,所以红黑树的逻辑并不难理解。

        虽然红黑树的逻辑不难理解,但是难点在于实现时的判断,通过树的结构判断需要走哪种逻辑。

        这里,给出红黑树的实现,作为参考;

	enum COLOR{BLACK,RED};template<class K,class V>struct BRTreeNode{BRTreeNode<K, V>* _parent;BRTreeNode<K, V>* _left;BRTreeNode<K, V>* _right;pair<K, V> _kv;COLOR _col;BRTreeNode(const pair<K,V>& kv = pair<K,V>()):_parent(nullptr),_left(nullptr),_right(nullptr),_kv(kv),_col(RED){}};template<class K,class V>class BRTree{typedef BRTreeNode<K, V> Node;public:BRTree():_root(nullptr){}bool insert(const pair<K,V>& kv){//对于空的特殊处理if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;//根节点为黑return true;}//找到插入位置Node* cur = _root, * parent = nullptr;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);if (cur->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//以上的逻辑与二叉搜索树完全一致,到这里二叉树逻辑结束,红黑树开始//根据树的结构 分情况讨论//cur为红,p为红,g为黑,while (parent &&cur->_parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){//uncle在右侧//        g//   p          u//	Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED)//u存在且为红{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上处理cur = grandfather;parent = cur->_parent;}else//u不存在或者u存在且为黑//旋转{if (cur == parent->_left)//单旋{RotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else//双旋{RotateL(parent);RotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;}}}else{//uncle在左侧//        g//   u          p//					Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED)//uncle存在且为红{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = grandfather->_parent;}else//uncle不存在或者存在且为黑//旋转{if (cur == parent->_right)//单旋{RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else//双旋{RotateR(parent);RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}}}}//无论如何变化颜色,根节点的颜色总是黑色_root->_col = BLACK;return true;}}private://左单旋void RotateL(Node* parent){Node* subL = parent->_left, * subLR = subL->_right;Node* Parentparent = parent->_parent;//调整子树内部subL->_right = parent;parent->_parent = subL;parent->_left = subLR;if (subLR)subLR->_parent = parent;//调整子树与Parentparentif (Parentparent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (parent == Parentparent->_left){subL = Parentparent->_left;}else{subL = Parentparent->_right;}subL->_parent = Parentparent;}}//右单旋void RotateR(Node* parent){Node* subR = parent->_right, * subRL = subR->_left;Node* Parentparent = parent->_parent;//子树内部关系subR->_left = parent;parent->_parent = subR;parent->_right = subRL;if (subRL)subRL->_parent = parent;//子树与Parentparent关系if (Parentparent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == Parentparent->_left){subR = Parentparent->_left;}else{subR = Parentparent->_right;}}}Node* _root;};

         到这里,除了删除操作以及一些其他的简单接口,红黑树的实现基本完成了。

        红黑树是STL一些重要容器的底层结构,理解红黑树对于深入了解STL有重要意义。


完~

未经作者同意禁止转载

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/404015.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

QT翻金币小游戏(含音频图片文件资源)

目录 QT翻金币小游戏 音频图片资源文件获取 效果展示 图片 视频 实现代码 main.cpp mymainwindow.h mymainwindow.cpp startscene.h startscene.cpp selectscene.cpp playscene.h playscene.cpp mypushbutton.h mypushbutton.cpp dataconfig.h dataconfig.cpp QT…

Spring Boot: 2.7.x 至 2.7.18 及更旧的版本,漏洞说明

本文提供的修复指南将帮助开发者有效规避 CVE-2024-38808 和 CVE-2024-38809 的风险。如果你正在使用老版本的 Spring Boot&#xff0c;请尽快参考本文进行修复与升级。 此漏洞来源于spring官网&#xff1a;https://spring.io/blog/2024/08/14/spring-framework-releases-fixe…

8.17模拟赛题解

先考虑空间能不能把N个座位放好 最优的方式就是挨着摆放 那么一排能摆放QL/x的商个椅子 &#xff0c;然后计算摆放完N个座位需要多少排&#xff0c;N/Q 向上取整 计算所需要的排总共占据多宽&#xff0c;讨论有没有超过W&#xff0c;然后讨论剩余空间还能放几条走廊 如果走廊数…

【Datawhale AI夏令营第四期】 魔搭-大模型应用开发方向笔记 Task04 RAG模型 人话八股文Bakwaan_Buddy项目创空间部署

【Datawhale AI夏令营第四期】 魔搭-大模型应用开发方向笔记 Task04 RAG模型 人话八股文Bakwaan_Buddy项目创空间部署 什么是RAG&#xff1a; 我能把这个过程理解为Kimi.ai每次都能列出的一大堆网页参考资料吗&#xff1f;Kimi学了这些资料以后&#xff0c;根据这里面的信息综…

Leading SAFe领导大规模敏捷认证公开课

课程简介 SAFe – Scaled Agile Framework是目前全球最广泛使用的大规模敏捷框架&#xff0c;也是全球敏捷相关认证中增长最快、最受认可的规模化敏捷认证。全球已有超过120万名SAFe认证专业人士。据官方统计&#xff0c;获得SAFe认证的IT专业人士平均工资增长13,000美元&…

澎湃认证显实力,浪潮信息存储兼容新篇章

浪潮信息在存储技术兼容性领域取得新突破&#xff0c;其集中式存储HF/AS系列与长擎安全操作系统24强强联合&#xff0c;成功完成澎湃技术认证。此次合作不仅验证了双方产品的无缝对接能力&#xff0c;更体现了浪潮信息在推动全产业链共建共享方面的坚定决心。 浪潮信息澎湃技术…

python人工智能001:NumPy科学计算库说明与安装

1. NumPy说明 NumPy&#xff08;Numerical Python&#xff09;是Python的一个开源数值计算扩展库。它提供了一个强大的N维数组对象ndarray&#xff0c;以及用于对这些数组进行操作的函数。NumPy的数组和数组操作是Python数据分析、机器学习、科学计算等领域的基础。 NumPy的主…

Linux 配置定时任务

Linux定时任务&#xff0c;通常被称为Cron Jobs&#xff0c;在系统管理和运维自动化领域中扮演着至关重要的角色&#xff0c;并且在日常的服务器维护活动中也展现出了广泛而深远的应用价值。这种强大的工具允许用户按照预定的时间周期自动执行各种任务&#xff0c;如数据备份、…

从零开始掌握限流技术:计数器、滑动窗口、漏桶与令牌桶详解

为什么需要限流呢&#xff1f; &#x1f539;想象一下&#xff0c;你的服务器就像一个繁忙的餐馆&#xff0c;而你的应用就像是餐馆的服务员。餐馆里人山人海&#xff0c;每个人都在争先恐后地想要点餐。这时候&#xff0c;如果没有一个好的限流机制&#xff0c;会发生什么呢&…

京东2025届秋招 算法开发工程师 第2批笔试

目录 1. 第一题2. 第二题3. 第三题 ⏰ 时间&#xff1a;2024/08/17 &#x1f504; 输入输出&#xff1a;ACM格式 ⏳ 时长&#xff1a;2h 本试卷还有选择题部分&#xff0c;但这部分比较简单就不再展示。 1. 第一题 村子里有一些桩子&#xff0c;从左到右高度依次为 1 , 1 2…

【免费】企业级大模型应用推荐:星环科技无涯·问知

无涯问知是星环科技发布的大模型应用系统&#xff0c;那么我们先简单了解下星环科技吧&#xff01; 星环科技&#xff08;股票代码&#xff1a;688031&#xff09;致力于打造企业级大数据和人工智能基础软件&#xff0c;围绕数据的集成、存储、治理、建模、分析、挖掘和流通等数…

这个是git使用的合集

如果遇到了关于git和github的bug就会写这里 2024/8/16 github一直没有打卡和上传代码是因为感觉除了做项目的情况&#xff0c;普通的学习和普通的笔记没必要记在github里&#xff1b;如果是笔记类的东西为什么不记在csdn上呢&#xff1f;如果是算法题算法网站上回有记录啊&am…

CAD图纸加密软件哪个好?(这六款大众好评度高!)

在CAD图纸加密软件领域&#xff0c;有多款软件因其高效、安全、易用等特点而广受好评。 以下是六款大众好评度较高的CAD图纸加密软件&#xff0c;它们各自具有独特的功能和优势&#xff1a; 1.安企神 特点&#xff1a;它以其强大的透明加密技术和精细化的权限管理功能著称。 …

python爬虫爬取某图书网页实例

文章目录 导入相应的库正确地设置代码的基础部分设置循环遍历遍历URL保存图片和文档全部代码即详细注释 下面是通过requests库来对ajax页面进行爬取的案例&#xff0c;与正常页面不同&#xff0c;这里我们获取url的方式也会不同&#xff0c;这里我们通过爬取一个简单的ajax小说…

MPU6050详细介绍

一、MPU6050介绍 MPU6050是由三个陀螺仪和三个加速度传感器组成的6轴运动处理组件 内部主要结构&#xff1a;陀螺仪、加速度计、数字运动处理器DMP&#xff08;Digital Motion Processor&#xff09; MPU6050有两个IIC接口&#xff0c;第一IIC接口可作为主接口给单片机传输数…

CSP-CCF 202012-1 期末预测之安全指数

一、问题描述 二、解答 #include<iostream> using namespace std; int main() {int n;cin >> n;int w[100001] { 0 };int score[100001] { 0 };for (int i 1; i < n; i){cin >> w[i] >> score[i];}int y 0;for (int i 1; i < n; i){y y …

电脑监控软件有哪些,哪款更好用?一网打尽!电脑监控软件大搜罗,总有一款适合你!

甲&#xff1a;哎&#xff0c;您听说了吗&#xff1f;这年头&#xff0c;电脑监控软件那是五花八门&#xff0c;跟变戏法似的&#xff01; 乙&#xff1a;哦&#xff1f;怎么个五花八门法&#xff1f; 甲&#xff1a;嘿&#xff0c;您还别说&#xff0c;从实时监控到网络追踪…

在HFSS中对曲线等结构进行分割(Split)

在HFSS中对曲线进行分割 我们往往需要把DXF等其他类型文件导入HFSS进行分析&#xff0c;但是有时需要对某一个曲线单独进行分割成两段修改。 如果是使用HFSS绘制的曲线&#xff0c;我们修改起来非常方便&#xff0c;修改参数即可。但是如果是导入的曲线&#xff0c;则需要使用…

js实现图片以鼠标为中心滚轮缩放-vue

功能背景 实现以鼠标在图中的位置为中心进行图片的滚轮缩放&#xff0c;现在是无论鼠标位置在哪都以图片中心进行缩放&#xff0c;这不符合预期&#xff1b; 关键点 缩放前鼠标在的位置是 A&#xff08;clinetX,clientY&#xff09; 点&#xff0c;缩放后鼠标的位置是 A’&a…

技术分享-商城篇-订单支付微信篇(十二)

B2C商城微信支付全解析&#xff1a;H5支付、小程序支付、JSAPI支付与APP支付 引言 在之前的文章中&#xff0c;我们聊了B2B2C的商城相关功能模块&#xff0c;如&#xff1a;首页布局、商品、购物车、购物结算、订单支付等&#xff0c;但是B2C商城的订单支付方式的选择&#x…