C++模拟实现红黑树

目录

介绍----什么是红黑树

 甲鱼的臀部----规定

分析思考

绘图解析+代码实现

节点部分

插入部分+分步解析

●父亲在祖父的左，叔叔在祖父的右：

●父亲在祖父的右，叔叔在祖父的左：

测试部分

整体代码

介绍----什么是红黑树

红黑树基于二叉搜索树，它和AVL树一样避免了二叉搜索树中极端场景单边树的情况，保证了检索的效率。红黑树允许最长路径是最短路径的二倍，相较于AVL树而言是近似于平衡的状态，但是减少了旋转的次数。

 甲鱼的臀部----规定

●每个节点都有颜色，不是红色就是黑色。

●根节点一定是黑色的。

●不能连续出现两个红色的节点。

●每条路径上的黑色节点数量相同。

●每个空节点都是黑色的。

●最多允许一条路径上的节点是另一条路径上节点的二倍。

分析思考

节点默认颜色应该选红色还是黑色，为什么？

答：插入红色可能会出现连续的红色节点，插入黑色会改变当前路径上的黑色节点数。选择默认插入节点为红色的原因是插入后的影响会小一些，当父节点是黑色时不用调整。相反的，黑色节点的插入一定会违反红黑树的规则。

满足上述特性为什么能保证最长路径不会超过最短路径的2倍？

答：这里要关注红黑树的两个特性，红色节点的孩子节点一定是黑色，每条路径的黑色节点树相同。也就说最长路径是红色节点和黑色交替，最短路径是全黑节点。这样一来，最长路径和最短路径间的差距就控制在了规定范围内。

绘图解析+代码实现

节点部分

三叉链结构分别指向左右孩子和父亲节点，数据方面存储键值对，除此之外还需要一个记录节点颜色的变量。

enum Color
{
	RED,
	BLACK
};

template<class K,class V>
struct RBTreeNode
{
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;

	pair<K, V> _kv;
	Color _color;

	RBTreeNode(pair<K, V> kv, Color color = RED)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_color(color)
	{

	}
};

插入部分+分步解析

红黑树是二叉搜索树，插入节点的规则和二叉搜索的特点一样：

   typedef RBTreeNode<K,V> Node;
	bool inster(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_color = BLACK;
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		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->_color = RED;
		if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
        //节点插入后，需要检查红黑树的特性有没有被破坏掉
        //......
    }

上述我们谈论过新节点的颜色默认为红色的原因，那么接下来的插入如果新节点插入后其父节点的颜色是黑色，那么直接插入即可。如果其父节点的颜色为红色，那么就出现了两个红色节点出现的情况，此时就需要进行调整：

 

关注：红黑树的处理方法重点关注这样的几个节点：cur(新增节点)、parent(父亲节点)、uncle(叔叔节点)、grandfather（祖父节点）。

当节点的插入违反了红黑树“龟腚”时，对应不同的情况分别处理：

●父亲在祖父的左，叔叔在祖父的右：

情况1：cur为红，parent红色，叔叔节点存在且是红色，祖父是黑色；

 

如上图所示，情况1的处理方法就是将父亲和叔叔的节点变为黑色，祖父的节点变为红色。对于祖父为什么要变红是基于这样的考虑，我们当前的处理很可能只是在子树当中，如果祖父节点保持黑色不变，对于子树这两条路径而言，增加了黑色节点，这样一来就“拆东墙补了西墙”，又违反了另一条规则。如果祖父节点是根节点，改为红色当然是不合理的，我们在最后做下强制处理即可。

注意：这种情况可能是局部的处理，当祖父节点变红且不是根节点时，可能会破坏规则，所以针对情况1需要继续向上查找，也就是将祖父节点看成新增节点，祖父的父亲看做新增节点的父节点，继续向上更新检查树结构。

                if (uncle && uncle->_color == RED)
				{
					//情况1，叔叔节点存在，且是红色的
					parent->_color = uncle->_color = BLACK;
					grandfater->_color = RED;
					
					//更新cur和parent的位置
					cur = grandfater;
					parent = cur->_parent;
				}

情况2：cur为红（插入或者调整后和父亲祖父为一条直线），parent红色，叔叔不存在或者叔叔是黑色，祖父是红色。

当叔叔不存在时：这种情况较好分析，新节点插入后左边高，左边高度超过右边的2倍，进行一次右单旋，祖父变成红色，父亲变为黑色，这颗树调整完毕，不管它是不是子树都不会向上影响。

叔叔存在且为黑色，观察下图，每条路径上的黑色节点数量不相等，所以cur的位置应该是从黑色调整为的红色。

