C++之红黑树模拟实现

目录

红黑树的概念

红黑树的性质

红黑树的查找效率

红黑树的实现 

红黑树的定义

红黑树节点的插入

红黑树的平衡调整

判断红黑树是否平衡 

红黑树整体代码 

测试代码

上期我们学习了AVL树的模拟实现，在此基础上，我们本期将学习另一个数据结构------红黑树。我们知道，AVL树的插入伴随着节点的旋转，那么红黑树是否在插入节点时也要进行旋转呢？这便是我们本期要学习的内容。

红黑树的概念

红黑树和AVL树一样，也是一种二叉搜索树，红黑树的每一个节点存储一个数据，表示该节点的颜色，为红色或者黑色。通过红黑树的性质作为约束，红黑树的最长路径的长度不会超过最短路径长度的二倍。红黑树图示如下。

红黑树的性质

  1. 红黑树的节点，不是红色就是黑色。
  2. 红黑树的根节点一定是黑色的。
  3. 红黑树中，如果一个节点是红色的，那么它的孩子节点一定是黑色的。（也就是说，红黑树中不能出现连续的两个红色节点）
  4. 红黑树的任意一个节点到其所有叶子节点的所有路径上的黑色节点的个数一定是相同的。
  5. 红黑树的叶子节点一定是黑色的。（这个叶子节点不是传统意义的叶子节点，而是如上图所示的NIL空节点）

 Q1:为什么通过红黑树的上述性质作为约束，能够保证红黑树的最长路径的长度不超过最短路径长度的2倍呢？

A1:其实决定上述条件的是红黑树性质中的3和4条。假设红黑树的每个路径的黑色节点的个数是4，极端情况下，红色树的最短路径就是4个黑色节点，最长路径就是1黑1红，总共4组，8个节点，所以就可以推出，红黑树的最长路径的长度不超过最短路径长度的2倍。

红黑树的查找效率与AVL树的比较

再学习AVL树时，我们知道了AVL树理想条件下其实就是一颗完全二叉树，所以对于有N个节点的完全二叉树，它的高度为logN，所以对于AVL树而言，它的查找效率是logN。

对于红黑树而言，假设红黑树的每条路径的黑色节点的个数为X，所以红黑树的高度h的范围为X<=h<=2X。假设红黑树的节点的个数为N，则N的范围为2^X-1<=N<=2^2X-1,从而得到X的取值范围为1/2logN<=X<=logN。所以对于具有N个节点的红黑树而言，红黑树的高度最高为2logN，红黑树也是搜索二叉树，所以红黑树的查找效率为2logN。

通过上述比较，不难看出，红黑树的查找效率远不及AVL树，所以我们应该是经常使用AVL树的。嗯？真的是我们想的这样吗，真的是AVL树的使用更为广泛吗？

实际上并不是这样，AVL树的查找效率固然很高，但是查找效率高的同时带来的代价也是很大的，因为AVL是高度平衡的二叉树，有时候插入一个元素往往需要旋转多次，但是对于红黑树而言，只要插入的节点的颜色不违反红黑树的性质，我们是不用进行旋转的。我们可以认为，AVL树和红黑树在插入节点时，AVL树中插入节点更容易违反性质，所以AVL插入元素时旋转的概率是远远比红黑树要高的，所以即使AVL树的查找效率更高，但是对于以数亿次运算的CPU看来，logN和2logN几乎是没有差异的，所以一般情况下，我们应用红黑树的场景更多。

红黑树的实现 

红黑树的定义

代码如下。

//枚举类型，代表红黑树节点的颜色。
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:
	RBTree()
		:_root(nullptr)
	{}


private:
	Node* _root;

};

红黑树节点的插入

查找合适的位置进行节点的插入，代码如下。

//如果当前红黑树为空，则直接插入即可
		if (_root == nullptr)
		{
			_root = new Node(pair);
			_root->_col = BLACK;
			return true;
		}

		//如果当前红黑树不为空，就要先找到合适的位置，然后进行节点的插入
		Node* cur = _root;
		Node* parent = _root->_parent;
		while (cur)
		{
			if (cur->_kv.first > pair.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < pair.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
				printf("插入的节点的值已经存在于红黑树中，不允许插入!\n");
			}
		}
		cur = new Node(pair);
		cur->_col = RED;
		cur->_parent = parent;
		if (cur->_kv.first > parent->_kv.first)
		{
		 parent->_right= cur ;
	
		}
		else
		{
		 parent->_left= cur ;
		}

红黑树的平衡调整

在插入一个结点时，为了对整个红黑树的影响最小，一般我们插入的都是红色节点。但是在插入红色节点时，可能会遇到很多情景，大致分为三种。

