【红黑树】—— 我与C++的不解之缘（二十五）

前言

学习了avl树，现在来学习红黑树。

一、什么是红黑树

红黑树是一颗平衡二叉搜索树，它每一个节点增加了一个存储位表示节点的颜色，可以是红色或者黑色。

相比较于AVL树，红黑树也是一个自平衡二叉搜索树，但是它与AVL树控制平衡的方式不同；

  • AVL是通过平衡因子来控制整个树的平衡
  • 红黑树则是通过节点的颜色红/黑来控制整个树的平衡

这里红黑树通过对任何一条从根到叶子的路径上每一个节点的颜色的约束，从而确保最长路径不会超过最短路径的2倍，因此让整个树保证平衡。

红黑树的规则

红黑树遵循以下几条规则：

  • 每一个节点的颜色不是RED/红色就是BLACE/黑色。
  • 根节点的颜色为BLACK。
  • 如果一个节点是红色的，那么它的孩子节点就一定是黑色的；也就是在任意一条路径中不会出现连续的红色节点。
  • 对任何一个节点，从这个节点到其所有的NULL的简单路径上，均包含相同数量的黑色节点。

这里在《算法导论》和《STL源码剖析》书籍中，存在这样的一条定义每个叶子节点NIL都是黑色；

注意：这里说的并不是我们认为的叶子节点，而是NULL节点；

在这里插入图片描述

有了NIL节点我们就可以十分清楚的看出来所有的路径。

为什么红黑树能确保最长路径不超过最短路径的2倍

  • 根据规则4，从根节点到NULL节点每条路径都存在相同数量的黑色节点；所以这里假设一下极端情况：最短路径下全是黑色节点，长度为bh，那么黑色节点的个数也是bh。
  • 根据规则3，任何一条路径下不会存在连续的红色节点，那极端情况下，最长路径就是由一黑一红组成的，那最长路径的长度为2*bh，黑色节点个数是bh。
  • 然而极端情况并不是在每一个红黑树中都存在的；假设从根节点到NULL的一条路径长度为h，那就存在bh <= h <= 2*bh。

在这里插入图片描述

红黑树的效率

对于红黑树，确实控制了平衡，但是它的查找效率如何呢？

这里假设红黑树的节点个数为n，h是最短路径的长度；那我们就可以得出红黑树最坏情况是走最长路径，时间复杂度就是O(log N)

虽然说红黑树相对于AVL树的效率较差一点，但是它的效率还是O(log N)

  • AVL树通过高度来严格控制了整个树的平衡
  • 而红黑树就通过了四条规则，控制树中节点的颜色来控制这个树的相对平衡。

二、红黑树的结构

说了这么多，现在来看一下红黑树的结构

红黑树首先是一个三叉链结构，还要存放pair<K,V>，和颜色Color

这里颜色使用枚举变量来表示

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

三、红黑树的插入

了解了红黑树节点的结果，现在来看红黑树的插入节点