注意：这里不要受图示的影响，感觉uncle路径上的黑节点好像是多一个。调整前后的每条路径数量都是相等的，想象小三角中有着不同的结构就可以了。

叔叔的存在与否只是分析的过程不同，它们的代码处理方式是一样的： 

                    //在一条线上
					if (parent->_left == cur)
					{
						//情况2，叔叔节点不存在或者存在是黑色的
						//右单旋
						RotaR(grandfater);

						parent->_color = BLACK;
						grandfater->_color = RED;
					}

 

情况3：cur为红（插入或者调整后和父亲祖父为线一条折），parent红色，叔叔不存在或者叔叔是黑色，祖父是红色。

uncle不存在：

 uncle存在:

                      
                       if(cur == parent->_left)
                        {
                           //情况3,叔叔节点存在是黑色的，在一条折线上
						   RotaL(parent);
						   RotaR(grandfater);

						   cur->_color = BLACK;
						   grandfater->_color = RED;
                        }

●父亲在祖父的右，叔叔在祖父的左：

处理大思路和上述一致，只是叔叔和父亲交换了位置，不在画图分析，列举处理要点：
情况1：叔叔存在且为红色，叔叔和父亲变黑，祖父变红。向上继续查找。

                if (uncle && uncle->_color == RED)
				{
					//情况1，叔叔存在且是红色
					parent->_color = uncle->_color = BLACK;
					grandfater->_color = RED;

					//继续向上更新
					cur = grandfater;
					parent = cur->_parent;
				}

情况2：叔叔不存在或者存在为黑色，cur的位置和父亲祖父是一条直线，右边高，以祖父为轴点左单旋。祖父变红，父亲变黑。

                   //在右边插入
					if (parent->_right == cur)
					{
						//进行一个左单旋
						RotaL(grandfater);
						//父亲的颜色变成黑色
						parent->_color = BLACK;
						//祖父的的颜色变成红色
						grandfater->_color = RED;
					}

情况3：叔叔不存在或者存在为黑色，cur的位置和父亲祖父是一条折线，先以父亲为轴右单旋，在以祖父为轴点左单旋，祖父变红，cur变黑。

                    if(cur == parent->_left)//左边插入
					{
						//右单旋
						RotaR(parent);
						//左单旋
						RotaL(grandfater);

						//改变颜色
						grandfater->_color = RED;
						cur->_color = BLACK;

					}

测试部分

因为红黑树是二叉搜索树，在测试时很可能会有隐式的错误，比较难发现，所以需要下面的测试接口对红黑树的特性进行检查，检查是否有连续的红色节点出现，每条路径上的黑色节点是否相等。

bool check(Node* root,int num,int BLACKNUM)
	{
		if (root == nullptr)
		{
			if (num != BLACKNUM)
			{
				cout << "某条路径上的黑色节点和其他路径不相等" << endl;
				return false;
			}
			return true;
		}

		if (root->_color == RED && root->_parent->_color == RED)
		{
			cout << "连续出现两个红色节点" << endl;
			return false;
		}
		if (root->_color == BLACK)
		{
			num++;
		}
		return check(root->_left, num, BLACKNUM)
		     &&check(root->_right, num, BLACKNUM);
	}
	bool IsBalance()
	{
		if (_root == nullptr)
		{
			return false;
		}
		//根节点的颜色一定要是黑色
		if (_root->_color != BLACK)
		{
			return false;
		}
		Node* ret = _root;
		int _blacknum = 0;
		while (ret)
		{
			if (ret->_color == BLACK)
			{
				_blacknum++;
			}
			ret = ret->_left;
		}
		return check(_root,0,_blacknum);
	}

整体代码

#include <time.h>
enum Color
{
	RED,
	BLACK
};

template<class K,class V>
struct RBTreeNode
{
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;

	pair<K, V> _kv;
	Color _color;

	RBTreeNode(pair<K, V> kv, Color color = RED)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_color(color)
	{

	}
};

template <class K,class V>
class RBTee
{
public:
	typedef RBTreeNode<K,V> Node;
	bool inster(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_color = BLACK;
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		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->_color = RED;
		if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}


