数据结构 —— 红黑树

目录

1. 初识红黑树

1.1 红黑树的概念

 1.2 红⿊树的规则

1.3 红黑树如何确保最长路径不超过最短路径的2倍

1.4 红黑树的效率:O(logN)

2. 红黑树的实现 

2.1 红黑树的基础结构框架

2.2 红黑树的插⼊

2.2.1 情况1：变色

2.2.2 情况2：单旋+变色

2.2.3 情况3：双旋+变色  

2.3 验证一棵树是否为红黑树

2.4 代码汇总

1. 初识红黑树

1.1 红黑树的概念

红⿊树是⼀棵⼆叉搜索树，他的每个结点增加⼀个存储位来表⽰结点的颜⾊，可以是红⾊或者⿊⾊。通过对任何⼀条从根到叶⼦的路径上各个结点的颜⾊进⾏约束，红⿊树确保没有⼀条路径会⽐其他路径⻓出2倍，因⽽是接近平衡的

 1.2 红⿊树的规则

1. 每个结点不是红⾊就是⿊⾊

     
2. 根结点是⿊⾊的

   
3. 如果⼀个结点是红⾊的，则它的两个孩⼦结点必须是⿊⾊的，也就是说任意⼀条路径不会有连续的红⾊结点

     
4. 对于任意⼀个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的⿊⾊结点   

 

1.3 红黑树如何确保最长路径不超过最短路径的2倍

1. 由规则4可知，从根到NULL结点的每条路径都有相同数量的⿊⾊结点，所以极端场景下，最短路径就就是全是⿊⾊结点的路径，假设最短路径⻓度为hb

  

hb:从某个节点出发（不包含该节点）到达一个叶子节点的任意一条简单路径上黑色节点的个数

    
2. 由规则2和规则3可知，任意⼀条路径不会有连续的红⾊结点，所以极端场景下，最⻓的路径就是⼀⿊⼀红间隔组成，那么最⻓路径的⻓度为2*bh

     
3. 综合红⿊树的4点规则⽽⾔，理论上的全⿊最短路径和⼀⿊⼀红的最⻓路径并不是在每棵红⿊树都存在的。假设任意⼀条从根到NULL结点路径的⻓度为x，那么bh <= h <= 2*bh

1.4 红黑树的效率:O(logN)

红⿊树的表达相对AVL树要抽象⼀些，AVL树通过⾼度差直观的控制了平衡。红⿊树通过4条规则的颜 ⾊约束，间接的实现了近似平衡，他们效率都是同⼀档次，但是相对⽽⾔，插⼊相同数量的结点，红⿊树的旋转次数是更少的，因为他对平衡的控制没那么严格

2. 红黑树的实现 

2.1 红黑树的基础结构框架

#pragma once
//定义一个枚举
enum Colour
{
	//枚举里面定义颜色
	RED,
	BLACK
};

//默认按key/value结构实现
template<class K, class V>
struct RBTreeNode
{
	//这⾥更新控制平衡也要加⼊parent指针
	pair<K, V> _kv;
	//也要实现成三叉链
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	Colour _col;

	RBTreeNode(const pair<K, V>& kv) :
		_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
	{}
};

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
private:
	Node* _root = nullptr;
};

2.2 红黑树的插⼊

1. 插⼊⼀个值按⼆叉搜索树规则进⾏插⼊，插⼊后我们只需要观察是否符合红⿊树的4条规则

    

2. 如果是空树插⼊，新增结点是⿊⾊结点。如果是⾮空树插⼊，新增结点必须是红⾊结点，因为⾮空树插⼊，新增⿊⾊结点就破坏了规则4，规则4是很难维护的

     

3. ⾮空树插⼊后，新增结点必须红⾊结点，如果⽗亲结点是⿊⾊的，则没有违反任何规则，插⼊结束

     

4. ⾮空树插⼊后，新增结点必须红⾊结点，如果⽗亲结点是红⾊的，则违反规则3。进⼀步分析，c是红⾊，p为红，g必为⿊，这三个颜⾊都固定了，关键的变化看u的情况，需要根据u分为以下⼏种 情况分别处理

    

