数据结构中的平衡搜索树 --- 红黑树 （如何旋转与变色）

目录

红黑树的概念

红黑树的性质

红黑树节点的定义

红黑树的插入

1. 按照二叉搜索的树规则插入新节点

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

红黑树的概念

        红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

红黑树的性质

  • 1. 每个结点不是红色就是黑色
  • 2. 根节点是黑色的 
  • 3. 如果一个节点是红色的，则它的两个孩子结点是黑色的 
  • 4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
  • 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

红黑树节点的定义

enum Color
{
	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;
	Color _col; //节点颜色

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

为什么构造函数中的节点默认给的是红色？ 通过红黑树的性质能总结出：

性质3 - 代表着不能出现连续的红色节点

性质4 - 每条路径上都有相同数量的黑色节点

        这时会发现违反性质3比违反性质4的代价要更小，而事实上也的确是这样做的，可能会有疑问，这样还是红黑树嘛，其实新增节点之后是需要通过变色来达到红黑树的结构的。（如下）

示例：

此时我们会发现，最后的结构是符合红黑树的：没有出现连续的红色节点；每条路径上的黑色节点数量相同。

红黑树的插入

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

1. 按照二叉搜索的树规则插入新节点
template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;

	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;   //记录cur的父节点，方便进行链接

		while (cur)
		{
			if (kv.first < cur->_kv.first)  //插入的值小于存储的值
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first) //插入的值大于存储的值
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false; //相等，插入失败
			}

		}

		//注意：新增的节点构造是红色，所以这里不用给颜色
		cur = new Node(kv);  
		if (kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}

		cur->_parent = parent; 

		//...调整颜色


		return true;

	}


protected:
	Node* _root = nullptr;
};
2. 检测新节点插入后，红黑树的性质是否造到破坏

注意：关于旋转处理可以参考AVL树的旋转处理

        因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

约定：1.grandfather->_left = parent;  grandfather->_right = uncle; (父节点在左，叔节点在右）
grandfather为黑，parent为红，cur（新增节点）为红
① uncle节点存在且为红色  ----》 parent , uncle 改黑，grandfather改红，继续向上调整

② uncle节点不存在 or  存在且为黑  - 单旋

③ uncle节点不存在 or  存在且为黑  - 双旋


 

约定：2.grandfather->_left = uncle;  grandfather->_right = parent; （叔节点在左，父节点在右） 

（参考上面）

具体代码演示：

        //旋转+更改颜色
		while (parent && parent->_col == RED)
		{
			//记录祖先节点
			Node* grandfather = parent->_parent;
			
			//父节点是祖先节点的左子树
			if (grandfather->_left == parent)
			{
				Node* uncle = grandfather->_right;

				//①uncle节点存在且为红
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//继续向上调整
					cur = grandfather;
					parent = cur->_parent; //注意需要重新计数parent
				}
				else 
				{
					//②uncle不存在 or 存在且为黑 ->  变色 + 旋转
					if (cur == parent->_left) 
					{
						//单旋
						RotateR(grandfather); 
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//双旋
						RotateL(parent); 
						RotateR(grandfather);

						parent->_col = grandfather->_col = RED;
						cur->_col = BLACK;
					}

					break;

				}

			}
			else if (grandfather->_right == parent) //父节点是祖先节点的右子树
			{
				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)
					{
						//单旋
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//双旋
						RotateR(parent);
						RotateL(grandfather);

						parent->_col = grandfather->_col = RED;
						cur->_col = BLACK;
					}

					break;

				}

			}
			else
			{
				assert(false); 
			}

		}
	
		//结尾做保险处理，无论什么情况，根节点置成黑
		_root->_col = BLACK;