		//插入的节点默认是红色的
		while (parent && parent->_color == RED)
		{
			Node* grandfater = parent->_parent;
			if (parent == grandfater->_left)
			{
				Node* uncle = grandfater->_right;
				if (uncle && uncle->_color == RED)
				{
					//情况1，叔叔节点存在，且是红色的
					parent->_color = uncle->_color = BLACK;
					grandfater->_color = RED;
					
					//更新cur和parent的位置
					cur = grandfater;
					parent = cur->_parent;
				}
				else 
				{
					//左边新增
					if (parent->_left == cur)
					{
						//情况2，叔叔节点存在是黑色的，在一条线上
						//右单旋
						RotaR(grandfater);

						parent->_color = BLACK;
						grandfater->_color = RED;
					}
					//右边新增
					else
					{
						//情况3,叔叔节点存在是黑色的，在一条折线上
						RotaL(parent);
						RotaR(grandfater);

						cur->_color = BLACK;
						grandfater->_color = RED;
					}
					//树进行了旋转调整，已经平衡，跳出循环
					break;
				}
				
			}
			else //parent在grandfater的右边
			{
				Node* uncle = grandfater->_left;
				if (uncle && uncle->_color == RED)
				{
					//情况1，叔叔存在且是黑色
					parent->_color = uncle->_color = BLACK;
					grandfater->_color = RED;

					//继续向上更新
					cur = grandfater;
					parent = cur->_parent;
				}
				else//uncle的颜色是黑色
				{
					//在右边插入
					if (parent->_right == cur)
					{
						//进行一个左单旋
						RotaL(grandfater);
						//父亲的颜色变成黑色
						parent->_color = BLACK;
						//祖父的的颜色变成红色
						grandfater->_color = RED;
					}
					else//左边插入
					{
						//右单旋
						RotaR(parent);
						//左单旋
						RotaL(grandfater);

						//改变颜色
						grandfater->_color = RED;
						cur->_color = BLACK;

					}
					break;
				}

			}
		}

		_root->_color = BLACK;
		return true;
	}

	void Inorder()
	{
		_Inorder(_root);
	}
	
	bool check(Node* root,int num,int BLACKNUM)
	{
		if (root == nullptr)
		{
			if (num != BLACKNUM)
			{
				cout << "某条路径上的黑色节点和其他路径不相等" << endl;
				return false;
			}
			return true;
		}

		if (root->_color == RED && root->_parent->_color == RED)
		{
			cout << "连续出现两个红色节点" << endl;
			return false;
		}
		if (root->_color == BLACK)
		{
			num++;
		}
		return check(root->_left, num, BLACKNUM)
		     &&check(root->_right, num, BLACKNUM);
	}
	bool IsBalance()
	{
		if (_root == nullptr)
		{
			return false;
		}
		//根节点的颜色一定要是黑色
		if (_root->_color != BLACK)
		{
			return false;
		}
		Node* ret = _root;
		int _blacknum = 0;
		while (ret)
		{
			if (ret->_color == BLACK)
			{
				_blacknum++;
			}
			ret = ret->_left;
		}
		return check(_root,0,_blacknum);
	}
private:
	void _Inorder(Node* root)
	{
		if (root == nullptr)
		{
			return ;
		}

		_Inorder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.first << endl;
		_Inorder(root->_right);
	}
		void RotaL(Node* pparent)
		{
			Node* subR = pparent->_right;
			Node* subRL = subR->_left;

			pparent->_right = subRL;
			if (subRL)
			{
				subRL->_parent = pparent;
			}

			Node* pNode = pparent->_parent;
			pparent->_parent = subR;
			subR->_left = pparent;

			if (pNode == nullptr)
			{
				_root = subR;
				_root->_parent = nullptr;
			}
			else
			{
				if (pNode->_left == pparent)
				{
					pNode->_left = subR;
				}
				else if (pNode->_right == pparent)
				{
					pNode->_right = subR;
				}
				subR->_parent = pNode;
			}
		}
		void RotaR(Node* pparent)
		{
			Node* subL = pparent->_left;
			Node* subLR = subL->_right;

			pparent->_left = subLR;
			if (subLR != nullptr)
			{
				subLR->_parent = pparent;
			}

			Node* pNode = pparent->_parent;
			subL->_right = pparent;
			pparent->_parent = subL;

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


private:
	Node* _root = nullptr;
};

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

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

相关文章

2023年江苏省职业院校技能大赛中职网络安全赛项试卷-教师组任务书

2023年江苏省职业院校技能大赛中职网络安全赛项试卷-教师组任务书

2023年江苏省职业院校技能大赛中职网络安全赛项试卷-教师组任务书 一、竞赛时间 9:00-12:00&#xff0c;12:00-15:00&#xff0c;15:00-17:00共计8小时。 二、竞赛阶段 竞赛阶段 任务阶段 竞赛任务 竞赛时间 分值 第一阶段 基础设施设置与安全加固、网络安全事件响应、数…
阅读更多...
链表相关oj题

链表相关oj题