我们将插入的节点称为cur节点，将cur节点的父亲称为parent节点，将cur节点的叔叔称为uncle节点，将cur节点的祖父称为grandfather节点。在此基础上我们展开分析。

情景1：uncle节点存在且为红。

代码如下。 

情景2和3，uncle节点存在为黑色或者uncle节点不存在。

 代码如下。

	while (parent&& parent->_col == RED)
		{

			Node* grandfather = parent->_parent;
			//1.叔叔节点都存在，且都为红色节点，就要进行颜色平衡
			if (parent == grandfather->_right)
			{
				Node* uncle = grandfather->_left;
				if (uncle&& uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
			//2.叔叔节点不存在
			//3.叔叔节点的颜色为黑色
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;

				}

			}
			else
			{
				Node* uncle = grandfather->_right;
				if (uncle&& uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					//2.叔叔节点不存在
					//3.叔叔节点的颜色为黑色
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;

				}
			}

判断红黑树是否平衡 

代码如下。

bool IsBalance()
	{
		if (_root && _root->_col == RED)
		{
			cout<<"根节点的颜色是红色，不符合红黑树的性质";
			return false;
		}
		
		int banchmark = 0;
		//选取最左侧的路径的黑色节点的个数为基准值
		Node* left = _root;
		while (left)
		{
			if (left->_col == BLACK)
			{
				banchmark++;
			}
				left = left->_left;
		 }

		int blackcount = 0;
		return _IsBalance(_root, banchmark, blackcount);
	}

	bool _IsBalance(Node* root, int banchmark, int blackcount)
	{
		if (root == nullptr)
		{
			if (banchmark != blackcount)
			{
				return false;
			}
			
				return  true;
			
		}

		if (root->_col == RED && root->_parent->_col == RED)
		{
		cout<<"出现两个连续的红节点，不符和红黑树的性质" << endl;
		return false;
		}
		if (root->_col == BLACK)
		{
			blackcount++;
		}

		return _IsBalance(root->_left, banchmark, blackcount) && _IsBalance(root->_right,banchmark, blackcount);
	}

红黑树整体代码 

 红黑树实现代码如下。

#include<time.h>
#include<iostream>
#include<vector>
using namespace std;

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:
	RBTree()
		:_root(nullptr)
	{}


	//红黑树节点的插入
	bool Insert(const pair<K, V>& pair)
	{
		//如果当前红黑树为空，则直接插入即可
		if (_root == nullptr)
		{
			_root = new Node(pair);
			_root->_col = BLACK;
			return true;
		}

		//如果当前红黑树不为空，就要先找到合适的位置，然后进行节点的插入
		Node* cur = _root;
		Node* parent = _root->_parent;
		while (cur)
		{
			if (cur->_kv.first > pair.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < pair.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
				printf("插入的节点的值已经存在于红黑树中，不允许插入!\n");
			}
		}
		cur = new Node(pair);
		cur->_col = RED;
		cur->_parent = parent;
		if (cur->_kv.first > parent->_kv.first)
		{
		 parent->_right= cur ;
	
		}
		else
		{
		 parent->_left= cur ;
		}
		

		//调整平衡
	
		while (parent&& parent->_col == RED)
		{

			Node* grandfather = parent->_parent;
			//1.叔叔节点都存在，且都为红色节点，就要进行颜色平衡
			if (parent == grandfather->_right)
			{
				Node* uncle = grandfather->_left;
				if (uncle&& uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
			//2.叔叔节点不存在
			//3.叔叔节点的颜色为黑色
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;

				}

			}
			else
			{
				Node* uncle = grandfather->_right;
				if (uncle&& uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					//2.叔叔节点不存在
					//3.叔叔节点的颜色为黑色
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateL(parent);
						RotateR(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* parentParent = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;

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

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

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

		Node* parentParent = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

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

			subL->_parent = parentParent;
		}
	}


	void InOrder()
	{
		_InOrder(_root);
	}

	void _InOrder(Node* root)
	{
		if (root == NULL)
			return;

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

private:
	Node* _root;

};

测试代码

void TestRBTree()
{
	RBTree<int, int> t;
	vector<int> v;
	srand(time(0));
	int N = 10;
	for (int i = 0; i < N; ++i)
	{
		v.push_back(rand());
	}

	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	
	}
	t.InOrder();
	cout<< t.IsBalance() << endl;

}

运行结果如下。

运行结果符合预期。 

以上便是红黑树的所有内容，较于AVL树，红黑树的应用较为广泛，后续的容器map和set以及哈希结构都是使用红黑树实现的。这些都是我们下几期要重点研究的。 

本期内容到此结束^_^

 

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

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

相关文章

机器学习常用术语

机器学习常用术语

目录 概要 机器学习常用术语 1、模型 2、数据集 3、样本与特征 4、向量 5、矩阵 6、假设函数与损失函数 7、拟合、过拟合与欠拟合 8、激活函数(Activation Function) 9、反向传播(Backpropagation) 10、基线(Baseline) 11、批量(Batch) 12、批量大小(Batch Size)…
阅读更多...
nest 学习3

nest 学习3

学习小册(nest通关秘籍) 邮箱验证码登陆 流程图&#xff1a; 邮箱作为key&#xff0c;生成随机验证码&#xff0c;然后放到redis中。调用邮箱api发送邮箱。 前端获取到code后&#xff0c;将验证码输入传给后端&#xff0c;后端根据邮箱取出redis数据&#xff0c;比对验证码&…
阅读更多...
原点安全再次入选信通院 2024 大数据“星河”案例

原点安全再次入选信通院 2024 大数据“星河”案例

近日&#xff0c;中国信息通信研究院和中国通信标准化协会大数据技术标准推进委员会&#xff08;CCSA TC601&#xff09;共同组织开展的 2024 大数据“星河&#xff08;Galaxy&#xff09;”案例征集活动结果正式公布。由工银瑞信基金管理有限公司、北京原点数安科技有限公司联…
阅读更多...
RabbitMQ 的7种工作模式

RabbitMQ 的7种工作模式

RabbitMQ 共提供了7种⼯作模式,进⾏消息传递,. 官⽅⽂档:RabbitMQ Tutorials | RabbitMQ 1.Simple(简单模式) P:⽣产者,也就是要发送消息的程序 C:消费者,消息的接收者 Queue:消息队列,图中⻩⾊背景部分.类似⼀个邮箱,可以缓存消息;⽣产者向其中投递消息,消费者从其中取出消息…
阅读更多...
Restaurants WebAPI（四)——Identity

Restaurants WebAPI（四)——Identity

文章目录 项目地址一、Authentication&#xff08;身份认证&#xff09;1.1 配置环境(解决类库包无法引用)1.2 使用Authentication控制Controller的访问1.3 获取User的Context1.3.1 在Application下创建User文件夹1. 创建User.cs record类封装角色信息2. 创建UserContext.cs提供…
阅读更多...
010 Qt_输入类控件(LineEdit、TextEdit、ComboBox、SpinBox、DateTimeEdit、Dial、Slider)

010 Qt_输入类控件(LineEdit、TextEdit、ComboBox、SpinBox、DateTimeEdit、Dial、Slider)

文章目录 前言一、QLineEdit1.简介2.常见属性及说明3.重要信号及说明4.示例一&#xff1a;用户登录界面5.示例二&#xff1a;验证两次输入的密码是否一致显示密码 二、TextEdit1.简介2.常见属性及说明3.重要信号及说明4.示例一&#xff1a;获取多行输入框的内容5.示例二&#x…
阅读更多...
Vue3：uv-upload图片上传

Vue3：uv-upload图片上传

效果图&#xff1a; 参考文档&#xff1a; Upload 上传 | 我的资料管理-uv-ui 是全面兼容vue32、nvue、app、h5、小程序等多端的uni-app生态框架 (uvui.cn) 代码&#xff1a; <view class"greenBtn_zw2" click"handleAddGroup">添加班级群</vie…
阅读更多...
通过Docker Compose来实现项目可以指定读取不同环境的yml包

通过Docker Compose来实现项目可以指定读取不同环境的yml包

通过Docker Compose来实现项目可以指定读取不同环境的yml包 1. 配置文件2. 启动命令 切换不同环境注意挂载的文件权限要777 1. 配置文件 version: 3.8 services:docker-test:image: openjdk:8-jdk-alpineports:- "${APP_PORT}:${CONTAINER_PORT}"volumes:- "${J…
阅读更多...
华为实训课笔记 2024 1223-1224

华为实训课笔记 2024 1223-1224

华为实训 12/2312/24 12/23 [Huawei]stp enable --开启STP display stp brief --查询STP MSTID Port Role STP State Protection 实例ID 端口 端口角色 端口状态 是否开启保护[Huawei]display stp vlan xxxx --查询制定vlan的生成树计算结…
阅读更多...
GitCode 光引计划投稿 | GoIoT：开源分布式物联网开发平台

GitCode 光引计划投稿 | GoIoT：开源分布式物联网开发平台

GoIoT 是基于Gin 的开源分布式物联网&#xff08;IoT&#xff09;开发平台&#xff0c;用于快速开发&#xff0c;部署物联设备接入项目&#xff0c;是一套涵盖数据生产、数据使用和数据展示的解决方案。 GoIoT 开发平台&#xff0c;它是一个企业级物联网平台解决方案&#xff…
阅读更多...
EasyGBS国标GB28181公网平台P2P远程访问故障诊断：云端服务端排查指南

EasyGBS国标GB28181公网平台P2P远程访问故障诊断：云端服务端排查指南

随着信息技术的飞速发展&#xff0c;视频监控领域正经历从传统安防向智能化、网络化安防的深刻转变。EasyGBS平台&#xff0c;作为基于国标GB28181协议的视频流媒体平台&#xff0c;为用户提供了强大的视频监控直播功能。然而&#xff0c;在实际应用中&#xff0c;P2P远程访问可…
阅读更多...
Vnlhun靶场Log4j2漏洞

Vnlhun靶场Log4j2漏洞

相关概念 log4j2是Apache的⼀个java日志框架&#xff0c;我们借助它进行日志相关操作管理&#xff0c;然而在2021年末log4j2爆出了远程代码执行漏洞&#xff0c;属于严重等级的漏洞 漏洞原理 简单说就是当你使⽤log4j2中提供的⽅法去输出⽇志信息时&#xff0c;⽐如说最常⻅…
阅读更多...
千兆网中的gmii与rgmii

千兆网中的gmii与rgmii

物理链路上是千兆网。1 Gbps1000 Mb/s1000/8 MB/s125 MB/s&#xff0c;这是和你的测试设备相连的1 Gbps物理带宽下的极速。关键点是1 B&#xff08;byte&#xff09;8 b&#xff08;bit&#xff09;。实际下载速度还取决于下载源的限制、出口的物理链路和运营商的限制。
阅读更多...
2024-12-24 NO1. XR Interaction ToolKit 环境配置

2024-12-24 NO1. XR Interaction ToolKit 环境配置

文章目录 1 软件配置2 安装 XRToolKit3 配置 OpenXR4 安装示例场景5 运行测试 1 软件配置 Unity 版本&#xff1a;Unity6000.0.26 ​ 2 安装 XRToolKit 创建新项目&#xff08;URP 3D&#xff09;&#xff0c;点击进入 Asset Store。 进入“Unity Registry”页签&#xff0…
阅读更多...
重温设计模式--外观模式

重温设计模式--外观模式

文章目录 外观模式&#xff08;Facade Pattern&#xff09;概述定义 外观模式UML图作用 外观模式的结构C 代码示例1C代码示例2总结 外观模式&#xff08;Facade Pattern&#xff09;概述 定义 外观模式是一种结构型设计模式&#xff0c;它为子系统中的一组接口提供了一个统一…
阅读更多...
【恶意软件检测】一种基于API语义提取的Android恶意软件检测方法（期刊等级：CCF-B、Q2）

【恶意软件检测】一种基于API语义提取的Android恶意软件检测方法（期刊等级：CCF-B、Q2）

一种基于API语义提取的Android恶意软件检测方法 A novel Android malware detection method with API semantics extraction 摘要 由于Android框架和恶意软件的持续演变&#xff0c;使用过时应用程序训练的传统恶意软件检测方法在有效识别复杂演化的恶意软件方面已显不足。为…
阅读更多...
【微信小程序】2|轮播图 | 我的咖啡店-综合实训

【微信小程序】2|轮播图 | 我的咖啡店-综合实训

轮播图 引言 在微信小程序中&#xff0c;轮播图是一种常见的用户界面元素&#xff0c;用于展示广告、产品图片等。本文将通过“我的咖啡店”小程序的轮播图实现&#xff0c;详细介绍如何在微信小程序中创建和管理轮播图。 轮播图数据准备 首先&#xff0c;在home.js文件中&a…
阅读更多...
RT-DETR学习笔记（2)

