C++进阶篇4---番外-红黑树

一、红黑树的概念

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

红黑树的性质

  1. 每个结点不是红色就是黑色
  2. 根节点是黑色的 
  3. 如果一个节点是红色的,则它的两个孩子结点是黑色的 (即不能出现两个连续的红色结点)
  4. 对于每个结点,从该结点到其所有后代叶结点的简单路径(从根节点到空结点)上,均包含相同数目的黑色结点 
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点,也被叫做NIL)

下图是一个红黑树

根据红黑树的性质:我们能得到这样一个结论---最长路径不会超过最短路径的两倍,为什么呢?

理由如下:因为每条路径上黑色节点的个数要相同,所以最短的路径上的点均为黑色结点,同时因为不能出现红色结点相邻的情况,所以最长路径上的结点颜色只能是黑红相间,故得出上诉结论

二、红黑树结点定义

enum Colour //这里用的枚举类型,也可以用其他的类型,只要能代表红黑两种颜色就行,如true/false
{BLACK,RED
};template<class K,class V>
struct RBTreeNode {RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;pair<K, V>_kv;Colour _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};

思考:为什么要将结点颜色默认设置为红色???

理由如下:由于每条路径上的黑色节点的个数要保持相同,如果我们插入的结点的颜色为黑色,那么必然该节点所在路径的黑色节点的个数要增加,就会导致这颗树的其他所有路径都需要多一个黑色节点,影响范围太大,而如果插入的结点颜色为红色,我们只要关心它所在子树的情况就行,具体看下面的插入操作。故每个新插入结点颜色都默认为红色

三、红黑树插入结点

红黑树是在二叉搜索树的基础上加上其平衡限制条件,因此红黑树的插入可分为两步:
1.按照二叉搜索树的规则插入新节点,如下
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* cur = _root;Node* parent = nullptr;while (cur) {if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);cur->_parent = parent;if (parent->_kv.first > kv.first){parent->_left = cur;}else{parent->_right = cur;}//调整红黑树//...}
private:Node* _root = nullptr;
};

2.检查新节点插入后,红黑树的性质有没有被破坏

因为新节点的默认颜色是红色,因此:如果其双亲节点的颜色是黑色,没有违反红黑树任何
性质,则不需要调整;但当新插入节点的双亲节点颜色为红色时,就违反了性质三不能有连
在一起的红色节点,此时需要对红黑树分情况来讨论  (p-parent  g-grandfather  u-uncle)   

情况一:cur为红,p为红,g为黑,u存在且为红

在这种情况下,我们只要改变结点的颜色就能保持红黑树的性质。

(注意:这种情况下,不用关心cur所在的位置)

情况二:cur为红,p为红,g为黑,u不存在或为黑色

 

这里就无法通过改变p、g、u的颜色来保持红黑树的性质(读者可以去手玩尝试一下),需要进行旋转+变色才行,那么看到这种形状的图形,我们就应该想到AVL树中的单旋和双旋,上面的情况很明显对应右单旋,旋转之后如下图

如何改变颜色使得红黑树的性质保持不变?

1.uncle为空,显而易见,将g变为红,p变为黑(可能有人会觉得将cur变成黑不是也行嘛?但如果p为红,且它是子树,那么还需要向上调整,会很麻烦,但如果p为黑色,那么它本身既符合红黑树性质,也并不会对其他的子树产生影响,直接就一步到位了)

2.uncle为黑色,(这种情况下,cur不可能是新插入的结点,只能是情况一向上调整得到的),这里就要分析a,b,c,d,e这几颗子树中黑色节点的个数,显然a,b,c的黑色结点个数相同,d和e的黑色结点比abc少一个,所以将p变为黑色,g变为红色,就能保持红黑树的性质(至于为什么不选择将g变成红色,理由同上)

具体的旋转和AVL树一样,只是红黑树旋转后需要变色,AVL树旋转后需要调整平衡因子,不了解的,可以看我写过的AVL树

这里,我们还要考虑cur所在的位置,共四种情况,第一种情况就是上面所讲的,剩下三种的旋转+变色,留给读者思考【旋转不会的可以去看我之前写的AVL树】

 

总结:红黑树的结点的插入首先看父节点是否为黑色(插入结点为根的情况要特别判断),如果为黑,不用处理,如果为红,关键看uncle结点,它决定了我们是否需要旋转,如果是红色,则只需要变色,如果是黑色/不存在,我们需要根据cur所在的位置选择合适的旋转方式,并对旋转之后的结点进行变色

 代码如下---附带检查检查红黑树是否正确的函数

