【进阶数据结构】——红黑树

🌈感谢阅读East-sunrise学习分享——[进阶数据结构]红黑树
博主水平有限,如有差错,欢迎斧正🙏感谢有你 码字不易,若有收获,期待你的点赞关注💙我们一起进步🚀


🌈我们上一篇博客分享了AVL树,但是关于平衡二叉树,还有一个boss在等着你——红黑树
🎄要是说AVL树利用平衡因子实现的方法,是学霸大佬实现的,那红黑树…可就像是一个天才的产物一般✨因为它是如此地天马行空而又独具优异🔴⚫
开始起飞🚀

目录

  • 一、红黑树
    • 1.1 概念
    • 1.2 性质
    • 1.3 红黑树和AVL树的比较
  • 二、红黑树的插入操作
    • 2.1 u存在且为红
    • 2.2 u不存在 / u存在且为黑
      • 单旋调整
      • 双旋调整
  • 三、红黑树的验证

一、红黑树

1.1 概念

红黑树,是一种二叉搜索树,但在每一个节点上增加一个存储位表示节点的颜色,可以是Red或者Black。通过对任何一条从根到叶子的路径上各个节点着色方式的限制,最长路径不超过最短路径的2倍,因而是接近平衡的。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HGV6jb22-1679569401700)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20230323143151723.png)]

1.2 性质

红黑树的性质

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

🔴⚫红黑树的性质较为精华的是其性质3和性质4;性质3就限制了一棵红黑树中没有连续的红色节点;性质4就限制了一棵红黑树中,每条路径上都包含了相同数量的黑色节点

那么这样一来,一棵红黑树中的最短路径最长路径会是什么样的呢?

  • 最短路径:全黑,整条路径都只有黑色节点
  • 最长路径:一黑一红相间的路径

1.3 红黑树和AVL树的比较

💭既然红黑树只是接近平衡,AVL树还是绝对平衡呢,那为什么当下流行的是红黑树呢?

因为红黑树和AVL树都是高效的平衡二叉树,增删查改的时间复杂度都是O(logN),红黑树不追求绝对平衡,其只需要保证最长路径不超过最短路径的2倍。那就意味着红黑树的增删查改最坏的情况就是O(2*logN){但是在复杂度的计算规则中,O(2logN)和O(logN)是同一个量级的};那可能在最坏情况下红黑树查找所花的次数是AVL树的2倍呗🎄

但是相对而言,红黑树放松了平衡的要求也就意味着降低了插入和旋转的次数旋转插入也是需要花费代价的。假如你现在插入了一亿个数,查找的时候AVL树可能需要30次,红黑树最多也就60次;但是在插入的过程中,红黑树能够比AVL树少百分之三十的旋转次数;因此在经常进行增删查改的结构中,红黑树的性能是优于AVL树的,而且红黑树实现也较为简单,所以实际中红黑树用的比较多🔴⚫

话不多说,开始我们今天的模拟实现红黑树🎄

二、红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件,因此红黑树的插入可分为两步:

  1. 按照二叉搜索的树规则插入新节点
  2. 检测新节点插入后,红黑树的性质是否造到破坏

当我们要插入时,随之便迎来了第一个问题
📌新插入的节点要设为红色还是黑色呢?

答案是新节点的默认颜色是红色,因此:如果其父节点的颜色是黑色,没有违反红黑树任何性质,则不需要调整;但当新插入节点的父节点颜色为红色时,就违法了性质三(不能有连续在一起的红色节点),此时便需要开始对红黑叔进行处理

假如新节点的默认颜色是黑色,则不论如何,插入之后必定会违反红黑树的性质四(每条路径都有相同数量的黑色节点);而假如新节点默认颜色是红色,只是有几率违反红黑树的性质🎯因此默认选择红色

当新插入节点的父节点为红时,需要开始对红黑树进行调整🚩
约定:cur为当前节点,p为父节点,g为祖父节点,u为叔叔节点

此时我们发现,需要对红黑树进行调整时:cur为红节点,p也为红节点,那此时只有u是不确定的
所以调整红黑树的关键就在于u节点的情况;根据u节点的不同情况我们分出了几种调整情况

2.1 u存在且为红

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-akhYG3gA-1679569401701)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20230322135427975.png)]

🎯解决方法:将p、u改为黑,g改为红,然后把g当成cur,迭代继续向上更新

2.2 u不存在 / u存在且为黑

🎄这里将u的两种情况合为一种大情况是因为,u的情况不影响我们的调整方法

单旋调整