1.Leetcode203 移除链表元素 解题思路&#xff1a;从头节点开始进行元素删除&#xff0c;每删除一个元素&#xff0c;需要重新链接节点 struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode*dummyheadmalloc(sizeof(struct ListNode));dummyhea…
阅读更多...
spring5（四）：IOC 操作 Bean 管理(基于注解方式)

spring5（四）：IOC 操作 Bean 管理(基于注解方式)

IOC操作Bean管理&#xff08;基于xml方式&#xff09;前言一、注解1、概述二、入门案例1、Bean 的创建2、Bean的自动装配2.1 Autowired2、Qualifie3、Resource4、Value3、扫描组件3.1 配置文件版3.2 注解版4、测试前言 本博主将用CSDN记录软件开发求学之路上亲身所得与所学的心…
阅读更多...
Mysql常用命令

Mysql常用命令

mysql连接&#xff1a; [roothost]# mysql -u root -p Enter password:******创建数据库&#xff1a; CREATE DATABASE 数据库名&#xff1b; 删除数据库&#xff1a; drop database 数据库名; 使用mysqladmin删除数据库&#xff1a; [roothost]# mysqladmin -u root -p dr…
阅读更多...
【数据结构】链表OJ(二)

【数据结构】链表OJ(二)

Yan-英杰的博客 悟已往之不谏 知来者之可追 目录 一、反转链表 二、合并两个有序链表 三、链表分割 四、链表的回文结构 一、反转链表 输入&#xff1a;head [1,2,3,4,5] 输出&#xff1a;[5,4,3,2,1] 输入&#xff1a;head [1,2] 输出&#xff1a;[2,1] 示例 3&#xf…
阅读更多...
Vulnhub靶场----10、LazySysadmin

Vulnhub靶场----10、LazySysadmin

文章目录一、环境搭建二、渗透流程一、环境搭建 DC-7下载地址&#xff1a;https://download.vulnhub.com/dc/DC-9.zip kali&#xff1a;192.168.144.148 DC-9&#xff1a;192.168.144.157 二、渗透流程 1、信息收集nmap -sV -sT -p- -T4 192.168.144.157思路&#xff1a; 1、80…
阅读更多...
基于vivado（语言Verilog）的FPGA学习（3）——FPGA理论知识

基于vivado（语言Verilog）的FPGA学习（3）——FPGA理论知识

基于vivado&#xff08;语言Verilog&#xff09;的FPGA学习&#xff08;3&#xff09;——FPGA理论知识 文章目录基于vivado&#xff08;语言Verilog&#xff09;的FPGA学习&#xff08;3&#xff09;——FPGA理论知识1. FPGA介绍1.1.FPGA内部结构&#xff08;1&#xff09;. 可…
阅读更多...
【云原生|Docker】01-docker简介

【云原生|Docker】01-docker简介

目录 前言 Docker简介 1. 什么是docker 2. Docker和vm有什么区别 3. Docker架构 4. Docker特性 Docker安装 1. Docker版本介绍 2. Centos7安装docker 3. Docker校验 4. Docker启动 5. Docker配置文件 前言 接下来准备记录云原生系列的相关知识&#x…
阅读更多...
Linux防火墙的关闭

Linux防火墙的关闭

查看防火墙的状态打开终端输入如下命令systemctl status firewalld如图所示&#xff1a;running表示防火墙目前处于打开状态输入命令进行关闭防火墙&#xff1a;systemctl stop firewalld如图所示正常的用户是没有权限的&#xff0c;需要输入管理员的密码才能够进行关闭防火墙。…
阅读更多...
OpenAI GPT-4震撼发布：多模态大模型

OpenAI GPT-4震撼发布：多模态大模型

OpenAI GPT-4震撼发布&#xff1a;多模态大模型发布要点GPT4的新功能GPT-4:我能玩梗图GPT4:理解图片GPT4:识别与解析图片内容怎样面对GPT4申请 GPT-4 API前言&#xff1a; &#x1f3e0;个人主页&#xff1a;以山河作礼。 &#x1f4dd;​&#x1f4dd;:本文章是帮助大家更加了…
阅读更多...
中国版的“ChatGPT”狂飙的机会或许要出现了

中国版的“ChatGPT”狂飙的机会或许要出现了

⭐️我叫忆_恒心&#xff0c;一名喜欢书写博客的在读研究生&#x1f468;‍&#x1f393;。 如果觉得本文能帮到您&#xff0c;麻烦点个赞&#x1f44d;呗&#xff01; 近期会不断在专栏里进行更新讲解博客~~~ 有什么问题的小伙伴 欢迎留言提问欧&#xff0c;喜欢的小伙伴给个三…
阅读更多...
avue-crud组件的行内编辑实现失焦保存，在没有右侧操作栏的情况下

