C++:平衡二叉搜索树之红黑树

一、红黑树的概念

红黑树， 和AVL都是二叉搜索树， 红黑树通过在每个节点上增加一个储存位表示节点的颜色， 可以是RED或者BLACK， 通过任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树能够确保没有一条路径会比其他路径长出两倍，因此红黑树是接近平衡的。

与AVL树相比，红黑树的插入和删除操作更具优势，因为红黑树是接近平衡的，AVL树是绝对平衡的， 因此插入删除等操作时，红黑树需要旋转的次数是比AVL树少的。

二、红黑树的性质

  1. 每个节点不是红色就是黑色
  2. 根节点是黑色的
  3. 如果一个节点是红色的，则它的两个孩子节点是黑色的
  4. 一条路径上没有连续的红色节点， 每条路径上黑色节点的数量是相同的

下面就是一个红黑树的示例：

根据红黑树的性质我们知道：一个红黑树中，最短路径 * 2 >= 最长路径

理论上：最短路径：全黑 最长路径：一黑一红交替

三、红黑树节点的定义

下面是红黑树节点的定义代码：

//节点的颜色定义
enum Colour
{
	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;//节点的双亲节点
	Colour _col;//节点的颜色
    
    //节点的构造函数
	RBTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
	{}
};

四、红黑树的插入

红黑树是在二叉搜索树的基础上加上使其近似平衡的限制条件， 因此红黑树的插入可以分成以下两步：

1、按照二叉搜索树的性质插入新节点

2、检测新节点插入后，红黑树的性质是否遭到破坏

新节点的默认颜色是红色，因此，如果双亲节点是黑色就没有违反任何红黑树的性质，不需要调整，但是如果新插入节点的双亲节点是红色时， 就违反了不能有相连的红色节点的规则，此时需要对红黑树进行分情况讨论：

cur为当前节点， p为父节点， g为祖父节点， u为叔父节点

4.1情况一：cur 为红， p为红， g为黑， u存在且为黑

注意：这里的树，可能是一棵完整的树， 也可能是一个子树

此时abcde子树都为空

这个时候我们只需要进行变色处理， 将p 和 u节点变为黑色， 将g改为红色

调整完以后，如果g是根节点， 需要将g改为黑色， 因为红黑树的性质规定根节点的颜色必须是黑色。

如果g是子树，并且g的双亲节点是红色的话就需要继续向上调整， 如下图所示：

4.2情况二： cur为红， p为红， g为黑， u不存在/u存在且为黑

这里说明u的情况有两种：

1.u不存在， 此时cur一定是新增节点， 如果cur不是新增节点的话， 那么cur和p一定有一个节点的颜色是黑色， 但是那样就不满足每条路径黑色节点的数目相同这一性质。

p是g的左子节点， cur是p的左子节点， 那么就对g进行右单旋：

变色处理：p, g变色 – p变黑色， g变红色

p是g的右子节点， cur是p的右子节点， 那么就对g进行左单旋：

变色处理：p, g变色 – p变黑色， g变红色

p是g的左子节点， cur是p的右子节点，先对p进行左单旋， 再对g做右单旋：

变色处理：cur, g变色 – cur变黑色， g变红色

先进行左单旋；

再进行右单旋：

p是g的右子节点， cur是p的左子节点， 先对p进行右单旋， 再对g进行左单旋：

变色处理：cur， g变色 – cur变黑色， g变红色

先进行右单旋：

再进行左单旋：

2.u存在且为黑， 那么cur节点原来的颜色一定是黑色， 现在是红色的原因就是因为cur的子树在调整的过程中将cur的颜色更新成了红色。

p是g的左子节点， cur是p的左子节点， 那么就对g进行右单旋：

变色处理：p, g变色 – p变黑色， g变红色

p是g的右子节点， cur是p的右子节点， 那么就对g进行左单旋：

变色处理：p, g变色 – p变黑色， g变红色

p是g的左子节点， cur是p的右子节点，先对p进行左单旋， 再对g做右单旋：

变色处理：cur, g变色 – cur变黑色， g变红色

先进行左单旋：

再进行右单旋：

p是g的右子节点， cur是p的左子节点， 先对p进行右单旋， 再对g进行左单旋：

变色处理：cur， g变色 – cur变黑色， g变红色

先进行右单旋：

再进行左单旋：

左单旋代码实现：

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

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

	}

右单旋代码实现：

