【数据结构】红黑树——领略天才的想法

个人主页：东洛的克莱斯韦克-CSDN博客  

祝福语：愿你拥抱自由的风       

目录

二叉搜索树

AVL树

红黑树概述

性质详解

效率对比

旋转操作

元素操作

代码实现

二叉搜索树

【数据结构】二叉搜索树-CSDN博客

AVL树

【数据结构】AVL树——平衡二叉搜索树-CSDN博客

红黑树概述

概念

在二叉搜索树的基础上符合一下性质便是红黑树

每一个节点不是红色就是黑色

根节点一定是黑色

空节点一定是黑色

父亲节点和孩子节点不能是连续的红色节点

每一条根节点至空节点路径上的黑色节点的数量一定相等

​

性质详解

理解路径

红黑树中，一条完整路径不是从叶子节点溯源至根节点，而是从空节点溯源至根节点

​

理解最长和最短路径

如果全是黑色节点，红黑树就是一颗满二叉树，因为每条路径的黑色节点数量相等

​

那么这颗树的每条完整路径都是最短路径，

如果在一条路径上红黑节点间隔（不允许连续的有红色节点），那么该路径为最长路径。

​

红黑树规则

那么最长路径是最短路径的两倍。这便是红黑树的平衡规则。

满二叉树的平衡条件是左右子树高度差为0，AVL树的平衡条件是左右子树高度差小于等于 1，相比于前两棵树平衡条件，红黑树是一种弱平衡。

红黑树和AVL树一样，只要保证自己的平衡规则不被打破，就能使自己不退化为类似于链表的结构。

退化成类似链表的结构——插入的数据接近有序或插入大量的数据不够随机或进行了一些插入删除等操作。

效率对比

查找效率

从直觉上讲，红黑树只是维持一种弱平衡，在最坏情况下，红黑树的高度是AVL树高度的两倍，那么红黑树查找数据的效率也应该比AVL树低两倍才对，为什么我们认为红黑树是一种更优的数据结构呢？下面小编带大家算笔账

2的40次方是一万亿，也就是说用满二叉树存一万亿个数据高度为40。AVL树是有高度差的，所以最坏情况下会查找40多次，而红黑树最坏情况下会找80多次。

那么对于cpu而言，找40多次和找80多次有区别吗？答案是没有的，现在的cpu每秒钟可以运算十亿次甚至几百亿。

可以理解为，在查找数据的效率上AVL树和红黑树是一样的。那么，红黑树的优势在哪里呢？

插入删除效率

不管是红黑树还是AVL树，如果打破平衡都需要旋转这一操作恢复平衡，旋转所付出的时间复杂度为O(1)。对于AVL树而言，需要溯源更新平衡因子，对于红黑树而言，需要溯源更新节点颜色，溯源更新最坏情况下是从叶子节点更新到根节点，所付出的时间复杂度为O(logN)。

因为AVL树的高度差小于等于1，平衡很容易被打破，要维持平衡就需要不断地付出O(1)和O(logN)来维持平衡。

那么红黑树维持弱平衡就不需要总是付出这样地代价，所以红黑树是一种更优的数据结构

旋转操作

旋转操作不是AVL树或红黑树特有的，旋转一次的本质是让二叉搜索树的某棵子树的高度减一。

对于红黑树而言，最长路径是最短路径的二倍加一，就意味着打破平衡，需要通过旋转让最长路径上的某棵子树高度减一来恢复平衡。旋转后需要更新节点的颜色，具体要怎么控制颜色下面细讲，现在看一下旋转操作吧

左单旋：新节点插入较高右子树的右侧——对fathernode

​

void RevolveLeft(node *& fathernode)//左单旋      
{
	node* cur = fathernode->_right; //父亲节点的右孩子
 
	fathernode->_right = cur->_left; //更改指向关系
 
	if (cur->_left != nullptr) //特殊情况
		cur->_left->_FatherNode = fathernode;//更改指向关系
 
	cur->_FatherNode = fathernode->_FatherNode;//更改指向关系
 
	if (fathernode->_FatherNode != nullptr) //为空是特殊情况，
	{
 
		if (fathernode->_FatherNode->_right == fathernode)
		{
			fathernode->_FatherNode->_right = cur;//更改指向关系
		}
		else
		{
			fathernode->_FatherNode->_left = cur;//更改指向关系
		}
 
	}
 
	cur->_left = fathernode;//更改指向关系
 
	fathernode->_FatherNode = cur;//更改指向关系
 
 
}

右单旋：新节点插入较高左子树的左侧——对fathernode