附上红黑树(测试是否是红黑树）部分代码：

                                                                                                RBTree.h

#pragma once
#include <iostream>
#include <assert.h>
#include <string>

using namespace std;

enum Color
{
	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;
	Color _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:
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	//检查是否是红黑树
	bool IsBalance()
	{
		//检查1：根节点颜色
		if (_root && _root->_col != BLACK)
		{
			cout << "根节点为红" << endl;
			return false;
		}

		//检查2：是否存在连续红色节点

		//检查3：每条路径上的黑色节点是否相同

		return _Check(_root, 0);

	}

	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;   //记录cur的父节点，方便进行链接

		while (cur)
		{
			if (kv.first < cur->_kv.first)  //插入的值小于存储的值
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first) //插入的值大于存储的值
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false; //相等，插入失败
			}

		}

		//注意：新增的节点构造是红色，所以这里不用给颜色
		cur = new Node(kv);  
		if (kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}

		cur->_parent = parent; 

		//旋转+更改颜色
		while (parent && parent->_col == RED)
		{
			//记录祖先节点
			Node* grandfather = parent->_parent;
			
			//父节点是祖先节点的左子树
			if (grandfather->_left == parent)
			{
				Node* uncle = grandfather->_right;

				//①uncle节点存在且为红
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//继续向上调整
					cur = grandfather;
					parent = cur->_parent; //注意需要重新计数parent
				}
				else 
				{
					//②uncle不存在 or 存在且为黑 ->  变色 + 旋转
					if (cur == parent->_left) 
					{
						//单旋
						RotateR(grandfather); 
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//双旋
						RotateL(parent); 
						RotateR(grandfather);

						parent->_col = grandfather->_col = RED;
						cur->_col = BLACK;
					}

					break;

				}

			}
			else if (grandfather->_right == parent) //父节点是祖先节点的右子树
			{
				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)
					{
						//单旋
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//双旋
						RotateR(parent);
						RotateL(grandfather);

						parent->_col = grandfather->_col = RED;
						cur->_col = BLACK;
					}

					break;

				}

			}
			else
			{
				assert(false); 
			}

		}
	
		//结尾做保险处理，无论什么情况，根节点置成黑
		_root->_col = BLACK;

		return true;
	}


protected:

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

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

	bool _Check(Node* root, int BlackNums)
	{
		if (root == nullptr)
		{
			cout <<BlackNums << endl;
			return true;
		}

		//这里是传值返回
		if (root->_col == BLACK)
			++BlackNums;

		//root与root的子树不好判断，因为节点不一定有子树，但是一定有父节点
		if (root->_col == RED &&root->_parent && root->_parent->_col == RED)
		{
			cout << "存在连续的红色节点" << endl;
			return false;
		}

		return _Check(root->_left, BlackNums)
			&& _Check(root->_right, BlackNums);

	}

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

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

		//提前记录祖先节点
		Node* pparent = parent->_parent;

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

		//值得注意的是，parent节点不一定为根节点，也就是旋转的可能是一棵子树而不是整棵树
		if (pparent == nullptr) //意味着parent节点是根节点
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			//判断parent 在 祖先节点的左还是右
			if (pparent->_right == parent)
			{
				pparent->_right = subR;
			}
			else
			{
				pparent->_left = subR;
			}

			subR->_parent = pparent;  //更改subR的父节点
		}

	}

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

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

		//提前记录祖先节点
		Node* pparent = parent->_parent;

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

		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			//判断parent 在 祖先节点的左还是右
			if (pparent->_right == parent)
			{
				pparent->_right = subL;
			}
			else
			{
				pparent->_left = subL;
			}

			subL->_parent = pparent;  //更改subR的父节点
		}

	}


protected:
	Node* _root = nullptr;
};


