【高阶数据结构】红黑树详解

目录

  • 前言
  • 一、红黑树的概念
  • 二、红黑树的性质
  • 三、红黑树节点的定义
  • 四、红黑树的插入
    • 情况1：cur为红，parent为红，grandfather为黑，uncle为红
    • 情况2： cur为红，parent为红，grandfather为黑，uncle不存在或者uncle存在且为黑
      • 1.右单旋
      • 2.左单旋
      • 3.左右单旋
      • 4.右左单旋
  • 五、红黑树与AVL树的比较
  • 六、完整代码

前言

在前面我们学习了平衡二叉树，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现，除了AVL树，下面我们要学习的红黑树也是处理二叉树自身缺陷的一种方式
在这里插入图片描述

一、红黑树的概念

红黑树是一种二叉搜索树，它在每个结点上增加一个存储位表示结点的颜色，可以是红（Red）或黑（Black），通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树能够确保没有任何一条路径的长度会超出其他路径两倍可以（小于等于），所以是接近平衡的。
在这里插入图片描述

二、红黑树的性质

红黑树有几大性质，通过维持这些性质，来保证红黑树最长路径的节点个数不会超过最短路径节点个数的两倍。

  1. 每个节点不是黑色就是红色的
  2. 根节点是黑色的
  3. 如果一个节点是红色的，它的两个孩子节点一定是黑的
    （即：没有连续的红色节点）
  4. 对于每个节点，从该节点到其所有后代叶节点的所有路径上，均包含数量相同的黑色节点
    （即：每条路径都包含相同数量的黑色节点）
  5. 每个叶子节点是黑色的（此处的叶子结点指的是空节点）

我们可以得出：
最长路径为一黑一红
最短路径为全黑

三、红黑树节点的定义

enum Colour
{
	RED,
	BLACK
};

template<class K,class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _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* 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);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
	}
private:
	Node* _root = nullptr;
};

2.检查一下插入新节点后有没有破坏红黑树的性质
我们的新增节点默认是红色
如果新增节点的双亲节点是黑色，则未违反红黑树性质，不需要调整；
如果新增节点的双亲节点是红的，则违反了红黑树的性质（不能有连续的红节点），此时我们需要分情况来调整

为了方便，我们假设cur为当前节点，parent为父节点，grandfather为爷爷节点，uncle为叔叔节点
在这些节点中，叔叔尤为重要，基本上是通过叔叔的状态来控制的

情况1：cur为红，parent为红，grandfather为黑，uncle为红

例如：在这里插入图片描述
注：此处的数可能是一颗完整的树，也可能是一颗子树
我们的解决方法是：将parent，uncle改为黑，grandfather改为红，然后把grandfather当成cur，继续向上调整

在这里插入图片描述
如果grandfather是根节点的话，需要将grandfather变成黑色，因为红黑树的性质（根节点是黑色的）

如果grandfather是子树的话，给就会有父节点，且父节点为红色，然后就以grandfather为cur，继续向上调整
在这里插入图片描述

情况2： cur为红，parent为红，grandfather为黑，uncle不存在或者uncle存在且为黑

1.uncle不存在：这种情况稍微简单一点，如果uncle不存在，说明cur一定是新增节点，则cur和parent定有一个节点是黑色的，就违反了红黑树的性质（每条路径黑色节点个数相同）
在这里插入图片描述
2.uncle存在：如果uncle存在且为黑，那么cur原来就应该是黑的，至于为什么是红的，原因是cur的子树在调整过程中将cur的颜色变成了红色，换句话说，这种情况是一个中间态，是由其他情况调整而变来的
在这里插入图片描述
如果出现了上述情况，我们就需要进行旋转了
旋转的思路我在AVL树中有详细讲解，对旋转不熟悉的可以看看（https://blog.csdn.net/liuty0125/article/details/139563426?spm=1001.2014.3001.5502），下面我就只给出具体代码了

1.右单旋

parent为grandfather的左孩子，cur为parent的左孩子
在这里插入图片描述

if (parent == gradfather->_left)
{
	Node* uncle = gradfather->_right;	
	if (uncle && uncle->_col == RED)//情况1：叔叔存在且为红
	{
		//......
	}
	else//情况2：叔叔不存在或者叔叔存在且为黑
	{
		//右单旋
		if (cur == parent->_left)
		{
			RotateR(gradfather);
			parent->_col = BLACK;
			gradfather->_col = RED;
		}
		//左右双旋
		else
		{
			//......
		}
		break;
	}
}
else
{
	//......
}

2.左单旋

parent为grandfather的右孩子，cur为parent的右孩子