说明：下图中假设我们把新增结点标识为c(cur)，c的⽗亲标识为p(parent)，p的⽗亲标识为 g(grandfather)，p的兄弟标识为u（uncle)

2.2.1 情况1：变色

新增结点标识为c(cur)，c的⽗亲标识为p(parent)，p的⽗亲标识为 g(grandfather)，p的兄弟标识为u（uncle)

c为红，p为红，g为⿊，u存在且为红，则将p和u变⿊，g变红，再在把g当做新的c，继续往上更新

    
分析：因为p和u都是红⾊，g是⿊⾊，把p和u变⿊，左边⼦树路径各增加⼀个⿊⾊结点，g再变红，相当于保持g所在⼦树的⿊⾊结点的数量不变，同时解决了c和p连续红⾊结点的问题，需要继续往上更新因为，g是红⾊

   

如果g的⽗亲还是红⾊，那么就还需要继续处理；如果g的⽗亲是⿊⾊，则处理结束了；如果g就是整棵树的根，再把g变回⿊⾊

   

 情况1只变⾊，不旋转。所以⽆论c是p的左还是右，p是g的左还是右，都是上⾯的变⾊处理⽅式

2.2.2 情况2：单旋+变色

c为红，p为红，g为⿊，u不存在或者u存在且为⿊，u不存在，则c⼀定是新增结点

    

u存在且为⿊，则c⼀定不是新增，c之前是⿊⾊的，是在c的⼦树中插⼊，符合情况1，变⾊将c从⿊⾊变成红⾊，更新上来的

分析：p必须变⿊，才能解决，连续红⾊结点的问题，u不存在或者是⿊⾊的，这⾥单纯的变⾊⽆法解决问题，需要旋转+变⾊

如果p是g的左，c是p的左，那么以g为旋转点进⾏右单旋，再把p变⿊，g变红即可。p变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为p的⽗亲是⿊⾊还是红⾊或者空都不违反规则

 

如果p是g的右，c是p的右，那么以g为旋转点进⾏左单旋，再把p变⿊，g变红即可。p变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为p的⽗亲是⿊⾊还是红⾊或者空都不违反规则

2.2.3 情况3：双旋+变色  

c为红，p为红，g为⿊，u不存在或者u存在且为⿊，u不存在，则c⼀定是新增结点

    

u存在且为⿊，则c⼀定不是新增，c之前是⿊⾊的，是在c的⼦树中插⼊，符合情况1，变⾊将c从⿊⾊变成红⾊，更新上来的

分析：p必须变⿊，才能解决，连续红⾊结点的问题，u不存在或者是⿊⾊的，这⾥单纯的变⾊⽆法解决问题，需要旋转+变⾊

如果p是g的左，c是p的右，那么先以p为旋转点进⾏左单旋，再以g为旋转点进⾏右单旋，再把c变⿊，g变红即可。c变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为c的⽗亲是⿊⾊还是红⾊或者空都不违反规则

如果p是g的右，c是p的左，那么先以p为旋转点进⾏右单旋，再以g为旋转点进⾏左单旋，再把c变⿊，g变红即可。c变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为c的⽗亲是⿊⾊还是红⾊或者空都不违反规则 

2.3 验证一棵树是否为红黑树

规则1：枚举颜⾊类型，天然实现保证了颜⾊不是⿊⾊就是红⾊

   

规则2：直接检查根即可

   

规则3：前序遍历检查，遇到红⾊结点查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检 查⽗亲的颜⾊就⽅便多了

    

规则4：前序遍历，遍历过程中⽤形参记录跟到当前结点的blackNum(⿊⾊结点数量)，前序遍历遇到 ⿊⾊结点就++blackNum，⾛到空就计算出了⼀条路径的⿊⾊结点数量。再任意⼀条路径⿊⾊结点数量作为参考值，依次⽐较即可 