//右单旋
	void RotateR(Node* parent)
	{
		Node* SubL = parent->_left;
		Node* SubLR = SubL->_right;
		parent->_left = SubLR;
		if (SubLR)
			SubLR->_parent = parent;

		Node* parentP = parent->_parent;
		SubL->_right = parent;
		parent->_parent = SubL;

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

插入函数整体代码实现：

bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			//如果是个空树就将新节点作为根节点
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);
		cur->_col = RED;
		if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}

		cur->_parent = parent;
		//处理
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			// g
			//p  u结构
			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//uncle不存在或者存在且为黑-》旋转加变色
				{
					if (cur == parent->_left)
					{
						//cur为parent的左子结点时进行右旋
						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)
					{
						//cur为父亲的右子节点时对g进行左单旋
						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;
	}

五、红黑树相关接口的实现

查找函数的实现：

依旧是根据二叉搜索树的查找规则：

//查找函数
	Node* Find(const K& key)
	{
		if (_root == nullptr)
			return nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else
				return cur;
		}

		return nullptr;
	}

容量高度相关：

返回有效节点个数：

//有效节点个数
	int Size()
	{
		_Size(_root);
	}

    int _Size(Node* root)
	{
		return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;
	}

二叉树高度：

//平衡二叉树高度
	int Height()
	{
		_Height(_root);
	}

    int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;

		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);

		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}

中序遍历：

//中序遍历
	void Inorder()
	{
		_inorder(_root);
		cout << endl;
	}

    void _inorder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_inorder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_inorder(root->_right);
	}

六、红黑树的验证

我们要通过代码来验证我们所实现的红黑树是否是符合红黑树的性质的。

红黑树的验证分为以下两步：

  1. 验证其是否满足二叉搜索树也就是中序遍历是否有序
  2. 验证其是否满足红黑树的性质

验证代码：

1、验证是否为二叉搜索树：

//中序遍历
	void Inorder()
	{
		_inorder(_root);
		cout << endl;
	}

    void _inorder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_inorder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_inorder(root->_right);
	}

2、验证是否满足红黑树的性质：

//判断是否为红黑树
	bool IsBalance()
	{
		if (_root == nullptr)
			return true;

		if (_root->_col == RED)
		{
			return false;
		}

		// 参考值
		int refNum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++refNum;
			}

			cur = cur->_left;
		}

		return Check(_root, 0, refNum);
	}

    bool Check(Node* root, int blackNum, const int refNum)
	{
		if (root == nullptr)
		{
			//cout << blackNum << endl;
			if (refNum != blackNum)
			{
				cout << "存在黑色节点的数量不相等的路径" << endl;
				return false;
			}

			return true;
		}

		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << root->_kv.first << "存在连续的红色节点" << endl;
			return false;
		}

		if (root->_col == BLACK)
		{
			blackNum++;
		}

		return Check(root->_left, blackNum, refNum)
			&& Check(root->_right, blackNum, refNum);
	}

通过以上几段代码就能完成对我们实现的红黑树验证。

七、红黑树与AVL数的比较

红黑树和AVL树都是平衡二叉搜索树， 进行增删查改的操作时的时间复杂度都是O(logN)， 红黑树不追求绝对平衡， AVL树追求绝对平衡，相对而言红黑树在维持平衡时的旋转次数要少于AVL树， 因此在经常进行插入和删除的结构中红黑树的性能一般要优于AVL树， 因此是实际中使用红黑树更多。

八、红黑树的应用

  1. C++ STL库中的map/set 、mutil_map/mutil_set的实现
  2. java库
  3. linux内核

不止以上三处使用， 这里仅是为了举例。

关于红黑树的介绍到这里就结束了， 希望大家通过这篇文章能都红黑树有一定的理解， 以下是红黑树的具体代码实现链接：

红黑树具体实现代码

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

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

相关文章

C++ 11相关新特性（lambda表达式与function包装器）

C++ 11相关新特性（lambda表达式与function包装器）

目录 lambda表达式 引入 lambda表达式介绍 lambda表达式捕捉列表的传递形式 lambda表达式的原理 包装器 包装器的基本使用 包装器与重载函数 包装器的使用 绑定 C 11 新特性 lambda表达式 引入 在C 98中&#xff0c;对于sort函数来说&#xff0c;如果需要根据不同的比较方式实现…
阅读更多...
超网和无类间路由是什么？

超网和无类间路由是什么？