if (parent == gradfather->_left)
{
	//......
}
else
{
	Node* uncle = gradfather->_left;
	//情况1：叔叔存在且为红
	if (uncle && uncle->_col == RED)
	{
		//......
	}
	else//情况2：叔叔不存在或者叔叔存在且为黑
	{
		//左单旋
		if (cur == parent->_right)
		{
			RotateL(gradfather);
			parent->_col = BLACK;
			gradfather->_col = RED;
		}
		//右左双旋
		else
		{
			//......
		}
		break;
	}
}

3.左右单旋

parent为grandfather的左孩子，cur为parent的右孩子
在这里插入图片描述

if (parent == gradfather->_left)
{
	Node* uncle = gradfather->_right;	
	if (uncle && uncle->_col == RED)//情况1：叔叔存在且为红
	{
		//......
	}
	else//情况2：叔叔不存在或者叔叔存在且为黑
	{
		//右单旋
		if (cur == parent->_left)
		{
			//.......
		}
		//左右双旋
		else
		{
			RotateL(parent);
			RotateR(grandfather);
			cur->_col = BLACK;
			gradfather->_col = RED;
		}
		break;
	}
}
else
{
	//......
}

4.右左单旋

parent为grandfather的右孩子，cur为parent的左孩子

if (parent == gradfather->_left)
{
	//......
}
else
{
	Node* uncle = gradfather->_left;
	//情况1：叔叔存在且为红
	if (uncle && uncle->_col == RED)
	{
		//......
	}
	else//情况2：叔叔不存在或者叔叔存在且为黑
	{
		//左单旋
		if (cur == parent->_right)
		{
			//......
		}
		//右左双旋
		else
		{
			RotateR(parent);
			RotateL(grandfather);
			cur->_col = BLACK;
			gradfather->_col = RED;
		}
		break;
	}
}

五、红黑树与AVL树的比较

红黑树和AVL树都是性能十分不错的二叉搜索树，它们的增删查改的时间复杂度都是O(log_n)，

但是红黑树并不像AVL树一样追求绝对平衡，只需要保证最长路径不超过最短路径的两倍，所以相对的降低了插入和旋转的次数，因此在经常需要修改的结构中，红黑树的性能要比AVL树更佳，在实际中红黑树的运用更多。

六、完整代码

#pragma once

enum Colour
{
	RED,
	BLACK
};

template<class K,class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _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* 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);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
		while (parent && parent->_col == RED)
		{
			Node* gradfather = parent->_parent;
			if (parent == gradfather->_left)
			{
				Node* uncle = gradfather->_right;	
				if (uncle && uncle->_col == RED)//情况1：叔叔存在且为红
				{
					parent->_col = uncle->_col = BLACK;
					gradfather->_col = RED;

					//继续往上处理
					cur = gradfather;
					parent = cur->_parent;
				}
				else//情况2：叔叔不存在或者叔叔存在且为黑
				{
					//右单旋
					if (cur == parent->_left)
					{
						RotateR(gradfather);
						parent->_col = BLACK;
						gradfather->_col = RED;
					}
					//左右双旋
					else
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						gradfather->_col = RED;
					}
					break;
				}
			}
			else
			{
				Node* uncle = gradfather->_left;
				//情况1：叔叔存在且为红
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					gradfather->_col = RED;

					//继续往上处理
					cur = gradfather;
					parent = cur->_parent;
				}
				else//情况2：叔叔不存在或者叔叔存在且为黑
				{
					//左单旋
					if (cur == parent->_right)
					{
						RotateL(gradfather);
						parent->_col = BLACK;
						gradfather->_col = RED;
					}
					//右左双旋
					else
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						gradfather->_col = RED;
					}
					break;
				}
			}
		}
		_root = BLACK;

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

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

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

		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subR;
			}
			else
			{
				ppnode->_right = subR;
			}
			subR->_parent = ppnode;
		}
	}
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		subL->_right = parent;

		Node* ppnode = parent->_parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subL;
			}
			else
			{
				ppnode->_right = subL;
			}
			subL->_parent = ppnode;
		}
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;

		_InOrder(root->_left);
		cout << root->_kv.first << endl;
		_InOrder(root->_right);
	}

	void InOrder()
	{
		_InOrder(_root);
	}
private:
	Node* _root = nullptr;
};

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

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

相关文章

GD32C103/GD32C113 CANFD

GD32C103/GD32C113 CANFD

CANFD介绍 FD全称是 Flexible Data-Rate,顾名思义&#xff0c;表示CAN-FD 的帧报文具有数据场波特率可变的特性&#xff0c;即仲裁场合数据控制场使用标准的通信波特率&#xff0c;而到数据场就会切换为更高的通信波特率&#xff0c;车端常用的为2Mbit/s和5Mbit/s,从而达到提高…
阅读更多...
harbor问题总结