RT-DETR学习笔记（2)

七、IOU-aware query selection 下图是原始DETR。content query 是初始化为0的label embedding, position query 是通过nn.Embedding初始化的一个嵌入矩阵&#xff0c;这两部分没有任何的先验信息&#xff0c;导致DETR的收敛慢。 RT-DETR则提出要给这两部分&#xff08;conten…
阅读更多...
fpgafor循环语句使用

fpgafor循环语句使用

genvar i;//循环变量名称 generate for(i0;i<4;ii1)begin:tx//自己定义名称 //循环内容 end endgenerate12位的16进制乘以4就是48位位宽的2进制 因为 222*2(2^4)16
阅读更多...
62.基于SpringBoot + Vue实现的前后端分离-驾校预约学习系统(项目+论文)

62.基于SpringBoot + Vue实现的前后端分离-驾校预约学习系统(项目+论文)

项目介绍 伴随着信息技术与互联网技术的不断发展&#xff0c;人们进到了一个新的信息化时代&#xff0c;传统管理技术性没法高效率、容易地管理信息内容。为了实现时代的发展必须&#xff0c;提升管理高效率&#xff0c;各种各样管理管理体系应时而生&#xff0c;各个领域陆续进…
阅读更多...
最新文章

Copyright @ 2022~2023