C++_红黑树

       

目录

1、红黑树的规则

2、红黑树节点的定义 

3、红黑树插入节点的调整操作

3.1 情况一

3.2 情况二

3.3 情况三 

4、红黑树的实现

结语

前言：

        在C++中，红黑树是二叉搜索树的另一种优化版本，他与AVL树的区别在于保持树的平衡方式不同，AVL树保持平衡的方式是在节点中多存储一个成员来记录平衡因子，红黑树保持平衡的方式也是增加了一个成员，但是该成员的作用是记录节点的两种状态（颜色）：红色--黑色。当然只记录颜色并不能保持平衡，红黑树还规定最长路径的节点个数不会超过最短路径的节点个数的两倍，因此红黑树不会因为插入有序数据而演变成“单支树”。

1、红黑树的规则

        红黑树有如下规则：

        1、顾名思义，红黑树的节点只能有黑色和红色两种状态。

        2、根结点默认为黑色。

        3、红色节点的两个孩子只能是黑色节点。

        4、插入的节点默认为红色节点。

        5、每条路径的黑色节点都相同。

        红黑树正确示意图：

         红黑树错误示意图：

2、红黑树节点的定义 

        通过上述对红黑树的简述，可以给出红黑树的节点代码：

#define _CRT_SECURE_NO_WARNINGS 1

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;//若是AVL树这里记载的是平衡因子，红黑树是颜色

	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)//默认插入的节点是红色
	{}
};

        可以发现，红黑树的节点代码几乎和AVL树一模一样，只是控制平衡的条件有区别，仅此而已。 

3、红黑树插入节点的调整操作

        红黑树的插入函数可以分两个步骤：

        1、找到合适的位置插入，即二叉搜索树插入的逻辑（小于根节点的放在左边，大于根节点的放在右边）。

        2、因为插入的节点默认为红色，则插入节点后，查看当前树是否破坏了红黑树的规则，即观察其节点的父母节点是否为红色，如果是则需要进行调整操作（规则3）。

        在分析之前，先确定好节点之间的关系名称（cur表示新插入的节点，parant表示父母节点，uncle表示叔叔节点，gparent表示祖父节点）：

3.1 情况一

        当叔叔节点存在且为红，父母节点为红，祖父节点为黑：

        最后可以发现，经过一系列的调整后符号红黑树的规则。

3.2 情况二

        情况二又分两种情况：1、叔叔节点为黑色。2、不存在叔叔节点。

        1、其他条件和情况一相同，但是叔叔节点是黑色的：

        从上图可以发现，情况二多了旋转的步骤，并且在旋转之后将parent变黑，gparent变红，最终结果满足红黑树的规则。

        2、若不存在叔叔节点：

        综上所述，情况二可以总结为：旋转+变色（parent变黑，gparent变红）。 

3.3 情况三 

        情况三即以上情况的插入点不一样，以上情况的插入节点都是插入在“边缘处”，通俗来讲就是左子树插入的节点都是作为左孩子插入的，而右子树插入的节点都是作为右孩子插入的，但是实际中总会出现在右子树中插入的节点是以左孩子的形式插入的（如下图），拿上述情况二的第二种情况举例，若插入的cur在parent的左边，那么以上的处理方法显然不能解决问题，具体操作图如下：