void RevolveRight(node *& fathernode) //右单旋
{
	node* cur = fathernode->_left; //父亲节点的左节点
 
	fathernode->_left = cur->_right;//更新指向关系
 
	if (cur->_right != nullptr) //特殊情况
		cur->_right->_FatherNode = fathernode;//更新指向关系
 
	cur->_FatherNode = fathernode->_FatherNode;//更新指向关系
 
	if (fathernode->_FatherNode != nullptr)//特殊情况
	{
 
		if (fathernode->_FatherNode->_right == fathernode)
		{
			fathernode->_FatherNode->_right = cur;//更新指向关系
		}
		else
		{
			fathernode->_FatherNode->_left = cur;//更新指向关系
		}
 
	}
 
 
	cur->_right = fathernode;//更新指向关系
	fathernode->_FatherNode = cur;//更新指向关系
 
}

​

左右双旋：新节点插入在较高左子树的右侧——先对fathernodeL左单旋再对fathernodeLR右单旋

​

右左双旋：新节点插入再较高右子树的左侧——先对fathernodeR右单旋再对fathernodeRL左单旋

​

元素操作

我们再来理解一下红黑树两条核心性质

父亲节点和孩子节点不能是连续的红色节点

每一条根节点至空节点路径上的黑色节点的数量一定相等

红黑树插入的新节点应该是黑色还是红色呢？

也就是说，插入红色节点可能会破坏第一条性质，插入黑色节点会破坏第二条性质。第一条性质被破坏只影响了当前路径，而第二条性质被破坏影响的是所有路径。所以插入新节点的颜色是红色。

如果新插入节点的父亲节点是黑色，那么不会破坏任何性质，如果新插入节点的父亲节点是红色该怎么办呢？

颜色管理

下面介绍红黑树如何通过管理颜色来判断是否需要旋转，为了方便讨论讨论，给以下节点起个别名，

父亲节点：Father

孩子节点：child（父亲节点的孩子节点）

祖父节点：grandfather（父亲节点的父亲节点）

叔叔节点：uncle（如果父亲节点是祖父节点的左孩子，叔叔节点就是祖父节点的右孩子，反之亦然）

如果新节点的父亲节点为黑，插入成功。如果父亲节点为红，需要溯源更新颜色，规则如下：

如果uncle存在且为红色，Father和uncle变为黑色，grandfather变为黑色，让grandfather变为child，继续溯源更新。

如果更新至整棵树的根节点（Father为空），让根节点置黑，或uncle为空或uncle黑色，停止溯源更新（uncle为空或uncle黑色后面会讨论）。

如果uncle不存在，或uncle存在且为黑，说明红黑树的平衡被打破了，此时就不需要溯源更新颜色了，需要旋转来恢复红黑树的平衡，旋转之后再更新Father，grandfather或child的颜色

右单旋颜色更新：

Father成为了根需要变成黑色节点，Father旋转之前的孩子节点为黑，该孩子会成为grandfather左孩子，grandfather需要变成红节点。

为什么Father旋转之前的孩子节点为黑呢？因为数据是一个一个插入的，新节点只会和一条路径上的父亲节点冲突，如果这是一颗正常的红黑树，Father旋转之前的孩子节点只能为黑色。Father作为根是黑色的，Father的孩子节点也只能是红色的。下面的旋转也一样

左单旋颜色更新：

还是和右单旋一样，Father成了根需要变成黑色，grandfather需要变成红色。

双旋颜色更新：

无论是左右双旋还是右左双旋，最终都是child变成了根，grandfather和Father变成了child的左右孩子，grandfatjie作为孩子需要变成红色。

代码实现

【C++】详解C++的模板-CSDN博客

enum Color { RED, BLACK };    

template <class K>
class RBTreeNode
{
public:

	
	typedef RBTreeNode <K> node_type;   

	K _ky;   
	node_type* _left;
	node_type* _right;
	node_type* _FatherNode;  
	Color _color;

	RBTreeNode(const K& key)
		:_ky(key)
		,_left(nullptr)
		,_right(nullptr)
		, _FatherNode(nullptr)  
		,_color(RED)
	{
	}

};

template <class K> 
class RBTree
{
public:

	typedef RBTreeNode <K> node_type;

	RBTree()
		:_root(nullptr)    
	{
	}