enum Colour {BLACK,RED
};template<class K,class V>
struct RBTreeNode {RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;pair<K, V>_kv;Colour _col;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* cur = _root;Node* parent = nullptr;while (cur) {if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);cur->_parent = parent;if (parent->_kv.first > kv.first){parent->_left = cur;}else{parent->_right = cur;}//父节点为黑,不用处理//为红需要调整while (parent && parent->_col == RED){//    g//  p   u//cNode* grandparent = parent->_parent;if (grandparent->_left == parent){Node* uncle = grandparent->_right;if (uncle && uncle->_col == RED)//情况一{grandparent->_col = RED;parent->_col = uncle->_col = BLACK;cur = grandparent;parent = cur->_parent;}else//情况二{if (parent->_left == cur)//单旋{RotateR(grandparent);grandparent->_col = RED;parent->_col = BLACK;}else//双旋{RotateL(parent);RotateR(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}else{//     g//  u     p//       c  cNode* uncle = grandparent->_left;if (uncle && uncle->_col == RED){//变色grandparent->_col = RED;parent->_col = uncle->_col = BLACK;//向上走cur = grandparent;parent = cur->_parent;}else{if (parent->_right == cur){RotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else{RotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}}_root->_col = BLACK;return true;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;Node* pParent = parent->_parent;subR->_left = parent;parent->_right = subRL;parent->_parent = subR;if (subRL)//注意h==0的情况subRL->_parent = parent;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{subR->_parent = pParent;if (pParent->_left == parent){pParent->_left = subR;}else{pParent->_right = subR;}}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;Node* pParent = parent->_parent;subL->_right = parent;parent->_left = subLR;parent->_parent = subL;if (subLR)//注意h==0的情况subLR->_parent = parent;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{subL->_parent = pParent;if (pParent->_left == parent){pParent->_left = subL;}else{pParent->_right = subL;}}}void InOrder(){_InOrder(_root);}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}bool Isbalance(){return _Isbalance(_root);}//检查是否出现两个连续的红色节点+是否路径上的黑色节点的个数是否相同bool check(Node* root,int blacknum){if (root == nullptr){cout << blacknum << " ";return true;}if (root->_col == RED && root->_parent->_col == RED)return false;if (root->_col == BLACK)blacknum++;return check(root->_left, blacknum) && check(root->_right, blacknum);}bool _Isbalance(Node* root){if (root == nullptr)return true;if (root->_col == RED){cout <<"出现两个连续的红色节点:"<< root->_kv.first << endl;return false;}return check(root->_left, 1) && check(root->_right, 1);}
private:Node* _root = nullptr;
};

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

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

相关文章

19. 深度学习 - 用函数解决问题

文章目录 Hi&#xff0c; 你好。我是茶桁。 上一节课&#xff0c;我们从一个波士顿房价的预测开始写代码&#xff0c;写到了KNN。 之前咱们机器学习课程中有讲到KNN这个算法&#xff0c;分析过其优点和缺点&#xff0c;说起来&#xff0c;KNN这种方法比较低效&#xff0c;在数…

Leetcode刷题详解—— 有效的数独

1. 题目链接&#xff1a;36. 有效的数独 2. 题目描述&#xff1a; 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 &#xff0c;验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的…

U-Mail邮件中继,让海外邮件沟通更顺畅

在海外&#xff0c;电子邮件是人们主要的通信工具&#xff0c;尤其是商务往来沟通&#xff0c;企业邮箱是标配。这主要是因为西方国家互联网发展较早&#xff0c;在互联网早期&#xff0c;电子邮件技术较为成熟&#xff0c;大家都用电子邮件交流&#xff0c;于是这成了一种潮流…

Jenkins简介及Docker Compose部署

Jenkins是一个开源的自动化服务器&#xff0c;用于自动化构建、测试和部署软件项目。它提供了丰富的插件生态系统&#xff0c;支持各种编程语言和工具&#xff0c;使得软件开发流程更加高效和可靠。在本文中&#xff0c;我们将介绍Jenkins的基本概念&#xff0c;并展示如何使用…

2023年第十六届山东省职业院校技能大赛中职组“网络安全”赛项规程

第十六届山东省职业院校技能大赛 中职组“网络安全”赛项规程 一、赛项名称 赛项名称&#xff1a;网络安全 英文名称&#xff1a;Cyber Security 赛项组别&#xff1a;中职组 专业大类&#xff1a;电子与信息大类 二、竞赛目的 网络空间已经成为陆、海、空、天之后的第…

C/C++满足条件的数累加 2021年9月电子学会青少年软件编程(C/C++)等级考试一级真题答案解析

目录 C/C满足条件的数累加 一、题目要求 1、编程实现 2、输入输出 二、算法分析 三、程序编写 四、程序说明 五、运行结果 六、考点分析 C/C满足条件的数累加 2021年9月 C/C编程等级考试一级编程题 一、题目要求 1、编程实现 现有n个整数&#xff0c;将其中个位数…

linux安装并配置git连接github

git安装 sudo apt-get install git git信息配置 git config --global uer.name "yourname" git config --global user.email "youremail" 其中&#xff0c;yourname是你在github上配置的用户名&#xff0c;youremail是你在github上设置的邮箱 查看git…

吃透 Spring 系列—MVC部分