avue-crud组件的行内编辑实现失焦保存，在没有右侧操作栏的情况下

前言 关于 avue 框架&#xff0c;其实本来不想写一篇随笔记录的&#xff0c;因为目前在网上有很多文章&#xff0c;关于其配置项介绍的比较详细&#xff0c;而且官网上也有对应的文档&#xff0c;这两者结合足以满足大部分的开发需求。 不过&#xff0c;产品经理总会有些不一…
阅读更多...
[大二下]什么是NPM

[大二下]什么是NPM

[大二下]什么是npm? 什么是NPM? 最简单来回答: ​ 就是一个包管理器, 一个仓库, 谁需要里面的物品, 谁就拿 npm 全称 Node Package(译: 包,包裹) Manager(译:如下). 直译过来就是 Node的包管理, 但是我们真正咱们约定俗成的称 NPM为"Node的包管理器". npm是Jav…
阅读更多...
nvm使用-node版本切换-npm版本-node版本异常导致错误

nvm使用-node版本切换-npm版本-node版本异常导致错误

目录什么是nvm?为什么要用它&#xff1f;它改变的是谁的版本号&#xff1f;安装并使用安装前操作安装使用&#xff08;常用命令&#xff09;nvm -hnvm install \<version\> [arch]nvm listnvm use [version] [arch]其他什么是nvm? .nvm是一个node的版本管理工具&#x…
阅读更多...
【计算机图形学】扫面转换算法（DDA算法 中点画线算法 Bresenham画线算法）

【计算机图形学】扫面转换算法（DDA算法 中点画线算法 Bresenham画线算法）

模块1 扫描转换算法 一 实验目的 编写直线、弧线的光栅扫描转换算法&#xff0c;并对线宽与线形的算法加以探讨用DDA算法、中点画线算法、Bresenham画线算法绘制直线&#xff08;如果键盘输入数据&#xff0c;给出数据值&#xff1b;如果绘制图案&#xff0c;图案中应包含各种…
阅读更多...
机器看世界

机器看世界

博主简介 博主是一名大二学生&#xff0c;主攻人工智能研究。感谢让我们在CSDN相遇&#xff0c;博主致力于在这里分享关于人工智能&#xff0c;c&#xff0c;Python&#xff0c;爬虫等方面知识的分享。 如果有需要的小伙伴可以关注博主&#xff0c;博主会继续更新的&#xff0c…
阅读更多...
开源超级终端工具——WindTerm

开源超级终端工具——WindTerm

1、下载和安装&#xff08;我的是win10&#xff0c;其他版本各位自选&#xff09; Releases kingToolbox/WindTerm GitHub 安装的话&#xff0c;相信大家不用我赘述了。 初始界面是这样的&#xff1a; 2、WindTerm使用 2.1 本地会话&#xff08;最下面那个框&#xff0c;发…
阅读更多...
自动化测试实战篇(10)，找不到合适接口测试怎么办？Postman中mock模拟接口帮你解决烦恼

自动化测试实战篇(10)，找不到合适接口测试怎么办？Postman中mock模拟接口帮你解决烦恼

一般想学习接口测试&#xff0c;找不到相应的接口进行测试也是比较麻烦的一件事情&#xff0c;尤其是找一些能够正常显示想要的相应的数据的接口更是相对来讲比较复杂&#xff0c;那么有没有简单点造接口数据的方式呢&#xff1f; 像是mock框架&#xff0c;以它为基础的apifox…
阅读更多...
23.3.14打卡 2022年江西省大学生程序设计竞赛（正式赛）ABL

23.3.14打卡 2022年江西省大学生程序设计竞赛（正式赛）ABL

就写了签到, 其他题没写, 这场好像3题就银了 纪念一下3.14原粥率日 比赛链接:https://ac.nowcoder.com/acm/contest/43898 A题 Special Adjustment Method 题意 给出非负整数x, y, z 你可以让其中两个数字-1, 另外一个2, 使得x2y2z2x^2y^{2}z^{2}x2y2z2最大 题解 这题很容…
阅读更多...
站上风口，文心一言任重道远

站上风口，文心一言任重道远

目录正式发布时机选择逻辑推理AI绘画用户选择总结自从OpenAI公司的chatGPT发布以来&#xff0c;吸引了全球目光&#xff0c;同时也引起了我们的羡慕&#xff0c;希望有国产的聊天机器人&#xff0c;盼星星盼月亮&#xff0c;终于等来了百度文心一言的发布。 正式发布 3月16日…
阅读更多...
最新文章

Copyright @ 2022~2023