	bool Insert(const K& key)//插入元素     
	{
		//
		//

		if (nullptr == _root) //是否是空树
		{
			_root = new node_type(key);
			_root->_color = BLACK;     
			return true;
		
		}
		//
		node_type* cur = _root;
		node_type* fathernode = nullptr;  
		
		while (cur)
		{
			if (cur->_ky < key)    
			{
				fathernode = cur;  
				cur = cur->_right;
			}
			else if (cur->_ky > key)     
			{
				fathernode = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}

		}


		cur = new node_type(key); //新插入节点 
		if (fathernode->_ky < cur->_ky)    
		{
			fathernode->_right = cur;
			cur->_FatherNode = fathernode;

		}
		else
		{
			fathernode->_left = cur;
			cur->_FatherNode = fathernode;
		}


		while (fathernode && fathernode->_color == RED)  
		{
			node_type* grandfather_node = fathernode->_FatherNode;
			node_type* unclenode = nullptr;

			if (fathernode == grandfather_node->_left) //父亲节点是祖父节点的左孩子
			{
				 unclenode = grandfather_node->_right; //叔叔节点是祖父节点的右孩子

				 if (unclenode == nullptr || unclenode->_color == BLACK)
				 {
					 if (cur == fathernode->_left)  
					 {
						 RevolveRight(fathernode);
						 fathernode->_color = BLACK;
						 grandfather_node->_color = RED; 
					 }
					 else if (cur == fathernode->_right)
					 {
						 RevolveLeft(fathernode);
						 RevolveRight(cur);

						 cur->_color = BLACK;   
						 grandfather_node->_color = RED;     
					 }
				 }
		        else
				{
					fathernode->_color = BLACK; //父亲变黑
					unclenode->_color = BLACK;  //叔叔变黑
					grandfather_node->_color = RED; //爷爷变红
					 
					cur = grandfather_node;
					fathernode = cur->_FatherNode; 
					
				}

			}
			else//父亲节点是祖父节点的右孩子
			{
				unclenode = grandfather_node->_left; //叔叔节点是祖父节点的左孩子       

				if (unclenode == nullptr || unclenode->_color == BLACK)
				{
					if (cur == fathernode->_right)
					{
						RevolveLeft(fathernode);   
						fathernode->_color = BLACK;
						grandfather_node->_color = RED;
					}
					else if (cur == fathernode->_left)
					{
						RevolveRight(fathernode);
						RevolveLeft(cur);     
						
						cur->_color = BLACK;
						grandfather_node->_color = RED;
					}
				}
				else  
				{
					fathernode->_color = BLACK; //父亲变黑
					unclenode->_color = BLACK;  //叔叔变黑
					grandfather_node->_color = RED; //爷爷变红

					cur = grandfather_node;
					fathernode = cur->_FatherNode;
				
				}
			}
			
		  



	
		}


		_root->_color = BLACK;  
		return true;

	}







private:
	void RevolveLeft(node_type*& fathernode)//左单旋        
	{
		node_type* cur = fathernode->_right;  

		fathernode->_right = cur->_left;

		if (cur->_left != nullptr)
			cur->_left->_FatherNode = fathernode;

		cur->_FatherNode = fathernode->_FatherNode;

		if (fathernode->_FatherNode != nullptr)
		{
			if (fathernode->_FatherNode->_right == fathernode)
			{
				fathernode->_FatherNode->_right = cur;
			}
			else
			{
				fathernode->_FatherNode->_left = cur;
			}
		}

		cur->_left = fathernode;
		fathernode->_FatherNode = cur;

	}



	void RevolveRight(node_type*& fathernode) //右单旋 
	{
		node_type* cur = fathernode->_left;  

		fathernode->_left = cur->_right;

		if (cur->_right != nullptr)
			cur->_right->_FatherNode = fathernode;

		cur->_FatherNode = fathernode->_FatherNode;

		if (fathernode->_FatherNode != nullptr)
		{
			if (fathernode->_FatherNode->_right == fathernode)
			{
				fathernode->_FatherNode->_right = cur;
			}
			else
			{
				fathernode->_FatherNode->_left = cur;
			}
		}

		cur->_right = fathernode;
		fathernode->_FatherNode = cur;

	}



	node_type* _root;
};

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

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

相关文章

摸鱼大数据——Hive表操作——基本操作

摸鱼大数据——Hive表操作——基本操作

Hive表操作 Hive乱码解决 1、乱码现象 create database test1 comment "乱码测试"; use test1; CREATE TABLE orders ( orderId bigint COMMENT 订单id, orderNo string COMMENT 订单编号, shopId bigint COMMENT 门店id ); 2、处理步骤 注意&#…
阅读更多...
uniapp页面vue3下拉触底发送获取新数据请求实现分页功能

uniapp页面vue3下拉触底发送获取新数据请求实现分页功能