void Test_RBTree1()
{
	int arr1[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	int arr2[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };

	RBTree<int, int> t1;

	for (auto e : arr1)
	{
		t1.Insert(make_pair(e, e));
		cout << e << "插入:" << t1.IsBalance() << endl;  //插入进行检查
	}

	t1.InOrder();
	cout << t1.IsBalance() << endl;
}

红黑树与AVL树的比较
        红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O($log_2 N$)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

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

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

相关文章

基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的农作物害虫检测系统（深度学习模型+UI界面+训练数据集）

基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的农作物害虫检测系统（深度学习模型+UI界面+训练数据集）

摘要&#xff1a;开发农作物害虫检测系统对于提高农业生产效率和作物产量具有关键作用。本篇博客详细介绍了如何运用深度学习构建一个农作物害虫检测系统&#xff0c;并提供了完整的实现代码。该系统基于强大的YOLOv8算法&#xff0c;并对比了YOLOv7、YOLOv6、YOLOv5&#xff0…
阅读更多...
Linux——多线程

Linux——多线程

目录 线程概念 线程控制 线程创建 进程 vs 线程 线程异常 线程等待 线程终止 pthread_cancel 进程替换 线程分离 线程互斥 mutex mutex接口 mutex的理解 互斥锁的实现 可重入和线程安全 死锁 什么是死锁 死锁产生的必要条件 避免死锁 线程同步 概念 条件…
阅读更多...
论坛管理系统|基于Spring Boot+ Mysql+Java+B/S架构的论坛管理系统设计与实现(可运行源码+数据库+设计文档+部署说明+视频演示)

论坛管理系统|基于Spring Boot+ Mysql+Java+B/S架构的论坛管理系统设计与实现(可运行源码+数据库+设计文档+部署说明+视频演示)

推荐阅读100套最新项目 最新ssmjava项目文档视频演示可运行源码分享 最新jspjava项目文档视频演示可运行源码分享 最新Spring Boot项目文档视频演示可运行源码分享 目录 目录 前台功能效果图 管理员功能登录前台功能效果图 用户功能模块 系统功能设计 数据库E-R图设计 l…
阅读更多...
webpack面试题

webpack面试题

1、webpack是干什么的 Webpack是一个现代的JavaScript应用程序的静态模块打包工具。当webpack处理应用程序时&#xff0c;它会在内部构建一个依赖图&#xff0c;此依赖图对应映射到项目所需的每个模块&#xff0c;然后将所有这些模块打包成一个或多个bundle。Webpack的主要功能…
阅读更多...
Java初阶数据结构队列的实现

Java初阶数据结构队列的实现

1.队列的概念 1.队列就是相当于排队打饭 2.在排队的时候就有一个队头一个队尾。 3.从队尾进对头出 4.所以他的特点就是先进先出 所以我们可以用链表来实现 单链表实现要队尾进队头出{要有last 尾插头删} 双向链表实现效率高&#xff1a;不管从哪个地方当作队列都是可以的&…
阅读更多...
HttpContext请求接收上下文模块设计与实现(http模块四)

HttpContext请求接收上下文模块设计与实现(http模块四)

目录 类功能 类定义 类实现 编译测试 类功能 类定义 // HttpContext接收请求上下文模块功能设计 typedef enum {RECV_HTTP_ERROR,RECV_HTTP_LINE,RECV_HTTP_HEAD,RECV_HTTP_BODY,RECV_HTTP_OVER } HttpRecvStatu;class HttpContext { private:int _resp_statu; …
阅读更多...
Games101笔记-变换

Games101笔记-变换

Scale Reflection Shear Rotate 没有额外提示默认绕原点旋转 线性变换 Transiation 不属于线性变换&#xff0c;仿射变换 齐次坐标 二维的点和向量增加一个维度 点加点等于两个点的中点 所有的仿射变换都可以写成齐次坐标的形式 在表示二维情况下的仿射变换时&#…
阅读更多...
Linux驱动分离与分层的简介

Linux驱动分离与分层的简介

一. 简介 我们在前面几章编写的设备驱动都非常的简单&#xff0c;都是对 IO 进行最简单的读写操作。 像 I2C 、SPI 、 LCD 等这些复杂外设的驱动就不能这么去写了&#xff0c; Linux 系统要考虑到驱动的可重用性&#xff0c;因 此&#xff0c;提出了驱动的分离与分层这样的软…
阅读更多...
Maven: There are test failures.（已解决）

Maven: There are test failures.（已解决）

问题解决办法 进行package打包时报错如下&#xff1a; 然后这些并不能看出是测试的哪里的问题&#xff0c;可以点击上一级进行查看更详细的错误&#xff0c;越向上日志越详细&#xff0c;可以看到是52行出了错误&#xff0c; 52对应代码如下&#xff1a; 原因是存在注册的测…
阅读更多...
基于FPGA的图像锐化算法（USM）设计

基于FPGA的图像锐化算法（USM）设计

免费获取源码请关注微信号《FPGA学习笔记册》&#xff01; 1.图像锐化算法说明 图像锐化算法在实际的图像处理应用很广泛&#xff0c;例如&#xff1a;医学成像、工业检测和军事领域等&#xff1b;它的作用就是将模糊的图像变的更加清晰。常用的图像锐化算法有拉普拉斯算子、s…
阅读更多...
记录一下在Pycharm中虚拟环境的创建

记录一下在Pycharm中虚拟环境的创建

如果在Pycharm中要新建一个虚拟环境&#xff0c;那你可以在Terminal中选择Command Prompt&#xff0c;在这里面执行相关命令 一、安装了Anaconda&#xff0c;创建虚拟环境 当你使用解释器是Anaconda提供的时&#xff0c;你可以使用conda命令执行&#xff0c;见以下操作&#x…
阅读更多...
Acwing.4261 孤独的照片(贡献法）

Acwing.4261 孤独的照片(贡献法）

题目 Farmer John 最近购入了 N 头新的奶牛&#xff0c;每头奶牛的品种是更赛牛&#xff08;Guernsey&#xff09;或荷斯坦牛&#xff08;Holstein&#xff09;之一。 奶牛目前排成一排&#xff0c;Farmer John 想要为每个连续不少于三头奶牛的序列拍摄一张照片。 然而&…
阅读更多...
华为组网：核心交换机旁挂防火墙，基于ACL重定向配置实验

华为组网：核心交换机旁挂防火墙，基于ACL重定向配置实验

如图所示&#xff0c;由于业务需要&#xff0c;用户有访问Internet的需求。 用户通过接入层交换机SwitchB和核心层交换机SwitchA以及接入网关Router与Internet进行通信。为了保证数据和网络的安全性&#xff0c;用户希望保证Internet到服务器全部流量的安全性&#xff0c;配置重…
阅读更多...
Flask开发类似jenkins构建自动化测试任务工具

Flask开发类似jenkins构建自动化测试任务工具

1、自动化 某一天你入职了一家高大上的科技公司&#xff0c;开心的做着软件测试的工作&#xff0c;每天点点点&#xff0c;下班就走&#xff0c;晚上陪女朋友玩王者&#xff0c;生活很惬意。 但是美好时光一般不长&#xff0c;这种生活很快被女主管打破。为了提升公司测试效率…
阅读更多...
如何“使用Docker快速安装Jenkins，在CentOS7”？

如何“使用Docker快速安装Jenkins，在CentOS7”？

1、运行 docker run -d --namejenkins -p 8080:8080 jenkins/jenkins 2、查看日志 &#xff0c;使用 "docker logs -f jenkins",可以持续刷新日志 docker logs jenkins 3、通过命令查看密码 docker exec -it jenkins cat /var/jenkins_home/secrets/initialAdminP…
阅读更多...
用云服务器构建gpt和stable-diffusion大模型

用云服务器构建gpt和stable-diffusion大模型

用云服务器构建gpt和stable-diffusion大模型 一、前置知识二、用云端属于自己的聊天chatGLM3step1、项目配置step2、环境配置1、前置知识2、环境配置流程 step3、创建镜像1、前置知识2、创建镜像流程 step4、通过 Gradio 创建ChatGLM交互界面1、前置知识2、创建ChatGLM交互界面…
阅读更多...
YOLOv8改进 | 图像去雾 | 特征融合注意网络FFA-Net增强YOLOv8对于模糊图片检测能力（北大和北航联合提出）

YOLOv8改进 | 图像去雾 | 特征融合注意网络FFA-Net增强YOLOv8对于模糊图片检测能力（北大和北航联合提出）

一、本文介绍 本文给大家带来的改进机制是由北大和北航联合提出的FFA-net: Feature Fusion Attention Network for Single Image Dehazing图像增强去雾网络&#xff0c;该网络的主要思想是利用特征融合注意力网络&#xff08;Feature Fusion Attention Network&#xff09;直接…
阅读更多...
基于单片机的Buck型变换器控制

基于单片机的Buck型变换器控制

摘要&#xff1a;对于电子产品而言&#xff0c;必不可少的供电电源&#xff0c;随着人们对电子产品的安全性能要求越来越高&#xff0c;变相的对供电电源提出了新的机遇和挑战。Buck型变换器控制的研究一直是该领域重要的一方面&#xff0c;对于直流斩波电路而言&#xff0c;研…
阅读更多...
C#在未安装Halcon环境中调用Halcon的方法

C#在未安装Halcon环境中调用Halcon的方法

1.1 找到Halcon的dll 将Halcon安装路径下的所有dll复制进一个文件夹内 1.2 放入程序目录下 1.3 设置程序引用目录文件 在App.config中添加如下代码 <runtime><assemblyBinding xmlns"urn:schemas-microsoft-com:asm.v1"><probing privatePath"H…
阅读更多...
前端开发小技巧【Vue篇】 - 样式穿透 + 绑定变量

前端开发小技巧【Vue篇】 - 样式穿透 + 绑定变量

前言 样式穿透 Vue都是通过深度选择器来样式穿透的。当我们在写项目的时候&#xff0c;经常会导入第三方库&#xff0c;有些特殊的情况&#xff0c;就是在导入第三方库后&#xff0c;呈现的样式并不是我们想要的样式&#xff0c;所以我们需要对第三方的样式进行修改&#xff1…
阅读更多...
最新文章

Copyright @ 2022~2023