4、红黑树的实现

        红黑树的实现代码如下：

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
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;//若是AVL树这里记载的是平衡因子，红黑树是颜色

	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()
	{
		_Destroy(_root);
		_root = nullptr;
	}
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->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		//当parent为红色则违法规则，需要调整
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (grandfather->_left == parent)//父母在祖父的左边
			{
				Node* uncle = grandfather->_right;
				// 情况1：叔叔节点存在且为红，叔叔和父母进行变色处理，并继续往上处理
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else // 情况2：叔叔不存在/叔叔存在且为黑，旋转+变色
				{
					//父母在祖父的左边，而cur在父母的左边，说明是“边缘”情况
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else//对应所述的情况三，需要旋转两次，并且cur变成了根结点
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else // 父母在祖父的右边
			{
				Node* uncle = grandfather->_left;
				// 情况1：u存在且为红，变色处理，并继续往上处理
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else // 情况2：叔叔不存在/叔叔存在且为黑，旋转+变色
				{
					//以下逻辑同上思路，只不过逻辑相反
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
		}
		_root->_col = BLACK;//根结点始终为黑

		return true;
	}

	void InOrder()
	{
		_InOrder(_root);
	}

	bool IsRedB()//检查红黑树
	{
		if (_root && _root->_col == RED)
		{
			cout << "根节点颜色是红色" << endl;
			return false;
		}

		int benchmark = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				++benchmark;
			cur = cur->_left;
		}

		// 连续红色节点
		return _Check(_root, 0, benchmark);
	}

	int Height()
	{
		return _Height(_root);
	}

private:
	void _Destroy(Node* root)//释放空间
	{
		if (root == nullptr)
		{
			return;
		}

		_Destroy(root->_left);
		_Destroy(root->_right);
		delete root;
	}

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

		int leftH = _Height(root->_left);
		int rightH = _Height(root->_right);

		return leftH > rightH ? leftH + 1 : rightH + 1;
	}

	bool _Check(Node* root, int blackNum, int benchmark)//红黑树的验证
	{
		if (root == nullptr)//走到空，就判断黑色节点数量是否一样
		{
			if (benchmark != blackNum)
			{
				cout << "某条路径黑色节点的数量不相等" << endl;
				return false;
			}

			return true;
		}

		if (root->_col == BLACK)//重新记录每条路径下的黑色节点
		{
			++blackNum;
		}

		if (root->_col == RED
			&& root->_parent
			&& root->_parent->_col == RED)//连续红色节点也会报错
		{
			cout << "存在连续的红色节点" << endl;
			return false;
		}

		//每次递归都把黑色节点数量传给下一个栈帧
		return _Check(root->_left, blackNum, benchmark)
			&& _Check(root->_right, blackNum, benchmark);
	}

	void _InOrder(Node* root)//中序遍历打印
	{
		if (root == nullptr)
		{
			return;
		}

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

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

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

		Node* ppnode = parent->_parent;

		subR->_left = parent;
		parent->_parent = subR;

		if (ppnode == nullptr)
		{
			_root = subR;
			_root->_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;

		Node* ppnode = parent->_parent;

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

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

private:
	Node* _root = nullptr;
};

int main()
{
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	RBTree<int, int> t1;
	for (auto e : a)
	{
		t1.Insert(make_pair(e, e));
	}

	t1.InOrder();//j检查打印出来的数据是否有序
	cout << endl << t1.IsRedB() << endl;
	return 0;
}

         运行结果：

        从上面代码可以看出，检验一棵树是否为红黑树，从以下几个方面进行判断：函数IsRedB的作用是判断根结点是否为黑色，然后随便遍历一条路径，记录该路径下黑色节点的数量（规则5）。 

        接着把记录下来的黑色节点数量传给函数_check，并且让_check函数把所有路径下的黑色节点记录下来，一一的去跟之前记录好的数据进行对比，若有不相等的情况说明该树不是红黑树，另外_check函数内还进行了红色节点是否连续的判断（规则3）。

结语

        以上就是关于红黑树的讲解，红黑树的重点还是在于了解红黑树的调整逻辑，理清叔叔节点和父母节点他们的位置关系，最核心的还是叔叔节点，他的存在与否，是红色还是黑色都影响最终的调整规律。最后希望本文可以给你带来更多的收获，如果本文对你起到了帮助，希望可以动动小指头帮忙点赞👍+关注😎+收藏👌！如果有遗漏或者有误的地方欢迎大家在评论区补充，谢谢大家！！

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

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

相关文章

Unity游戏输入系统（新版+旧版）

Unity游戏输入系统（新版+旧版）

使用新版还是旧版 旧版 using System.Collections; using System.Collections.Generic; using UnityEngine;public class c5 : MonoBehaviour {void Start(){}void Update(){// 注意要在游戏中 点鼠标键盘进行测试// 鼠标// 0左键 1右键 2滚轮if (Input.GetMouseButtonDown(0)…
阅读更多...
Java二叉树（1）

Java二叉树（1）

&#x1f435;本篇文章将对二叉树的相关概念、性质和遍历等知识进行讲解 一、什么是树 在讲二叉树之前&#xff0c;先了解一下什么是树&#xff1a;树是一种非线性结构&#xff0c;其由许多节点和子节点组成&#xff0c;整体形状如一颗倒挂的树&#xff0c;比如下图&#xff1…
阅读更多...
基于springboot+vue的党员教育和管理系统

基于springboot+vue的党员教育和管理系统

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、阿里云专家博主、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战&#xff0c;欢迎高校老师\讲师\同行交流合作 ​主要内容&#xff1a;毕业设计(Javaweb项目|小程序|Pyt…
阅读更多...
Springboot+vue的制造装备物联及生产管理ERP系统（有报告）。Javaee项目，springboot vue前后端分离项目。

Springboot+vue的制造装备物联及生产管理ERP系统（有报告）。Javaee项目，springboot vue前后端分离项目。

演示视频&#xff1a; Springbootvue的制造装备物联及生产管理ERP系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot vue前后端分离项 项目介绍&#xff1a; 本文设计了一个基于Springbootvue的制造装备物联及生产管理ERP系统&#xff0c;采用M&#xff…
阅读更多...
C++ opencv 学习

C++ opencv 学习

文章目录 1、创建窗口2、读取图片3、视频采集4、Mat的使用5、异或操作6、通道分离&#xff0c;通道合并7、色彩空间转换8、最大值、最小值9、绘制图像10、多边形绘制11、随机数12、鼠标实时绘制矩形13、归一化14、resize操作15、旋转翻转16、视频操作17、模糊操作18、高斯模糊操…
阅读更多...
力扣110 平衡二叉树 Java版本

力扣110 平衡二叉树 Java版本

文章目录 题目描述代码 题目描述 给定一个二叉树&#xff0c;判断它是否是高度平衡的二叉树。 本题中&#xff0c;一棵高度平衡二叉树定义为&#xff1a; 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 示例 1&#xff1a; 输入&#xff1a;root [3,9,…
阅读更多...
LaTeX中的多行数学公式

LaTeX中的多行数学公式

目录 参考链接 一、gather以及gather*环境编排公式 1、 gather环境 2、 gather*环境 3、 阻止编号 二、align以及align*环境设定公式对齐方式 1、align环境 2、align*环境 三、split环境实现一个公式多行排版 四、cases环境实现分段函数 参考链接 LaTeX中的多行数学…
阅读更多...
OpenCV 4基础篇| OpenCV图像的拼接

OpenCV 4基础篇| OpenCV图像的拼接

目录 1. Numpy (np.hstack&#xff0c;np.vstack)1.1 注意事项1.2 代码示例 2. matplotlib2.1 注意事项2.2 代码示例 3. 扩展示例&#xff1a;多张小图合并成一张大图4. 总结 1. Numpy (np.hstack&#xff0c;np.vstack) 语法结构&#xff1a; retval np.hstack(tup) # 水平…
阅读更多...
Endnote x9 最快方法批量导入.enw格式文件

Endnote x9 最快方法批量导入.enw格式文件

按照网上看到的一个方法直接选中所有enw批量拖拽到 All references 附件不行啊&#xff0c; 以为只能写bat脚本方式了 经过一番尝试&#xff0c;惊人的发现拖到下面这个符号的地方就行了&#xff01;&#xff01;&#xff01; 如果不成功的话&#xff0c;可能&#xff1a; 我…
阅读更多...
C语言：结构体（自定义类型）知识点（包括结构体内存对齐的热门知识点）

C语言：结构体（自定义类型）知识点（包括结构体内存对齐的热门知识点）

和黛玉学编程呀&#xff0c;大家一起努力呀............. 结构体类型的声明 回顾一下 struct tag { member-list; }variable-list; 创建和初始化 我们知道&#xff0c;在C语言中&#xff0c;对于一些数据是必须初始化的&#xff0c;但是结构体怎么创建并且初始化呢&#xff1…
阅读更多...
码垛工作站：食品生产企业的转型助推器

码垛工作站：食品生产企业的转型助推器

在当今高度自动化的工业生产中&#xff0c;码垛工作站的应用正逐渐成为一种趋势。某食品生产企业在面临市场竞争加剧、人工成本上升等多重压力下&#xff0c;决定引入码垛工作站&#xff0c;以期实现生产流程的升级与变革。 一、码垛工作站引入背景 该企业主要从事休闲食品的…
阅读更多...
A股绿色发展报告：2000-2022年指数变化分析

A股绿色发展报告：2000-2022年指数变化分析

一、有关“绿色发展”的发文趋势和主题分布 运用熵值法测算出企业绿色发展指数 二、数据来源&#xff1a;企业年报等&#xff0c;企业财务相关数据 三、时间跨度&#xff1a;2000-2022年 四、数据范围&#xff1a;A股上市公司 五、数据指标 股票代码 FE法全要素生产率 支付给…
阅读更多...
STM32 中断流程介绍

STM32 中断流程介绍

STM32可以产生中断的事件多种多样&#xff0c;比如&#xff1a;定时器时间结束、串口接收到数据、某个GPIO检测到电平变化等等等等。 1、STM32 gpio 中断处理流程介绍 1、从引脚进入的高低电平首先由输入驱动器处理&#xff0c;如下图 2、经过输入驱动器处理后的信号会进…
阅读更多...
栈与队列力扣经典例题20. 有效的括号1047. 删除字符串中的所有相邻重复项150. 逆波兰表达式求值

栈与队列力扣经典例题20. 有效的括号1047. 删除字符串中的所有相邻重复项150. 逆波兰表达式求值

对于栈与队列&#xff0c;我们首先要搞清楚&#xff0c;栈是先入后出&#xff0c;而队列是先入先出&#xff0c;利用这个特性&#xff0c;我们来判断题目用什么STL容器&#xff0c;便于我们去解决问题 20. 有效的括号 这道题&#xff0c;首先我们要知道哪些情况&#xff0c;是会…
阅读更多...
IDEA丢失 此窗口 新窗口 打开项目怎么办？

IDEA丢失 此窗口 新窗口 打开项目怎么办？

IDEA丢失 此窗口 新窗口 打开项目怎么办&#xff1f; 出现的问题如下&#xff1a;我的这个页面没有了&#xff0c;直接提示是不是关闭当前的进程。 解决的方法&#xff1a;
阅读更多...
Unity TMP文字移动效果

Unity TMP文字移动效果

前言 看见很多游戏有很特殊的波浪形文字效果&#xff0c;于是来尝试一下控制TMP文字顶点的方式达到类似效果。 原理 挂载tmp text&#xff0c;在里面随便放入非空格字符。 tmp text组件开放了textInfo接口&#xff0c;也就是GetComponent<TextMeshProUGUI>().textInfo…
阅读更多...
Linux：线程控制和原生线程库

Linux：线程控制和原生线程库

文章目录 线程的id和LWP线程的终止线程的返回值问题关于原生线程库问题 本篇总结的内容主要是关于线程的控制专题 线程的id和LWP 对于获取线程的id来说&#xff0c;在Linux系统中存在这样的调用 这个调用就可以获取返回当前线程的id 先写出下面的实例代码 #include <ios…
阅读更多...
设计模式学习笔记 - 设计原则 - 8.迪米特法则（LOD）

设计模式学习笔记 - 设计原则 - 8.迪米特法则（LOD）

前言 迪米特法则&#xff0c;是一个非常实用的原则。利用这个原则&#xff0c;可以帮我们实现代码的 “高内聚、松耦合”。 围绕下面几个问题&#xff0c;来学习迪米特原则。 什么是 “高内聚、松耦合”&#xff1f;如何利用迪米特法则来实现 高内聚、松耦合&#xff1f;哪些…
阅读更多...
【Python】FastAPI 项目创建 与 Docker 部署

【Python】FastAPI 项目创建 与 Docker 部署

文章目录 前言&需求描述1. 本地FastAPI1.1 Python 环境准备1.2 本地 Pycharm 创建FastAPI项目 2. Python FastAPI 部署2.1 服务器配置Python环境2.2.1 下载与配置Git、Pyenv等工具2.2.2 下载与配置Python 2.2 FastAPI 打包成镜像2.2.1 项目准备所需环境文件2.2.2 编写Docke…
阅读更多...
Java基于SpringBoot的在线文档管理系统的设计与实现论文

Java基于SpringBoot的在线文档管理系统的设计与实现论文

摘 要 随着科学技术的飞速发展&#xff0c;社会的方方面面、各行各业都在努力与现代的先进技术接轨&#xff0c;通过科技手段来提高自身的优势&#xff0c;在线文档管理当然也不能排除在外。在线文档管理系统是以实际运用为开发背景&#xff0c;运用软件工程原理和开发方法&am…
阅读更多...
最新文章

Copyright @ 2022~2023