harbor问题总结

1. http协议的仓库docker login不上&#xff0c;更改/etc/docker/daemon.json&#xff0c;加一个镜像仓库地址 http: server gave HTTP response to HTTPS client 分析一下这个问题如何解决中文告诉我详细的解决方案-CSDN博客 2. Error response from daemon: login attempt t…
阅读更多...
机器学习笔记 - 用于3D数据分类、分割的Point Net的网络实现

机器学习笔记 - 用于3D数据分类、分割的Point Net的网络实现

上一篇，我们大致了解了Point Net的原理，这里我们要进行一下实现。 机器学习笔记 - 用于3D数据分类、分割的Point Net简述-CSDN博客文章浏览阅读3次。在本文中，我们将了解Point Net，目前，处理图像数据的方法有很多。从传统的计算机视觉方法到使用卷积神经网络到Transforme…
阅读更多...
【spring 】支持spring WebFlux 的容器

【spring 】支持spring WebFlux 的容器

spring WebFlux 是 Spring 5 引入的响应式 Web 框架&#xff0c;它支持非阻塞、事件驱动的编程模型&#xff0c;特别适合处理高并发的场景。 Spring WebFlux 可以运行在多种容器上 包括下面&#xff1a; Netty: Netty 是一个异步事件驱动的网络应用程序框架&#xff0c;用于快…
阅读更多...
WPF/C#：程序关闭的三种模式

WPF/C#：程序关闭的三种模式

ShutdownMode枚举类型介绍 ShutdownMode是一个枚举类型&#xff0c;它定义了WPF应用程序的关闭方式。这个枚举类型有三个成员&#xff1a; OnLastWindowClose&#xff1a;当最后一个窗口关闭或者调用System.Windows.Application.Shutdown方法时&#xff0c;应用程序会关闭。O…
阅读更多...
分布式物联网平台特点

分布式物联网平台特点

随着物联网&#xff08;IoT&#xff09;技术的飞速发展&#xff0c;我们正步入一个万物互联的新时代。在这个时代&#xff0c;设备、数据和服务的无缝集成是实现智能化的关键。分布式物联网平台作为这一进程的核心&#xff0c;正在成为构建智能世界的基石。 一、分布式物联网平…
阅读更多...
【培训】企业档案管理专题（私货）

【培训】企业档案管理专题（私货）

导读&#xff1a;通过该专题培训&#xff0c;可以系统了解企业档案管理是什么、为什么、怎么做。尤其是对档案的价值认知&#xff0c;如何构建与新质生产力发展相适应的企业档案工作体系将有力支撑企业新质生产力的发展&#xff0c;为企业高质量发展贡献档案力量&#xff0c;提…
阅读更多...
IDEA创建简单web(servlet)项目（server为tomcat）

IDEA创建简单web(servlet)项目（server为tomcat）

引言 鉴于网上很少有关于IDEA开发servlet项目的教程&#xff08;24版idea&#xff0c;并且servlet技术十分复古&#xff0c;很少有人用到&#xff0c;能够理解&#xff0c;该文章旨在为在校的学生提供一个参考&#xff0c;项目技术简单&#xff09;本人在此总结从头开始到项目…
阅读更多...
C数据结构：排序

C数据结构：排序

目录 冒泡排序 选择排序 堆排序 插入排序 希尔排序 快速排序 hoare版本 挖坑法 前后指针法 快速排序优化 三数取中法 小区间优化 快速排序非递归 栈版本 队列版本 归并排序 归并排序非递归 ​编辑 计数排序 各排序时间、空间、稳定汇总 冒泡排序 void Bub…
阅读更多...
学习grdecl文件格式之后的事情

学习grdecl文件格式之后的事情

学习了grdecl文件格式&#xff0c;搞地质的专业人士都知道&#xff0c;这是专门用在地质上的油藏软件&#xff08;个人感觉就是斯伦贝谢的Petrel的&#xff09;的一种文件格式&#xff0c;正好自己也在学习三维的开发&#xff0c;顺手写了一个简单的读取grdecl算法&#xff0c;…
阅读更多...
[深度学习]使用python转换pt并部署yolov10的tensorrt模型封装成类几句完成目标检测加速任务

[深度学习]使用python转换pt并部署yolov10的tensorrt模型封装成类几句完成目标检测加速任务

【简单介绍】 使用Python将YOLOv10模型从PyTorch格式&#xff08;.pt&#xff09;转换为TensorRT格式&#xff0c;并通过封装成类来实现目标检测加速任务&#xff0c;是一个高效且实用的流程。以下是该过程的简要介绍&#xff1a; 模型转换&#xff1a; 利用官方提供导出命令…
阅读更多...
Roboflow 图片分类打标