目录 ◆ SpringMVC简介 - SpringMVC概述 - SpringMVC快速入门 - Controller中访问容器中的Bean - SpringMVC关键组件浅析 ◆ SpringMVC的请求处理 - 请求映射路径的配置 - 请求数据的接收 - Javaweb常用对象获取 - 请求静态资源 - 注解驱动 标签 ◆ SpringMV…

STL简介+浅浅了解string——“C++”

各位CSDN的uu们好呀&#xff0c;终于到小雅兰的STL的学习了&#xff0c;下面&#xff0c;让我们进入CSTL的世界吧&#xff01;&#xff01;&#xff01; 1. 什么是STL 2. STL的版本 3. STL的六大组件 4. STL的重要性 5. 如何学习STL 6.STL的缺陷 7.为什么要学习string类 …

AIGC专栏8——EasyPhoto 视频领域拓展-让AIGC肖像动起来

AIGC专栏8——EasyPhoto 视频领域初拓展-让AIGC肖像动起来 学习前言源码下载地址技术原理储备Video Inference 功能说明 & 效果展示1、Text2Video功能说明a、实现原理简介b、文到视频UI介绍c、结果展示 2、Image2Video功能说明a、实现原理简介i、单图模式ii、首尾图模式 b、…

react 组件进阶

目标&#xff1a;1.能够使用props接收数据 2.能够实现父子组建之间的通讯 3.能够实现兄弟组建之间的通讯 4.能够给组建添加props校验 5.能够说出生命周期常用的钩子函数 6.能够知道高阶组件的作用 一&#xff0c;组件通讯介绍 组件是独立且封闭的单元&#xff0c;默认情况下&a…

【PyQt】(自制类)处理鼠标点击逻辑

写了个自认为还算不错的类&#xff0c;用于简化mousePressEvent、mouseMoveEvent和mouseReleaseEvent中的鼠标信息。 功能有以下几点&#xff1a; 鼠标当前状态&#xff0c;包括鼠标左/中/右键和单击/双击/抬起鼠标防抖(仅超出一定程度时才判断鼠标发生了移动)&#xff0c;灵…

mysql主从复制-使用心得

文章目录 前言环境配置主库从库 STATEMENTbinloggtidlog-errorDistSQL总结 前言 mysql 主从复制使用感受&#xff0c;遇到一些问题的整理&#xff0c;也总结了一些排查问题技巧。 环境 mysql5.7 配置 附&#xff1a;千万级数据快速插入配置可以参考&#xff1a;mysql千万数…

112. 路径总和

描述 : 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径&#xff0c;这条路径上所有节点值相加等于目标和 targetSum 。如果存在&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 叶子节点 是指没…

Ubuntu 创建并发布 Django 项目

Ubuntu 创建并发布 Django 项目 升级操作系统和软件 sudo apt updatesudo apt -y dist-upgrade 安装 python3-pip sudo apt -y install python3-pip安装 django pip install -i https://pypi.tuna.tsinghua.edu.cn/simple djangosudo apt -y install python3-django创建 dj…

RT-Thread:嵌入式实时操作系统的设计与应用

RT-Thread&#xff08;Real-Time Thread&#xff09;是一个开源的嵌入式实时操作系统&#xff0c;其设计和应用在嵌入式领域具有重要意义。本文将从RT-Thread的设计理念、核心特性&#xff0c;以及在嵌入式系统中的应用等方面进行探讨&#xff0c;对其进行全面的介绍。 首先&a…

2023/11/12总结

踩坑记录&#xff1a; org.springframework.jdbc.BadSqlGrammarException: ### Error querying database. Cause: java.sql.SQLSyntaxErrorException: Expression #1 of SELECT list is not in GROUP BY clause and contains nonaggregated column elm.flavors.id which is …

【FAQ】Gradle开发问题汇总

1. buildSrc依赖Spring Denpendency时报错 来自预编译脚本的插件请求不能包含版本号。请从有问题的请求中删除该版本&#xff0c;并确保包含所请求插件io.spring.dependency-management的模块是一个实现依赖项 解决方案 https://www.5axxw.com/questions/content/uqw0grhttps:/…

生成式AI - Knowledge Graph Prompting:一种基于大模型的多文档问答方法

大型语言模型&#xff08;LLM&#xff09;已经彻底改变了自然语言处理&#xff08;NLP&#xff09;任务。它们改变了我们与文本数据交互和处理的方式。这些强大的AI模型&#xff0c;如OpenAI的GPT-4&#xff0c;改变了理解、生成人类类似文本的方式&#xff0c;导致各种行业出现…

Spring基础——初探

Spring是一个开源的Java应用程序开发框架&#xff0c;它提供了一个综合的编程和配置模型&#xff0c;用于构建现代化的企业级应用程序。Spring的目标是简化Java开发&#xff0c;并提供了许多功能和特性&#xff0c;以提供开发效率、降低开发复杂性。 特别 主要功能 IoC容器 …