bool Check(Node* root, int blacknum, const int retnum)
{
	if (root == nullptr)
	{
		if (blacknum != retnum)
		{
			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, retnum)
		&& Check(root->_right, blacknum, retnum);
}
bool IsBalance()
{
	if (_root == nullptr)
	{
		return true;
	}
 
	if (_root->_col == BLACK)
	{
		return false;
	}
 
	int retnum = 0;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_col == BLACK)
		{
			retnum++;
		}
		cur = cur->_left;
	}
 
	return Check(_root, 0, retnum);
}

2.4 代码汇总

#pragma once
#pragma once
//定义一个枚举
enum Colour
{
	//枚举里面定义颜色
	RED,
	BLACK
};

//默认按key/value结构实现
template<class K, class V>
struct RBTreeNode
{
	//这⾥更新控制平衡也要加⼊parent指针
	pair<K, V> _kv;
	//也要实现成三叉链
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	Colour _col;//颜色

	RBTreeNode(const pair<K, V>& kv) :
		_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
	{}
};

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;
		}
		else
		{
			parent->_left = cur;
		}
		// 链接父亲
		cur->_parent = parent;

		// 父亲存在并且也是红色，当出现连续的红色节点时
		while (parent && parent->_col == RED)
		{
			//找到爷爷节点
			Node* grandfather = parent->_parent;
			//再根据叔叔节点来判断父亲节点的情况
			if (parent == grandfather->_left)
			{
				//	 g
				//p		u
				// 
				//说明u在g的右边
				Node* uncle = grandfather->_right;
				//如果u存在并且u的颜色为红色
				if (uncle && uncle->_col == RED)
				{
					//将u和p的颜色改为黑色，g的颜色改为红色
					uncle->_col = parent->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上处理
					cur = grandfather;
					parent = cur->_parent;//p寻找g的p节点
				}
				else
				{
					if (cur == parent->_left)
					{
						//     g
						//   p    u
						// c
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//      g
						//   p    u
						//     c
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
			else
			{
				//   g
				// u   p
				Node* uncle = grandfather->_left;
				// 叔叔存在且为红，-》变色即可
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else // 叔叔不存在，或者存在且为黑
				{
					// 情况二：叔叔不存在或者存在且为黑
					// 旋转+变色
					//   g
					// u   p
					//       c
					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 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 (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (pParent->_left == parent)
			{
				pParent->_left = subL;
			}
			else
			{
				pParent->_right = subL;
			}

			subL->_parent = pParent;
		}
	}

	//左单旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

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



private:
	Node* _root = nullptr;
};

完结撒花~

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

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

相关文章

Java多线程--Thread类的那些事3.--线程的6中状态和sleep()和 join()

Java多线程--Thread类的那些事3.--线程的6中状态和sleep()和 join()

一.sleep()方法 首先在Thead类中有一个静态的sleep()方法,可以让线程进入到休眠状态即TEMD-WAITING状 在调用sleep()方法时需要注意的是在哪个线程里面调用sleep()方法,哪个线程就会进入阻塞状态.,在这个线程中的其他线程不会发生阻塞, 只有当休眠时间到来这个线程才会继续执行…
阅读更多...
MySQL表设计（三大范式 表的设计）

MySQL表设计（三大范式 表的设计）

1.上讲约束复习&#xff1a; 1.NOT NULL 非空约束&#xff0c;被指定NOT NULL的列&#xff0c;值不允许为空(必填) 2. UNIQUE 唯一约束&#xff0c;这个列里的值在表中是唯一的&#xff0c;也就是说不能重复 3. PRIMARY KEY 主键约束&#xff0c;可以看做是NOT NULL和UNIQUE…
阅读更多...
基于SpringBoot的免税商品优选购物商城的设计与实现

基于SpringBoot的免税商品优选购物商城的设计与实现

一、项目背景 从古至今&#xff0c;通过书本获取知识信息的方式完全被互联网络信息化&#xff0c;但是免税商品优选购物商城&#xff0c;对于购物商城工作来说&#xff0c;仍然是一项非常重要的工作。尤其是免税商品优选购物商城&#xff0c;传统人工记录模式已不符合当前社会…
阅读更多...
RabbitMQ 存储机制

RabbitMQ 存储机制

一、消息存储机制 不管是持久化的消息还是非持久化的消息都可以被写入到磁盘。持久化的消息在到达队列时就被写入到磁盘&#xff0c;非持久化的消息一般只保存在内存中&#xff0c;在内存吃紧的时候会被换入到磁盘中&#xff0c;以节省内存空间。这两种类型的消息的落盘处理都…
阅读更多...
Kafka自动生产消息软件(自动化测试Kafka)

Kafka自动生产消息软件(自动化测试Kafka)

点击下载《Kafka服务端(含Zookeeper)一键自启软件》 点击下载《kafka客户端生产者消费者kafka可视化工具&#xff08;可生产和消费消息&#xff09;》 点击下载《Kafka自动生产消息软件》 1. 前言 在软件开发过程中&#xff0c;Kafka常被用作消息队列来处理特定的业务功能。为…
阅读更多...
C#应用随系统启动 - 开源研究系列文章

C#应用随系统启动 - 开源研究系列文章

上次写过一个随系统启动的例子&#xff0c;不过那个是写到注册表中的&#xff0c;自从更新Windows操作系统后就不好使了&#xff0c;所以就换了个方式&#xff0c;只是将应用的快捷方式添加到操作系统的启动目录里&#xff0c;这样随系统启动。 1、 项目目录&#xff1b; 2、 源…
阅读更多...
大语言模型在交通领域的应用分析

大语言模型在交通领域的应用分析

大语言模型在交通领域的研究进展 前言&#xff1a; 大语言模型&#xff08;Large Language Models, LLMs&#xff09;如 GPT (Generative Pre-trained Transformer) 系列&#xff0c;BERT (Bidirectional Encoder Representations from Transformers) 和其他基于 Transformer …
阅读更多...
快速删除iPhone照片：释放你的空间，加速你的手机

快速删除iPhone照片：释放你的空间，加速你的手机

随着时间的推移&#xff0c;我们的iPhone往往会积累下大量的照片&#xff0c;这不仅占用了大量的存储空间&#xff0c;还可能影响手机的性能。如果你正寻找一种快速、高效的方法快速删除iPhone照片&#xff0c;以下的策略将会大有帮助。此外&#xff0c;本文还将介绍如何利用Cl…
阅读更多...
matlab 质心重合法实现点云配准

matlab 质心重合法实现点云配准

目录 一、算法原理1、原理概述2、参考文献二、代码实现三、结果展示1、初始位置2、配准结果本文由CSDN点云侠原创，原文链接，首发于：2024年11月5日。 一、算法原理 1、原理概述 质心重合法是将源点云 P P P
阅读更多...
MySQL数据库中的视图

MySQL数据库中的视图

视图 ​ 本篇将开始介绍有关数据库中视图的相关知识点&#xff0c;其中主要包含视图的基本使用&#xff0c;视图规则和限制。 ​ 视图是一个虚拟表&#xff0c;其内容由查询定义。同真实的表一样&#xff0c;视图包含一系列带有名称的列和行数据&#xff0c;视图的数据变化会…
阅读更多...
软件测试基础：单元测试与集成测试

软件测试基础：单元测试与集成测试

单元测试的重要性 单元测试是软件开发过程中的必要步骤。它通过针对软件的最小可测试单元进行测试&#xff0c;可以及早发现代码中的逻辑错误和缺陷。根据统计数据显示&#xff0c;单元测试可以在软件开发初期就发现约70%的错误&#xff0c;从而减少了后期修改的成本和时间消耗…
阅读更多...
昆仑通态触摸屏-如何完成几个窗口的切换

昆仑通态触摸屏-如何完成几个窗口的切换

一、启动窗口 想要哪一个窗口是启动时第一个显示的&#xff0c;就把谁设置为启动窗口就可以。 二、公共窗口 给一个窗口命名为公共窗口 然后选择一个窗口&#xff0c;将他的公共窗口设置为我们刚才命名的那个窗口 三、页面切换 页面切换&#xff0c;是通过在公共窗口内设置按…
阅读更多...
修改elementUI等UI组件样式的5种方法总结，哪些情况需要使用/deep/, :deep()等方式来穿透方法大全

修改elementUI等UI组件样式的5种方法总结，哪些情况需要使用/deep/, :deep()等方式来穿透方法大全

文章目录 方法 1：全局修改样式示例：修改 `ElMessage` 的背景色和字体颜色方法 2：修改特定类型的 `ElMessage` 样式-全局-不需要穿透示例：修改 `ElMessage` 成功类型的样式方法 3：通过 Scoped CSS 在组件内部修改-局部-不需要穿透方法 4：使用 JavaScript 动态修改样式-不需…
阅读更多...
SpringBoot中使用SpringTask实现定时任务

SpringBoot中使用SpringTask实现定时任务

SpringBoot默认在无任何第三方依赖的情况下使用spring-context模块下提供的定时任务工具SpringTask。我们只需要使用EnableScheduling注解就可以开启相关的定时任务功能。 定义一个SpringBean&#xff0c;然后定义具体的定时任务逻辑方法并使用Scheduled注解标记该方法即可。…
阅读更多...
CTF中的phar反序列化 [SWPU 2018]SimplePHP

CTF中的phar反序列化 [SWPU 2018]SimplePHP

以[SWPU 2018]SimplePHP 这道题为例 页面可以查看文件和上传文件 点击查看文件,发现url变成/file.php?file 猜测可能存在文件包含,可以读取文件 尝试读取index.php文件 回显了源码 再读取base.php 只看最后有信息的代码: <!--flag is in f1ag.php--> 提示flag在f1…
阅读更多...
车载通信架构 --- PNC、UB与信号的关系

车载通信架构 --- PNC、UB与信号的关系

我是穿拖鞋的汉子，魔都中坚持长期主义的汽车电子工程师。 老规矩，分享一段喜欢的文字，避免自己成为高知识低文化的工程师： 所有人的看法和评价都是暂时的，只有自己的经历是伴随一生的，几乎所有的担忧和畏惧，都是来源于自己的想象，只有你真的去做了，才会发现有多快乐。…
阅读更多...
C++进阶--＞红黑树的实现

C++进阶--＞红黑树的实现

1、红黑树的概念 红黑树是一棵二叉搜索树&#xff0c;他和前面AVL树不同的是红黑树不是通过平衡因子来保证树的平衡&#xff0c;而是在树结点的处加多了个记录颜色的变量&#xff0c;这个变量可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束&…
阅读更多...
微信公众号绑定设计-WeChat public platform bing and send message

微信公众号绑定设计-WeChat public platform bing and send message

一 WeChat bind ui 二、message style 三、 consume style 四、send log 五、temp setting
阅读更多...
Linux多线程(个人笔记)

Linux多线程(个人笔记)

Linux多线程 1.Linux线程概念1.1线程的优点1.2线程的缺点 2.Linux线程VS进程3.Linux线程控制3.1创建线程3.2线程tid及进程地址空间布局3.3线程终止3.4线程等待 4.分离线程5.线程互斥5.1互斥锁mutex5.2互斥锁接口5.3互斥锁实现原理5.4可重入VS线程安全 6.线程同步6.1条件变量6.2…
阅读更多...
Java项目实战II基于Spring Boot的药店管理系统的设计与实现（开发文档+数据库+源码）

Java项目实战II基于Spring Boot的药店管理系统的设计与实现（开发文档+数据库+源码）

目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发&#xff0c;CSDN平台Java领域新星创作者&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。 一、前言 随着医疗行业的快速发展和人们对健康需…
阅读更多...
最新文章

Copyright @ 2022~2023