Roboflow 图片分类打标

今天准备找个图片标注工具&#xff0c;在网上搜了一下&#xff0c;看 Yolo 的视频中都是用 Roboflow 工具去尝试了一下&#xff0c;标注确实挺好用的&#xff0c;可以先用一些图片训练一个模型&#xff0c;随后用模型进行智能标注。我主要是做标注然后到处到本地进行模型的训练…
阅读更多...
html是什么？http是什么？

html是什么？http是什么？

html Html是什么&#xff1f;http是什么&#xff1f; Html 超文本标记语言&#xff1b;负责网页的架构&#xff1b; http(&#xff08;HyperText Transfer Protocol&#xff09;超文本传输协议&#xff1b; https&#xff08;全称&#xff1a;Hypertext Transfer Protocol …
阅读更多...
Linux 基本指令2

Linux 基本指令2

cp 指令 cp[选项]源文件 目标文件 将源文件的内容复制到目标文件中&#xff0c;源文件可以有多个&#xff0c;最后一个文件为目标文件&#xff0c;目标文件也可以是一段路径&#xff0c;若目的地不是一个目录的话会拷贝失败。若没有路径上的目录则会新建一个&#xff0c;若源是…
阅读更多...
.NET MAUI Sqlite数据库操作（一）

.NET MAUI Sqlite数据库操作（一）

一、安装 NuGet 包 安装 sqlite-net-pcl 安装 SQLitePCLRawEx.bundle_green 二、配置数据库&#xff08;数据库文件名和路径&#xff09; namespace TodoSQLite; public static class Constants {public const string DatabaseFilename "TodoSQLite.db3";//数据库…
阅读更多...
MonoNodes – LOOK / LAB / PRINT DCTLS 复古美学柯达富士胶片负片模拟电影感DCTL达芬奇插件

MonoNodes – LOOK / LAB / PRINT DCTLS 复古美学柯达富士胶片负片模拟电影感DCTL达芬奇插件

MonoNodes – LOOK / LAB / PRINT DCTLS&#xff0c;我们包装中的“MONOLOOK”DCTL 的灵感来自柯达和富士的经典胶片美学。这些工具提供了三种特定的负片仿真&#xff0c;每种都经过精心设计&#xff0c;以捕捉模拟胶片的独特色彩质量。它们专为希望将胶片的永恒魅力与数字传感…
阅读更多...
文心智能体体验，打造你自己的GPTs应用

文心智能体体验，打造你自己的GPTs应用

利用百度智能体搭建的《RPG冒险游戏大作战》已经发布啦&#xff01; RPG冒险游戏大作战 玩家扮演一位小小勇士女孩&#xff0c;从被巨龙毁灭的冒险小镇出发&#xff0c;一路披荆斩棘&#xff0c;集齐四件神器后&#xff0c;打败巨龙&#xff0c;夺回小镇的安宁&#xff01; 整…
阅读更多...
ESP32s3与Lsm6ds3通信---i2c【开源】

ESP32s3与Lsm6ds3通信---i2c【开源】

接线 ESPS3&#xff0c;I2C的初始化 #ifdef __cplusplus extern "C" { #endif #define I2C_MASTER_SCL_IO CONFIG_I2C_MASTER_SCL /*!< GPIO number used for I2C master clock */ #define I2C_MASTER_SDA_IO CONFIG_I2C_MASTER_SDA …
阅读更多...
深度学习笔记: 最详尽Airbnb租赁搜索排名设计

深度学习笔记: 最详尽Airbnb租赁搜索排名设计

欢迎收藏Star我的Machine Learning Blog:https://github.com/purepisces/Wenqing-Machine_Learning_Blog。如果收藏star, 有问题可以随时与我交流, 谢谢大家&#xff01; Airbnb租赁搜索排名 1. 问题陈述 Airbnb用户在特定地点搜索可用房源。系统应在搜索结果中对多个房源进…
阅读更多...
短剧APP开发，线上观看短剧成为“主流”

短剧APP开发，线上观看短剧成为“主流”

短剧作为一种新型的影视模式&#xff0c;热度持续飙升&#xff0c;受到了大众的欢迎&#xff0c;成为影视行业一个新的风口赛道。短剧时长短、节奏快、剧情爽&#xff0c;在当下快节奏生活中&#xff0c;能够给大众带来娱乐消遣新方式。 短剧题材丰富多样&#xff0c;从总裁、…
阅读更多...
最新文章

Copyright @ 2022~2023