页面下拉触底获取新数据实现分页功能实现方式有两种&#xff0c;根据自己的业务需求来定&#xff0c;不同的方案适用场景不一样&#xff0c;有的是一整个页面下拉获取新数据&#xff0c;有的是部分盒子内容滚动到底部时候实现获取新数据&#xff0c;下面讨论一下两种方式的区别…
阅读更多...
是他将计算机从“一屋子”变成“一柜子”——量子前哨缅怀小型机之父 戈登·贝尔

是他将计算机从“一屋子”变成“一柜子”——量子前哨缅怀小型机之父 戈登·贝尔

内容来源&#xff1a;量子前哨&#xff08;ID&#xff1a;Qforepost&#xff09; 文丨浪味仙 排版丨沛贤 深度好文&#xff1a;6000字丨15分钟阅读 5 月 21 日&#xff0c; 美国贝尔实验室资深人士 John Mashey 发布消息称&#xff0c;计算机先驱戈登贝尔&#xff08;Gordon…
阅读更多...
精通C++ STL（二）：string类的模拟实现

精通C++ STL（二）：string类的模拟实现

目录 string类各函数接口总览 默认成员函数 构造函数 拷贝构造函数 赋值运算符重载函数 析构函数 迭代器相关函数 begin和end 容量和大小相关函数 size和capacity reserve和resize empty 修改字符串相关函数 push_back append operator insert erase clear swap c_str 访…
阅读更多...
[数据集][目标检测]森林火灾检测数据集VOC+YOLO格式362张1类别

[数据集][目标检测]森林火灾检测数据集VOC+YOLO格式362张1类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;362 标注数量(xml文件个数)&#xff1a;362 标注数量(txt文件个数)&#xff1a;362 标注类别…
阅读更多...
《开发问题解决》Window下7z解压：cannot create symbolic link : 客户端没有所需的特权

《开发问题解决》Window下7z解压：cannot create symbolic link : 客户端没有所需的特权

问题描述&#xff1a; 今天使用7z来解压东西的是突然出现这个问题。 问题解决&#xff1a; download直接下载到c盘中&#xff0c;由于所在文件夹有权限限制。无法进行正常解压。 7.zip解压时使用管理员权限进行解压&#xff0c;解压时使用管理员权限。即如图 使用管理员权限重…
阅读更多...
代码随想录算法训练营第四十一天|动态规划理论基础、509. 斐波那契数列、70. 爬楼梯、746. 使用最小花费爬楼梯

代码随想录算法训练营第四十一天|动态规划理论基础、509. 斐波那契数列、70. 爬楼梯、746. 使用最小花费爬楼梯

动态规划理论基础 什么是动态规划 动态规划&#xff0c;英文&#xff1a;Dynamic Programming&#xff0c;简称DP&#xff0c;如果某一问题有很多重叠子问题&#xff0c;使用动态规划是最有效的。 所以动态规划中每一个状态一定是由上一个状态推导出来的&#xff0c;这一点就…
阅读更多...
android-mvp模式

android-mvp模式

mvvm可以理解成使用databing的mvp模式&#xff0c;modleview 通过接口让view和Presenter层解耦 从图中就可以看出&#xff0c;最明显的差别就是view层和model层不再相互可知&#xff0c;完全的解耦&#xff0c;取而代之的presenter层充当了桥梁的作用&#xff0c;用于操作view…
阅读更多...
技术面‍：前端代码是如何与服务器交互的

技术面‍：前端代码是如何与服务器交互的

前言&#xff1a; 本篇文章主要是想讲解 .html 文件和 .CSS 文件在实际开发中和后端服务器交互最后上线的基础原理。 面向的人群&#x1f195;&#xff1a;是刚入行不久&#xff0c;且目前只会写前端业务代码而不清楚整个工作流的前端新人。我会从 0 开始一步一步带你理解整个…
阅读更多...
Kubernetes(k8s) v1.30.1 本地集群部署 安装metallb 支持LoadBalancer 生产环境 推荐 BGP模式部署

Kubernetes(k8s) v1.30.1 本地集群部署 安装metallb 支持LoadBalancer 生产环境 推荐 BGP模式部署

1 metallb 安装参考:Kubernetes(k8s) v1.30.1 本地集群部署 默认不支持LoadBalancer metallb来解决-CSDN博客 2 删除 Layer 2 模式 配置 kubectl delete -f IPAddressPool.yaml kubectl delete -f L2Advertisement.yaml kubectl delete -f discuz-srv.yaml 3 配置 k8s Metal…
阅读更多...
2024电工杯数学建模B题完整论文讲解（含每一问python代码+数据）

2024电工杯数学建模B题完整论文讲解（含每一问python代码+数据）