​一、超网概述 超网是将多个连续的网络地址组合成一个增加的网络地址的技术。常用于减少路由器的路由表大小&#xff0c;网络的可扩展性。通过合并连续的子网&#xff0c;超网可以减少路由入侵的数量&#xff0c;从而提高网络的效率。 超网的实现基于合并多个具有连续IP地址…
阅读更多...
【vue教程】五. Vue 的路由管理

【vue教程】五. Vue 的路由管理

目录 往期列表本章涵盖知识点回顾Vue Router 的基本概念什么是 Vue Router&#xff1f;为什么需要 Vue Router&#xff1f; 路由的配置和使用安装 Vue Router创建路由在 Vue 实例中使用路由模板中的路由链接 动态路由和嵌套路由动态路由嵌套路由 路由守卫什么是路由守卫&#x…
阅读更多...
HarmonyOS应用三之组件生命周期和参数传递

HarmonyOS应用三之组件生命周期和参数传递

目录&#xff1a; 1、生命周期的执行顺序2、页面数据传递3、图片的读取4、数据的备份和恢复5、轮播图6、页面布局图 1、生命周期的执行顺序 /** Copyright (c) 2023 Huawei Device Co., Ltd.* Licensed under the Apache License, Version 2.0 (the "License");* yo…
阅读更多...
微服务架构设计中的常见的10种设计模式

微服务架构设计中的常见的10种设计模式

微服务架构设计的概念 微服务架构&#xff08;Microservices Architecture&#xff09;是一种用于构建分布式系统的软件设计模式。它将大型应用程序拆分成一组小型、自治的服务&#xff0c;每个服务都运行在其独立的进程中&#xff0c;服务之间通过轻量级的通信机制&#xff08…
阅读更多...
Nginx 核心配置详解

Nginx 核心配置详解

章节 1 NGINX 的源码安装 2 NGINX 核心配置详解 3 NGINX 之 location 匹配优先级 4 NGINX 基础参数与功能 目录 1 配置文件说明 1.1 nginx 配置文件格式说明 1.2 Nginx 主配置文件的配置指令方式&#xff1a; 1.3 主配置文件结构&#xff1a;四部分 1.4 nginx 文件作用解…
阅读更多...
使用Python编写AI程序，让机器变得更智能

使用Python编写AI程序，让机器变得更智能

人工智能&#xff08;AI&#xff09;是当今科技领域最热门的话题之一。随着Python编程语言的逐渐流行&#xff0c;它已经成为许多人工智能编程的首选语言。本文将介绍如何使用Python编写AI程序&#xff0c;让机器变得更智能。 首先&#xff0c;Python提供了大量的AI库和工具&a…
阅读更多...
10、stm32实现adc读取数据

10、stm32实现adc读取数据