1️⃣当u节点不存在

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LqEKrXI0-1679569401702)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20230322141716037.png)]

💭值得思考的是:以上这种u节点不存在的情况,cur一定是新插入的节点;因为如果cur不是新插入节点,则cur和p一定要有一个是黑色节点,否则违反了性质3,而倘若cur和p有一个是黑色节点,则又违反了性质4;所以此情况只有是cur为新节点刚插入的(a、b子树为空)

2️⃣当u节点存在且为黑

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-u6G6YwcM-1679569401702)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20230322142533006.png)]

💭值得思考的是:当u存在且为黑这种情况,cur节点一定不是新插入的节点并且其原来是黑色;假若不是的话,则违背了性质4;所以如图的情况是cur的子树在调整之后将cur节点的颜色由黑色变为红色

综上所述,虽然u节点有两种情况,但是不论如何都是一种调整操作:

  1. 单旋:以g为轴点进行一次右单旋
  2. 变色:p变黑,g变红

上图只画出了p为g的左孩子一种情况,若p为g的右孩子,则同理并进行左单旋

双旋调整

1️⃣当u不存在

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xYuxG5lK-1679569401702)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20230322144355417.png)]

2️⃣当u节点存在且为黑

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oePmOGDO-1679569401702)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20230322212444207.png)]

综上所述,虽然u节点有两种情况,但是不论如何都是一种调整操作:

  1. 双旋:先以p为轴点进行一次左单旋,再以g为轴点进行一次右单旋
  2. 变色:p变黑,g变红

⭕上图只画出了p为g的左孩子一种情况,若p为g的右孩子,则同理并进行右左双旋


有的兄弟会发现,上图的两个情况2️⃣调整后好像路径中的黑色节点并不相同;这是因为情况2️⃣只存在与cur节点也有子树的情况下,所以cur并不是路径的终点,并不会违反性质4的

在2.2这个情况中,我们发现最后经过旋转+变色,根节点是黑色了,也就是说不会对其祖先造成任何违反性质的影响因此经过旋转+变色处理后便不需要再迭代向上更新了…这些归纳和细节在我们的代码实现时均需要体现✏️✏️

代码实现✏️

enum Color
{
	RED,
	BLACK,
};

template<class K, class V>
struct RBTreeNode
{
	pair<K, V> _kv;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	Color _col;


	RBTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _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;
		}

		//调整红黑树 
		while (parent && parent->_col == RED)//当parent为空则是在创建根节点
		{
			Node* grandfather = parent->_parent; //要找到祖父才能找到叔叔
			if (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 (cur == parent->_left)
					{
						//单旋
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//双旋
						RotateL(parent);
						RotateR(grandfather);

						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else
			{
				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)
					{
						//单旋
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//双旋
						RotateR(parent);
						RotateL(grandfather);

						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;//不论如何根都为黑色

		return true;
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;

		if (subRL)
			subRL->_parent = parent;

		Node* pparent = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;

		if (pparent)
		{
			if (parent == pparent->_left)
				pparent->_left = subR;
			else
				pparent->_right = subR;
			subR->_parent = pparent;
		}
		else
		{
			_root = subR;
			subR->_parent = nullptr;
		}
	}

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;

		if (subLR)
			subLR->_parent = parent;

		Node* pparent = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;

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

private:
	Node* _root = nullptr;
};

三、红黑树的验证

红黑树的验证分为两步:

  1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
  2. 检测其是否满足红黑树的性质

🔴⚫对于红黑树的验证,较为费脑的就是其性质3和性质4

验证性质3还行,就递归遍历检查每个节点的颜色,是否会连续为红
但是验证性质4,也就是需要知道每个路径的黑色节点数量💭一开始博主准备直接在红黑树节点中再增加一个变量用于标记从根到每个节点的黑色节点数;但是觉得这样未免太过杀鸡用牛刀了…接着博主就想到了利用递归:在递归的时候增加一个值传递,注意是值传递不是引用传递变量;如此一来,在递归遍历时每一个函数栈帧都会有一个变量记录了此层递归的节点路径上有多少个黑色节点,然后因为递归遍历能够将整颗树走完(走到空),所以当走到空时便能将此路径的黑色节点记录下来;然后找个容器将每条路径的黑色节点总数记录起来再比较即可🎯

最后博主想着不想再增加其空间复杂度,既然要求每个路径黑色节点需要相同,那么我们可以在检查时先直接迭代统计一条路径的黑色节点数量作为一个参考值,之后在检查时每条路径的黑色节点数与参考值比较即可🔴⚫

✏️上代码

void _Inorder(Node* root)
{
	if (root == nullptr)
		return;

	_Inorder(root->_left);
	cout << root->_kv.first << ":" << root->_kv.second << endl;
	_Inorder(root->_right);
}

bool Check(Node* root, int BlackNum, int ref)
{
	if (root == nullptr)
	{
		if (BlackNum != ref)
		{
			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, ref) && Check(root->_right, BlackNum, ref);
}

bool isBalance()
{
	if (_root == nullptr)
		return true;

	if (_root->_col != BLACK)
		return false;
		
	int ref = 0;
	Node* left = _root;
	while (left)
	{
		if (left->_col == BLACK)
			++ref;
		left = left->_left;
	}

	return Check(_root,0,ref);
}

🌈🌈写在最后 我们今天的学习分享之旅就到此结束了
🎈感谢能耐心地阅读到此
🎈码字不易,感谢三连
🎈关注博主,我们一起学习、一起进步

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

SpringCloud之 LoadBalancer和Feign负载均衡

文章目录LoadBalancer 负载均衡一、LoadBalanced 负载均衡&#x1f33d;①观察负载均衡现象&#x1f33d;②LoadBalanced 源码剖析二、自定义负载均衡三、OpenFeign 实现负载均衡&#x1f346;①添加依赖&#x1f346;②启动类添加 EnableFeignClients&#x1f346;③创建客户端…

MySQL的COUNT语句,竟然都能被面试官虐的这么惨!?

关于数据库中行数统计&#xff0c;无论是MySQL还是Oracle&#xff0c;都有一个函数可以使用&#xff0c;那就是COUNT 但是&#xff0c;就是这个常用的COUNT函数&#xff0c;却暗藏着很多玄机&#xff0c;尤其是在面试的时候&#xff0c;一不小心就会被虐。不信的话请尝试回答下…

一文了解Jackson注解@JsonFormat及失效解决

背景 项目中使用WRITE_DATES_AS_TIMESTAMPS: true转换日期格式为时间戳未生效。如下&#xff1a; spring:jackson:time-zone: Asia/Shanghaiserialization:WRITE_DATES_AS_TIMESTAMPS: true尝试是否关于时间的注解是否会生效&#xff0c;使用JsonForma和JsonFiled均失效。 常…

【Docker】CAdvisor+InfluxDB+Granfana容器监控

文章目录原生命令 docker stats容器监控3剑客CIGCAdvisorInfluxDBGranfanacompose容器编排&#xff0c;一套带走新建目录新建3件套组合的 docker-compose.yml检查配置&#xff0c;有问题才有输出 docker-compose config -q启动docker-compose文件 docker-compose up -d测试浏览…

HTML5 Canvas

HTML5 Canvas <canvas>元素是HTML5中的新元素&#xff0c;通过使用该元素&#xff0c;你可以在网页中绘制所需的图形。 标签定义图形&#xff0c;比如图表和其他图像&#xff0c;您必须使用脚本来绘制图形。在画布上&#xff08;Canvas&#xff09;画一个红色矩形&#…

Java基础知识之HashMap的使用

一、HashMap介绍 HashMap是Map接口的一个实现类&#xff08;HashMap实现了Map的接口&#xff09;&#xff0c;它具有Map的特点。HashMap的底层是哈希表结构。 Map是用于保存具有映射关系的数据集合&#xff0c;它具有双列存储的特点&#xff0c;即一次必须添加两个元素&#xf…

5个高清/4K视频素材网站,免费下载。

本期跟大家分享5个超好用的视频素材网站&#xff0c;4K质量&#xff0c;免费可商用。 1、菜鸟图库 https://www.sucai999.com/video.html?vNTYwNDUx 菜鸟图库主要提供设计素材为主&#xff0c;自媒体相关素材也很多&#xff0c;像商用图片、背景图、视频素材、音频素材都很齐…

算法刷题总结 (二) 回溯与深广搜算法

算法总结2 回溯与深广搜算法一、理解回溯算法1.1、回溯的概念1.2、回溯法的效率1.3、回溯法问题分类1.4、回溯法的做题步骤二、经典问题2.1、组合问题2.1.1、77. 组合 - 值不重复2.1.2、216.组合总和III - 值不重复且等于目标值2.1.3、17. 电话号码的字母组合 - 双层回溯2.1.4、…

KafKa知识汇总

前言 汇总相关知识 Kafka快速实战与基本原理详解

LeetCode:215. 数组中的第K个最大元素

&#x1f34e;道阻且长&#xff0c;行则将至。&#x1f353; &#x1f33b;算法&#xff0c;不如说它是一种思考方式&#x1f340;算法专栏&#xff1a; &#x1f449;&#x1f3fb;123 一、&#x1f331;215. 数组中的第K个最大元素 题目描述&#xff1a;给定整数数组nums和整…

Django 之 Cookie 和 Session

3. Cookie 和 Session 会话 因为 HTTP 协议是无状态的&#xff0c;每次浏览器请求 request都是无状态的&#xff0c;后台服务器无法识别当前请求与上一次请求及之后请求是否为同一用户。 对于静态网站来说无所谓&#xff08;所有用户看到的都是一样的&#xff09;&#xff0c…

【C++】引用详细解析

目录引用的概念引用的用法引用的特性常引用&#xff08;涉及权限的放大与缩小&#xff09;引用的使用场景**作参数****作返回值**正确使用引用返回传值、传引用效率比较引用和指针的区别引用的概念 引用不是新定义一个变量&#xff0c;而是给已存在变量取了一个别名&#xff0…

干货 | 开关电源的PCB布线设计技巧—如何降低EMI?

开关电源PCB排版是开发电源产品中的一个重要过程。许多情况下&#xff0c;一个在纸上设计得非常完美的电源可能在初次调试时无法正常工作&#xff0c;原因是该电源的PCB排版存在着许多问题。为了适应电子产品飞快的更新换代节奏&#xff0c;产品设计工程师更倾向于选择在市场上…

【Zblog建站】搭建属于自己的博客网站,并内网穿透实现公网访问

文章目录1. 前言2. Z-blog网站搭建2.1 XAMPP环境设置2.2 Z-blog安装2.3 Z-blog网页测试2.4 Cpolar安装和注册3. 本地网页发布3.1. Cpolar云端设置3.2 Cpolar本地设置4. 公网访问测试5. 结语1. 前言 想要成为一个合格的技术宅或程序员&#xff0c;自己搭建网站制作网页是绕不开…

第十四届蓝桥杯三月真题刷题训练——第 20 天

目录 第 1 题&#xff1a;纸张尺寸 问题描述 输入格式 输出格式 样例输入1 样例输出1 样例输入 2 样例输出 2 运行限制 代码&#xff1a; 解析&#xff1a; 第 2 题&#xff1a;最大数字 第 3 题&#xff1a;全排列的价值_递推公式 问题描述 输入格式 输出格式…

【中级软件设计师】—操作系统考点总结篇(二)

【中级软件设计师】—操作系统考点总结篇&#xff08;二&#xff09; 1.操作系统概述 1.1操作系统的功能 1.2 特殊的操作系统 1.3 进程的概念和状态 进程与程序的区别&#xff1a; 进程是程序的一次执行过程&#xff0c;没有程序就没有进程 程序是一个静态的概念&#xff0c;…

flowable-ui

一、介绍 flowable-ui主要用于画流程图,之后再使用flowable整合Spring Boot。Flowable提供了一个web UI应用程序来演示和利用Flowable项目提供的功能。 flowable-ui的官网文档地址为: https://www.flowable.com/open-source/docs/bpmn/ch14-Applications/ 二、安装flowab…

Counterpoint发布颈戴式耳机市场报告,苹果Find My加持不易丢

根据市场调查机构 Counterpoint 公布的 2022 年第 4 季度报告&#xff0c;一加凭借着 20.2% 的市场占有率&#xff0c;成为印度市场最大的颈戴式耳机市场厂商。 一加以 20.2% 的市场占有率领先&#xff0c;boAt 以 16% 的份额位居第二。一加云耳 Z2 已经连续 3 个季度成为印度…

【CodeForces】Codeforces Round 859 (Div. 4) D

嘿嘿嘿&#xff0c;CF虐我千百遍&#xff0c;我待CF如初见&#xff01; &#xff08;doge&#xff09; 目录 题目含义&#xff1a; 前缀和&#xff1a; 代码 &#x1f386;音乐分享&#xff08;点击链接可以听哦&#xff09; A Hundred Miles&#xff08;一百英里&#xff09;…

JDBC——Java数据库连接

文章目录一、数据库工具类二、JDBC—— Java数据库连接三、执行DML语句四、执行DQL语句五、关联查询六、执行预编译SQL语句七、SELECT语句八、练习创建表:student1九、向student1表中插入100条数据十、删除名字为Test20---Test100的学生十一、将student1表中所有test学生的年龄…
最新文章