大家好呀&#xff0c;从发布赛题一直到现在&#xff0c;总算完成了2024电工杯数学建模B题大学生平衡膳食食谱的优化设计及评价完整的成品论文。 本论文可以保证原创&#xff0c;保证高质量。绝不是随便引用一大堆模型和代码复制粘贴进来完全没有应用糊弄人的垃圾半成品论文。 …
阅读更多...
【Python】 XGBoost模型的使用案例及原理解析

【Python】 XGBoost模型的使用案例及原理解析

原谅把你带走的雨天 在渐渐模糊的窗前 每个人最后都要说再见 原谅被你带走的永远 微笑着容易过一天 也许是我已经 老了一点 那些日子你会不会舍不得 思念就像关不紧的门 空气里有幸福的灰尘 否则为何闭上眼睛的时候 又全都想起了 谁都别说 让我一个人躲一躲 你的承诺 我竟然没怀…
阅读更多...
SQL使用函数给多个分表添加同一字段

SQL使用函数给多个分表添加同一字段

数据库中分表时&#xff0c;往往需要向多个分表中添加同一个字段&#xff0c;可以定义一个函数&#xff0c;每次调用这个函数向多个份表中添加同意字段。 1、创建函数示例&#xff1a; 在PostgreSQL中创建一个简单的函数 以下是一个在PostgreSQL中创建函数的简单示例&#x…
阅读更多...
Mac安装 Intellij IDEA，亲测有效M1、M2可用

Mac安装 Intellij IDEA，亲测有效M1、M2可用

引言 最近开始学习使用spring boot写一个简单的后端项目&#xff0c;使用Intellij IDEA软件&#xff0c;Intellij IDEA为新用户提供了30天的免费试用。 方案 1.官网下载Intellij IDEA IntelliJ IDEA – the Leading Java and Kotlin IDE 或者直接网盘连接下载&#xff1a;…
阅读更多...
OrangePi AIpro开箱评测

OrangePi AIpro开箱评测

开箱评测 有幸受邀参与了CSDN与OrangePi组织的评测活动&#xff0c;今天刚收到快递。拆开快递能看到保护盒、电源、双头typec线这三样&#xff08;充电器和线有保护膜的我先拆掉了&#xff09; 打开保护盒&#xff0c;能看到上下两块黑色海棉包裹的开发板&#xff08;保护得不…
阅读更多...
三、Servlet基础

三、Servlet基础

注&#xff1a;因为我并不完全是为了从0开始Java开发&#xff0c;因此&#xff0c;我这里先暂时跳过第二章服务器环境相关的内容&#xff0c;直接开始第三章的内容。 3.1、Servlet 的基本结构&#xff1a; ​ 下面的代码给出了一个基本的 Servlet &#xff0c;它处理 GET 请求…
阅读更多...
QtXlsx库编译使用

QtXlsx库编译使用

文章目录 一、前言二、Windows编译使用2.1 用法①&#xff1a;QtXlsx作为Qt的附加模块2.1.1 检验是否安装Perl2.1.2 下载并解压QtXlsx源码2.1.3 MinGW 64-bit安装模块2.1.4 测试 2.2 用法②&#xff1a;直接使用源码 三、Linus编译使用3.1、安装Qt5开发软件包&#xff1a;qtbas…
阅读更多...
翻译《The Old New Thing》- Why are INI files deprecated in favor of the registry?

翻译《The Old New Thing》- Why are INI files deprecated in favor of the registry?

Why are INI files deprecated in favor of the registry? - The Old New Thing (microsoft.com)https://devblogs.microsoft.com/oldnewthing/20071126-00/?p24383 Raymond Chen 2007年11月26日 为什么弃用 INI 文件而改用注册表&#xff1f; 欢迎&#xff0c;Slashdot的读…
阅读更多...
【再探】设计模式—职责链模式、命令模式及迭代器模式

【再探】设计模式—职责链模式、命令模式及迭代器模式

行为型设计模式研究系统在运行时对象之间的交互&#xff0c;进一步明确对象的职责。有职责链模式、命令模式、解释器模式、迭代器模式、中介者模式、备忘录模式、观察者模式、状态模式、策略模式、模板方法模式及访问模式共11种。 1 职责链模式 需求&#xff1a;1) 请求能被多…
阅读更多...
2024可信赖的企业级生成式 AI 白皮书

2024可信赖的企业级生成式 AI 白皮书

来源&#xff1a;COPU&IBM&#xff1a; 近期历史回顾&#xff1a;
阅读更多...
最新文章

Copyright @ 2022~2023