插入一个值，我们需要按照`二叉搜索树的结构来进行插入，插入之后来判断是否满足红黑树的规则

这里AVL在找到插入位置并插入节点后做的是更新平衡因子；

而红黑树则是进行循环操作（变色、旋转+变色1等），直到其父节点不存在（遍历到_root)或者父节点颜色为BLACK。

首先就是插入节点的颜色

  • 如果是空树插入，新增节点为黑色；
  • 那如果是非空树的插入节点，新增节点就必须是红色
template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:RBTree() {};bool insert(const pair<K, V>& kv){if (_root == nullptr)//空树插入{_root = new Node(kv);_root->_col = BLACK;return true;}//非空树插入Node* tail = _root;Node* parent = nullptr;while (tail){if (kv.first > tail->_kv.first){parent = tail;tail = tail->_right;}else if (kv.first < tail->_kv.first){parent = tail;tail = tail->_left;}else{return false;}}Node* cur = new Node(kv);cur->_col = RED;//新插入节点一定是红色cur->_parent = parent;if (cur->_kv.first > parent->_kv.first){parent->_right = cur;}else if (cur->_kv.first < parent->_kv.first){parent->_left = cur;}//进行不满足规则的一系列处理}
private:Node* _root;
};

这里如果新增节点是黑色，那就一定破坏了规则四（因为插入之前是符合条件的红黑树）。

如果我们插入红色节点，其父节点为黑色就不需要做任何调整；

如果父节点是红色，这时违反了规则三，我们需要进一步分析

  • 此时其父节点p为红色，那祖父节点g就一定为黑色；而叔节点uncle颜色并不确定

    这时c插入节点，p父节点，g祖父节点颜色都是固定的，这种情况下我们来看u叔节点

我们根据u节点的颜色可以分为三种情况

1. 情况一： 变色

在上述中，我们已经确定了c、p、g的颜色，现在我们现在唯一不能确定的就是u节点；

如果u节点存在，且u节点的颜色为红色，如下图所示

在这里插入图片描述

对于这种情况，u存在且为红色；通过观察我们可以发现：

g节点的黑色节点影响的路径是其左右子树p和u的路径，那我们将p和u变成黑色、g变成红色

变化之后可以发现，从g节点到NULL节点的路径上的黑色几点并没有发生变化。

这里有些问题：

  1. 在上述图中，g的父节点为黑色，那如果g的父节点为红色呢？

这就好说了，将g赋值给c，继续执行循环即可。

  1. 那现在存在一个问题，如果在向上变色的过程中，g为根节点怎么办？

这里在执行完循环过后，直接把_root的颜色修改为黑即可。

  1. 如果在执行向上变色的过程中遇到u不存在或者u存在但其颜色为黑怎么办？

接着往下看情况二：

2. 情况二：单选 + 变色

如果我们在向上执行变色的过程中，遇到了u不存在或者u存在但它的颜色为黑；

这时我们就不能只变色来解决问题了。

在这里插入图片描述

这种情况下，我们就需要进行一次单旋，再进行变色才能解决问题

在这里插入图片描述

在这里插入图片描述

根据上图可以看到，右单旋的条件是c = p->_left && u==g->_right

这里都是右单旋的问题，左单旋是以下情况，就不做分析了。

在这里插入图片描述

进行右单旋加变色的条件是c = p->_right && u==g->_left

3. 情况三： 双旋 + 变色

在上述过程中，只有单旋，那如果单旋解决不了问题呢？

如下图所示：

在这里插入图片描述

如果我们在p的这个位置插入（或者有g向上更新变化过来的c）

这时就不能就进行单旋了，就像AVL中平衡因中一样，如果进行了单旋就会发现把问题变得更加复杂了。

这是要进行左右双旋转

先以p节点进行一次左单旋，再以g节点进行一下右单旋。

在这里插入图片描述

在这里插入图片描述

当然，存在左右双旋的情况，也存在右左双旋的情况，如下图所示（这里就不推理了）

在这里插入图片描述

插入代码实现：

有了上述情况分析，现在来实现红黑树插入的代码：

template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:RBTree() {};bool insert(const pair<K, V>& kv){if (_root == nullptr)//空树插入{_root = new Node(kv);_root->_col = BLACK;return true;}//非空树插入Node* tail = _root;Node* parent = nullptr;while (tail){if (kv.first > tail->_kv.first){parent = tail;tail = tail->_right;}else if (kv.first < tail->_kv.first){parent = tail;tail = tail->_left;}else{return false;}}Node* cur = new Node(kv);cur->_col = RED;//新插入节点一定是红色cur->_parent = parent;if (cur->_kv.first > parent->_kv.first){parent->_right = cur;}else if (cur->_kv.first < parent->_kv.first){parent->_left = cur;}//这里当父节点存在且为红色时就一直循环//直到父节点不存在或者父节点的颜色为黑色while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//   g// p   uif (parent == grandfather->_left){Node* uncle = grandfather->_right;//叔节点的颜色为红色if (uncle && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else if (uncle == nullptr || uncle->_col == BLACK){if (cur == parent->_left){//    g//  p   u//c//右单旋+变色RevoleR(parent);parent->_col = BLACK;grandfather->_col = RED;}else if (cur == parent->_right){//    g//  p   u//   c//先左单旋，再右单旋，再变色RevoleL(parent);RevoleR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}}else if (uncle == grandfather->_left){//   g// u  pif (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else if (uncle == nullptr || uncle->_col == BLACK){if (cur == parent->_right){//   g// u   p//       c//左单旋+变色RevoleL(parent);parent->_col = BLACK;grandfather->_col = RED;}else if (cur == parent->_left){//   g// u   p//    c//先右单旋，再左单旋，再变色RevoleR(parent);RevoleL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}}}}}_root->_col = BLACK;}
private:void RevoleR(Node* parent) //右单旋{Node* subl = parent->_left;Node* sublr = parent->_left->_right;parent->_left = sublr;if (sublr)sublr->_parent = parent;Node* ppNode = parent->_parent;parent->_parent = subl;subl->_parent = ppNode;if (ppNode == nullptr){_root = subl;}else{if (parent == ppNode->_left){ppNode->_left = subl;}else if (parent->_right){ppNode->_right = subl;}}}void RevoleL(Node* parent)//左单旋{Node* subr = parent->_right;Node* subrl = parent->_right->_left;parent->_right = subrl;if (subrl)subrl->_parent = parent;Node* ppNode = parent->_parent;parent->_parent = subr;subr->_left = parent;subr->_parent = ppNode;if (ppNode == nullptr){_root = subr;}else{if (parent == ppNode->_left){ppNode->_left = subr;}else if (parent == ppNode->_right){ppNode->_right = subr;}}}Node* _root;
};

四、红黑树的查找

红黑树依旧是一个搜索二叉树，它的查找效率仍旧是log N；比AVL略微差一点。

	bool find(const pair<K, V>& kx){Node* tail = _root;while (tail){if (kv.first > tail->_kv.first){tail = tail->_right;}else if (kv.first < tail->_kv.first){tail = tail->_left;}else{return true;}}return false;}

四、红黑树的查找

红黑树依旧是一个搜索二叉树，它的查找效率仍旧是log N；比AVL略微差一点。

	bool find(const pair<K, V>& kx){Node* tail = _root;while (tail){if (kv.first > tail->_kv.first){tail = tail->_right;}else if (kv.first < tail->_kv.first){tail = tail->_left;}else{return true;}}return false;}

五、红黑树验证

说了这么多，现在来看一下如何验证一个树是不是红黑树。

首先去检查最长路经和最短路径是不可行的，因为如果满足最长路径不超过最短路径的2倍，但是颜色也可能不满足规则。

也也能存在问题；

所以我们需要去检查红黑树的四条规则

  • 对于规则一，我们使用枚举常量，就保证了颜色不是黑色就是红色。
  • 规则二，直接检查跟节点颜色即可。
  • 规则三，使用前序遍历检查，遇到红色节点（可能不存在孩子节点，有可能存在一个/两个），非常不方便；这里可以反过来检查，遇到红色节点检查其父节点即可。
  • 规则四，在遍历的过程中，用形参来记录根节点到当前节点的BLACK_num（黑色节点个数），前序遍历遇到黑色节点就++BLACK_num，遍历到空就计算出了一条路径的黑色节点个数，再将任一条路径黑色节点个数作为参考值，依次比较即可。

六、红黑树的删除

对于红黑树的删除，这里暂时不做讨论，等以后再深入研究。

感兴趣的可以参考书籍《算法导论》和《STL源码剖析》。

到这里本篇内容就结束了，希望对你有所帮助。

制作不易，感谢大佬的支持。

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws

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

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

相关文章

SFT数据处理部分的思考

SFT数据处理部分的思考

SFT数据及处理的业内共识 1&#xff0e;prompt的质量和多样性远重要于数据量级&#xff0c;微调一个 30 b 量级的base model只需要 10 w 量级的数据即可 参考&#xff1a;《LIMA&#xff1a;Less Is More for Alignment》 2&#xff0e;合成数据很重要&#xff01;一般需要通过…
阅读更多...
Python（学习一）

Python（学习一）

做网站有成熟的框架像FLASK、DJANGO、TORNADO&#xff0c;写爬虫有好用到哭的REQUESTS&#xff0c;还有强大到没盆友的SCRAPY 随着NUMPY、SCIPY、MATLOTLIB等众多第三方模块的开发和完善&#xff0c;不仅支持py支持各种数学运算&#xff0c;还可以绘制高质量的2D和3D图像&…
阅读更多...
ArcGIS Pro将有文字标注底图切换为无标注底图（在线地图图源）

ArcGIS Pro将有文字标注底图切换为无标注底图（在线地图图源）

今天介绍一下在ArcGIS Pro将有标注的地形底图换成无标注的底图。 大家在这项目底图时候会经常调用ArcGIS Pro自带的地形图&#xff0c;但是这个地形图自带是有注记的&#xff0c;如下图。 如何更改&#xff0c;才可以调用无文字注记的呢&#xff1f; 对于一个已经切好图的有注记…
阅读更多...
Linux第三次练习

Linux第三次练习

1、创建根目录结构中的所有的普通文件 首先在根目录下面新创建一个test目录&#xff0c;然后将查找到的普通文件新建到test目录下 2、列出所有账号的账号名 3、将/etc/passwd中内容按照冒号隔开的第三个字符从大到小排序后输出所有内容 4、列出/etc/passwd中的第20行-25行内容…
阅读更多...
[CISCN 2022 初赛]ezpop（没成功复现）

[CISCN 2022 初赛]ezpop（没成功复现）

打开在线环境可以看到&#xff1a; 记得之前做过一个类似的就是有点像照着漏洞去复现。应该可以直接在网上找到链子去打。 www.zip查看路由是 Index/test&#xff0c;然后 post 传参 a&#xff1a; exp&#xff08;参考了别的大神的wp&#xff09;&#xff1a; <?php //…
阅读更多...
技术-NBIOT

技术-NBIOT

是什么&#xff1f; 窄带物联网&#xff08;Narrow Band Internet of Things, NB-IoT&#xff09;成为万物互联网络的一个重要分支支持低功耗设备在广域网的蜂窝数据连接&#xff0c;也被叫作低功耗广域网(LPWAN)NB-IoT支持待机时间长、对网络连接要求较高设备的高效连接NB-Io…
阅读更多...
Spring @Bean注解使用场景二

Spring @Bean注解使用场景二

bean:最近在写一篇让Successfactors顾问都能搞明白的sso的逻辑的文章&#xff0c;所以一致在研究IAS的saml2.0的协议&#xff0c;希望用代码去解释SP、idp的一些概念&#xff0c;让顾问了解SSO与saml的关系&#xff0c;在github找代码的时候发现一些代码的调用关系很难理解&…
阅读更多...
pip install和conda install的区别

pip install和conda install的区别

这里写目录标题 一、什么是 Python 依赖&#xff08;Python Dependencies&#xff09;&#xff1f;1. 依赖的作用2. 如何管理 Python 依赖3. 依赖管理问题4. 依赖锁定总结 二、使用pip安装包venv隔离环境方法 1&#xff1a;使用 venv&#xff08;推荐&#xff09;创建虚拟环境激…
阅读更多...
R语言高效数据处理-自定义EXCEL数据排版

R语言高效数据处理-自定义EXCEL数据排版

注&#xff1a;以下代码均为实际数据处理中的笔记摘录&#xff0c;所以很零散 1、自定义excel表数据输出格式、布局 在实际数据处理中为了提升效率&#xff0c;将Excel报表交付给需求方时减少手动调整的环节很有必要 #1.1设置表头格式 header_style <- createStyle(font…
阅读更多...
Word 小黑第4套

Word 小黑第4套

对应大猫41 上下日期是一起变动的&#xff0c;删掉第一个&#xff0c;第二个日期格式&#xff08;文件 -选项 -自定义功能区 -选上开发工具&#xff09; 点开发工具 -属性 选择相应的日期格式&#xff09; 修改标题样式时&#xff0c;标题三只有点标题二时才会显示 右击正文样…
阅读更多...
酒店宾馆IPTV数字电视系统：创新宾客体验，引领智慧服务新潮流

酒店宾馆IPTV数字电视系统：创新宾客体验，引领智慧服务新潮流

酒店宾馆IPTV数字电视系统&#xff1a;创新宾客体验&#xff0c;引领智慧服务新潮流 北京海特伟业科技有限公司任洪卓于2025年3月15日发布 随着智慧酒店的不断发展&#xff0c;宾客对于酒店内的娱乐和信息服务需求日益多样化&#xff0c;传统的电视服务已难以满足现代宾客的高…
阅读更多...
jupyter无法转换为PDF，HTMLnbconvert failed: Pandoc wasn‘t found.

jupyter无法转换为PDF，HTMLnbconvert failed: Pandoc wasn‘t found.

无法转为PDF 手动下载工具 https://github.com/jgm/pandoc/releases/tag/3.6.3 似乎跟我想的不大一样&#xff0c;还有新的报错 https://nbconvert.readthedocs.io/en/latest/install.html#installing-tex 不知道下的啥玩意儿 sudo apt-get install texlive-xetex texlive-fon…
阅读更多...
如何在 VS编译器上使用 C99规定的变长数组------使用Clang工具

如何在 VS编译器上使用 C99规定的变长数组------使用Clang工具

VS编译器默认处理代码的工具是 MSVC&#xff0c;而MSVC工具是无法处理变长数组的&#xff0c;这个时候我们就要换一个处理代码的工具了----Clang 1 int n 9; 2 int arr[n];// 数组长度可以拟定1.打开 Visual Stdudio Intaller 2.点击修改&#xff0c;鼠标下滑找到>>使用…
阅读更多...
vue echarts封装使用

vue echarts封装使用

echarts 尺寸自动调节 resize.js 柱状图 components/dashboard/lineChart.vue <template><div :class"className" :style"{height:height,width:width}" /> </template><script> import echarts from echarts require(echarts/…
阅读更多...
《计算机图形学》第二课笔记-----二维变换的推导

《计算机图形学》第二课笔记-----二维变换的推导

前言&#xff1a;为什么这么突兀的把这一节内容放在了第二课&#xff0c;第一是因为我急于求成&#xff0c;第二是因为这一章节太重要了&#xff0c;这几乎是二维三维变换的最核心的东西&#xff0c;理解了这一章节内容&#xff0c;后面的就会像打通了任督二脉一样&#xff0c;…
阅读更多...
OTP单片机调试工具之—单线数据编码

OTP单片机调试工具之—单线数据编码

OTP单片机调试工具在实现过程中离不开单线数据的传输&#xff0c;那么使用哪一种方式的数据编码会比较好呢&#xff1f; 我所了解的主要有以下三种&#xff1a; 1.UART&#xff08;串口&#xff09;&#xff0c;这种方式在单片机和pc之间进行传输都非常常见&#xff0c;效率比较…
阅读更多...
背诵--2

背诵--2

DAY01 面向对象回顾、继承、抽象类 学习目标 能够写出类的继承格式public class 子类 extends 父类{}public class Cat extends Animal{} 能够说出继承的特点子类继承父类,就会自动拥有父类非私有的成员 能够说出子类调用父类的成员特点1.子类有使用子类自己的2.子类没有使用…
阅读更多...
穷举vs暴搜vs深搜vs回溯vs剪枝刷题 + 总结

穷举vs暴搜vs深搜vs回溯vs剪枝刷题 + 总结

文章目录 全排列题解代码 子集题解代码 总结 全排列 题目链接 题解 1. 画一颗决策树 2. 全局变量&#xff1a; int[ ][ ] ret&#xff1a;用于存结果的二维数组 int[ ] path&#xff1a;用于存每次路径的答案 bool[ ] check&#xff1a;判断这个数是否已经用过&#xff0c;…
阅读更多...
深度学习中学习率调整策略

深度学习中学习率调整策略

学习率衰减策略是深度学习优化过程中的一个关键因素&#xff0c;它决定了训练过程中学习率的调整方式&#xff0c;从而影响模型收敛的速度和效果。不同的衰减策略在不同的任务和模型上可能有不同的表现&#xff0c;下面从我用到过的几个衰减策略进行记录&#xff0c;后续慢慢跟…
阅读更多...
《Electron 学习之旅：从入门到实践》

《Electron 学习之旅：从入门到实践》

前言 Electron 简介 Electron 是由 GitHub 开发的一个开源框架&#xff0c;基于 Chromium 和 Node.js。 它允许开发者使用 Web 技术&#xff08;HTML、CSS、JavaScript&#xff09;构建跨平台的桌面应用程序。 Electron 的优势 跨平台&#xff1a;支持 Windows、macOS 和 Linux…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023