一、配置 二、代码 /* USER CODE BEGIN 2 */OLED_Init();OLED_Clear();OLED_ShowString(0,0,"Hello adc",12,0);uint16_t adc_number 0;/* USER CODE END 2 *//* USER CODE BEGIN WHILE */while (1){HAL_ADC_Start(&hadc1);HAL_ADC_PollForConversion(&hadc1…
阅读更多...
SQL实战

SQL实战

学习视频&#xff1a;【课程2.0】SQL从入门到实战|云端数据库搭建|Excel&Tableau连接数据库_哔哩哔哩_bilibili 由于我学习过SQL&#xff0c;所以直接记录一些函数、特殊用法、刷题等实战的知识&#xff0c;后面教学搭建云端数据库和其他软件连接数据库视频讲解很清晰&…
阅读更多...
华为AR1220配置GRE隧道

华为AR1220配置GRE隧道

1.GRE隧道的配置 GRE隧道的配置过程，包括设置接口IP地址、配置GRE隧道接口和参数、配置静态路由以及测试隧道连通性。GRE隧道作为一种标准协议，支持多协议传输，但不提供加密，并且可能导致CPU资源消耗大和调试复杂等问题。本文采用华为AR1220路由器来示例说明。 配置…
阅读更多...
C语言家教记录（六）

C语言家教记录（六）

导语 本次授课的内容如下&#xff1a;指针&#xff0c;指针和数组 辅助教材为 《C语言程序设计现代方法&#xff08;第2版&#xff09;》 指针 指针变量 计算机按字节划分地址&#xff0c;每个地址访问一个字节 指针变量指向变量的地址&#xff0c;指的是变量第一个字节的…
阅读更多...
ElasticSearch读写性能调优

ElasticSearch读写性能调优

文章目录 ES写入数据过程ES读取数据的过程写数据底层原理提升集群读取性能数据建模优化分片 提升写入性能的方法服务器端优化写入性能建模时的优化降低Translog写磁盘的频率&#xff0c;但是会降低容灾能力分片设定调整Bulk 线程池和队列 ES写入数据过程 客户端选择一个node发…
阅读更多...
记录一次搭建uniapp-vue3的基础项目

记录一次搭建uniapp-vue3的基础项目

1.使用 HBuilder X 创建uniapp vue3的基础项目 2.安装 自动导包插件 unplugin-auto-import npm install unplugin-auto-import或者 pnpm install unplugin-auto-import2.1 根目录下创建 vite.config.js 复制粘贴以下内容 import { defineConfig } from vite import uni fro…
阅读更多...
食品零食小吃商城管理系统-计算机毕设Java|springboot实战项目

食品零食小吃商城管理系统-计算机毕设Java|springboot实战项目

&#x1f34a;作者&#xff1a;计算机毕设匠心工作室 &#x1f34a;简介&#xff1a;毕业后就一直专业从事计算机软件程序开发&#xff0c;至今也有8年工作经验。擅长Java、Python、微信小程序、安卓、大数据、PHP、.NET|C#、Golang等。 擅长&#xff1a;按照需求定制化开发项目…
阅读更多...
一文学会本地部署可视化应用JSONCrack并配置公网地址实现远程协作

一文学会本地部署可视化应用JSONCrack并配置公网地址实现远程协作

文章目录 前言1. Docker安装JSONCrack2. 安装Cpolar内网穿透工具3. 配置JSON Crack界面公网地址4. 远程访问 JSONCrack 界面5. 固定 JSONCrack公网地址 前言 本文主要介绍如何在Linux环境使用Docker安装数据可视化工具JSONCrack&#xff0c;并结合cpolar内网穿透工具实现团队在…
阅读更多...
网络编程/在哪些场景中不必要进行网络字节序装换? Windows Sockets: Byte Ordering

网络编程/在哪些场景中不必要进行网络字节序装换? Windows Sockets: Byte Ordering

文章目录 概述字节序必须转换字节序的的情况不必转换字节序的的情况字节序转换的例程字节序转换函数字节序转换可以不生硬字节序和位序 概述 本文主要讲述了在哪些场景下必须要进行大小端字节序转换&#xff0c;在哪些场景下可以不用进行大小端字节序转换&#xff0c;IP和端口…
阅读更多...
＜数据集＞安全帽和安全背心识别数据集＜目标检测＞

＜数据集＞安全帽和安全背心识别数据集＜目标检测＞

数据集格式&#xff1a;VOCYOLO格式 图片数量&#xff1a;22141张 标注数量(xml文件个数)&#xff1a;22141 标注数量(txt文件个数)&#xff1a;22141 标注类别数&#xff1a;3 标注类别名称&#xff1a;[helmet, vest, head] 序号类别名称图片数框数1helmet15937572402v…
阅读更多...
程序员如何写PLC程序

程序员如何写PLC程序

PLC是可编程逻辑控制器的简称&#xff0c;常用的编程语言是IEC61131-3&#xff08;梯形图、结构化文本、指令表、功能块、顺序功能图&#xff09;和西门子的SCL。程序员常用的编程语言是JS、Java、Python、C/C、Go等。PLC广泛采用编程工具有codesys、博图等。程序员常用的编程工…
阅读更多...
XSS DOM破坏实战案例

XSS DOM破坏实战案例

目录 案例一 思考 源码分析 查找问题 实现 案例二 查看源码 问题查找 实现 实验环境&#xff1a;DOM clobbering | Web Security Academy (portswigger.net) 案例一 里面是一篇篇的博客&#xff0c;点击进去里面是一些评论 思考 尝试一些常规的xss 没什么效果... 他将…
阅读更多...
为什么穷大方

为什么穷大方

为什么有些人明明很穷&#xff0c;却非常的大方呢&#xff1f; 因为他们认知太低&#xff0c;根本不懂钱的重要性&#xff0c;总是想着及时享乐&#xff0c;所以一年到头也存不了什么钱。等到家人孩子需要用钱的时候&#xff0c;什么也拿不出来&#xff0c;还到处去求人。 而真…
阅读更多...
最新文章

Copyright @ 2022~2023