C++第十六讲：红黑树

C++第十六讲：红黑树

  • 1.什么是红黑树
    • 1.1红黑树的特点
  • 2.MyRBTree实现
    • 2.1红黑树的结构
    • 2.2红黑树的插入
      • 2.2.1插入的总体逻辑
      • 2.2.2情况一：变色
      • 2.2.3情况二：单旋 + 变色
      • 2.2.4情况三：双旋 + 变色
      • 2.2.4插入代码总结
    • 2.3红黑树的检查
    • 2.4完整代码实现
  • 3.红黑树的删除

1.什么是红黑树

总结：
1.每一个结点不是红色就是黑色。
2.根节点必须是黑色的。
3.红色节点的子节点必须是黑节点，也就是说任意一条道路上不会有连续的红色结点。
4.对任意一个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的黑色结点。

上面说的是红黑树的规则，但是在算法导论上，又补充了一条规则：每一个叶子结点（NIL）都是黑色的规则，这个叶子结点不是先前理解的叶子结点，而是空结点。
在这里插入图片描述
所以上面的图里面其实是有6条路径的，而不是两条路径。

1.1红黑树的特点

根据红黑树的规则可以推出：红黑树能够确保最长路径不超过最短路径的两倍，我们分析一下为什么：

假设每一个路径上都存在bh个黑色结点，那么在极端情况下存在的最短路径为：全部都是黑色结点，也就是bh个结点。最长路径为：一个黑色结点，一个红色结点，交叉排列，也就是2bh个结点，所以说，这就保证了，最长路径不会超过最短路径的两倍。

2.MyRBTree实现

2.1红黑树的结构

红黑树，首先要有颜色的标识，而且要有结点的表示，最后就是红黑树的总体表示：

enum Color {
	BLACK,
	RED
};

template <class K, class V>
struct RBTreeNode
{
	pair<K.V> _kv;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	Color color;

	RBTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
	{}
};

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node; 
public:

private:
	Node* _root = nullptr;
};

2.2红黑树的插入

2.2.1插入的总体逻辑

1.首先要保证二叉搜索树的逻辑，也就是二叉搜索树的插入逻辑
2.要保证红黑树的规则，这里会存在三种情况，下面就是来讨论三种情况的

插入的总体逻辑就是二叉搜索树的插入：

bool insert(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)
	{
		parent = cur;
		if (kv->first < cur->_kv.first)
			cur = cur->_left;
		else if (kv->first > cur->_kv.first)
			cur = cur->_right;
		else return false;
	}
	cur = new Node(kv);
	cur->color = RED;//先假设插入的结点是红色的
}

2.2.2情况一：变色

在这里插入图片描述

2.2.3情况二：单旋 + 变色

在这里插入图片描述

2.2.4情况三：双旋 + 变色

在这里插入图片描述

2.2.4插入代码总结

bool insert(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)
	{
		parent = cur;
		if (kv->first < cur->_kv.first)
			cur = cur->_left;
		else if (kv->first > cur->_kv.first)
			cur = cur->_right;
		else return false;
	}
	cur = new Node(kv);
	cur->color = RED;
	if (cur->_kv.first < parent->_kv.first) parent->_left = cur;
	else parent->_right = cur;
	cur->_parent = parent;

	//变色，当多个红色在一起出现时，就要进行变色处理
	while (parent && parent->color == RED)
	{
		Node* grandfather = parent->_parent;
		if (grandfather->_left == parent)
		{
			Node* uncle = grandfather->_right;
			if (uncle && uncle->color == RED)
			{
				//当unclde存在且为红色时，进行变色
				parent->color = uncle->color = BLACK;
				grandfather->color = RED;
				
				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				//当uncle不存在或者unclde存在但为黑时，旋转 + 变色
				if (cur == parent->_left)
				{
					//插入的位置在左边，单旋 + 变色
					RotateR(grandfather);
					parent->color = BLACK;
					grandfather->color = RED;
				}
				else
				{
					RotateL(parent);
					RotateR(grandfather);
					cur->color = BLACK;
					grandfather->color = RED;
				}
				break;
			}
		}
		else//grandfather->_right == parent
		{
			Node* uncle = grandfather->_left;
			if (uncle && uncle->color == RED)
			{
				//当unclde存在且为红色时，进行变色
				parent->color = uncle->color = BLACK;
				grandfather->color = RED;

				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				//当uncle不存在或者unclde存在但为黑时，旋转 + 变色
				if (cur == parent->_right)
				{
					//插入的位置在右边，单旋 + 变色
					RotateL(grandfather);
					parent->color = BLACK;
					grandfather->color = RED;
				}
				else
				{
					RotateR(parent);
					RotateL(grandfather);
					cur->color = BLACK;
					grandfather->color = RED;
				}
				break;
			}
		}
	}
	
	_root->color = BLACK;//这一点也要注意
	return true;
}

2.3红黑树的检查

我们创建的红黑树结构是否正确，还需要我们进行检查，检查的方法为检查各个路径下的黑色结点是否相同。算法为先算出来一条道路上的黑色结点数量，再通过递归检查所有道路上的黑色结点数量是否相同：

bool Check(Node* root, int blackNum, const int refNum)
{
	if (root == nullptr)
	{
		//root为空，证明一条道路走完了，此时再进行数量的比较
		if (blackNum != refNum)
		{
			cout << "路径上的黑色结点数目为：" << blackNum << endl;
			cout << "和参考值的黑色结点数目不同：" << refNum << endl;
			return false;
		}
		return true;
	}
	
	if (root->color == BLACK) blackNum++;
	if (root->color == RED && root->_parent->color == RED)
	{
		cout << "存在连续的红色结点" << endl;
		return false;
	}
	return Check(root->_left, blackNum, refNum) &&
		Check(root->_right, blackNum, refNum);
}

bool IsBalance()
{
	if (_root == nullptr) return true;
	if (_root->color == RED) return false;
	
	int refNum = 0;//设置一个参考值
	Node* cur = _root;
	while (cur)
	{
		if (cur->color == BLACK) refNum++;
		cur = cur->_left;
	}

	return Check(_root, 0, refNum);//递归进行检查
}

2.4完整代码实现

#pragma once

enum Color {
	BLACK,
	RED
};

template <class K, class V>
struct RBTreeNode
{
	pair<K, V> _kv;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	Color color;

	RBTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
	{}
};

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	bool Insert(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)
		{
			parent = cur;
			if (kv.first < cur->_kv.first)
				cur = cur->_left;
			else if (kv.first > cur->_kv.first)
				cur = cur->_right;
			else return false;
		}
		cur = new Node(kv);
		cur->color = RED;
		if (cur->_kv.first < parent->_kv.first) parent->_left = cur;
		else parent->_right = cur;
		cur->_parent = parent;

		//变色，当多个红色在一起出现时，就要进行变色处理
		while (parent && parent->color == RED)
		{
			Node* grandfather = parent->_parent;
			if (grandfather->_left == parent)
			{
				Node* uncle = grandfather->_right;
				if (uncle && uncle->color == RED)
				{
					//当unclde存在且为红色时，进行变色
					parent->color = uncle->color = BLACK;
					grandfather->color = RED;
					
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					//当uncle不存在或者unclde存在但为黑时，旋转 + 变色
					if (cur == parent->_left)
					{
						//插入的位置在左边，单旋 + 变色
						RotateR(grandfather);
						parent->color = BLACK;
						grandfather->color = RED;
					}
					else
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->color = BLACK;
						grandfather->color = RED;
					}
					break;
				}
			}
			else//grandfather->_right == parent
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->color == RED)
				{
					//当unclde存在且为红色时，进行变色
					parent->color = uncle->color = BLACK;
					grandfather->color = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					//当uncle不存在或者unclde存在但为黑时，旋转 + 变色
					if (cur == parent->_right)
					{
						//插入的位置在右边，单旋 + 变色
						RotateL(grandfather);
						parent->color = BLACK;
						grandfather->color = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->color = BLACK;
						grandfather->color = RED;
					}
					break;
				}
			}
		}
		
		_root->color = BLACK;//这一点也要注意
		return true;
	}

	bool Check(Node* root, int blackNum, const int refNum)
	{
		if (root == nullptr)
		{
			//root为空，证明一条道路走完了，此时再进行数量的比较
			if (blackNum != refNum)
			{
				cout << "路径上的黑色结点数目为：" << blackNum << endl;
				cout << "和参考值的黑色结点数目不同：" << refNum << endl;
				return false;
			}
			return true;
		}
		
		if (root->color == BLACK) blackNum++;
		if (root->color == RED && root->_parent->color == RED)
		{
			cout << "存在连续的红色结点" << endl;
			return false;
		}
		return Check(root->_left, blackNum, refNum) &&
			Check(root->_right, blackNum, refNum);
	}

	bool IsBalance()
	{
		if (_root == nullptr) return true;
		if (_root->color == RED) return false;
		
		int refNum = 0;//设置一个参考值
		Node* cur = _root;
		while (cur)
		{
			if (cur->color == BLACK) refNum++;
			cur = cur->_left;
		}

		return Check(_root, 0, refNum);//递归进行检查
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

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

	int Size()
	{
		return _Size(_root);
	}

	Node* Find(const K& key)
	{
		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;
	}

protected:
	int _Size(Node* root)
	{
		if (root == nullptr)
			return 0;

		return _Size(root->_left) + _Size(root->_right) + 1;
	}

	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 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;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
	}

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

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

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

private:
	Node* _root = nullptr;
};

3.红黑树的删除

红黑树的删除不做讲解，感兴趣的自行了解，《算法导论》或《STL源码剖析》中都有讲解。

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

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

相关文章

KubeKey一键安装部署k8s集群和KubeSphere详细教程

KubeKey一键安装部署k8s集群和KubeSphere详细教程

目录 一、KubeKey简介 二、k8s集群KubeSphere安装 集群规划 硬件要求 Kubernetes支持版本 操作系统要求 SSH免密登录 配置集群时钟 所有节点安装依赖 安装docker DNS要求 存储要求 下载 KubeKey 验证KubeKey 配置集群文件 安装集群 验证命令 登录页面 一、Ku…
阅读更多...
Java 值传递

Java 值传递

1 形参&实参 方法的定义可能会用到参数&#xff0c;参数在程序语言中分为&#xff1a; 实参&#xff1a;用于传递给函数/方法的参数&#xff0c;必须有确定的值。 形参&#xff1a;用于定义函数/方法&#xff0c;接收实参&#xff0c;不需要有确定的值。 String hello …
阅读更多...
开源一款I2C电机驱动扩展板-FreakStudio多米诺系列

开源一款I2C电机驱动扩展板-FreakStudio多米诺系列

总线直流电机扩展板 原文链接&#xff1a; FreakStudio的博客 摘要 设计了一个I2C电机驱动板&#xff0c;通过I2C接口控制多个电机的转速和方向&#xff0c;支持刹车和减速功能。可连接16个扩展板&#xff0c;具有PWM输出、过流过热保护和可更换电机驱动芯片。支持按键控制…
阅读更多...
论文笔记（七十二）Reward Centering（三）

论文笔记（七十二）Reward Centering（三）

Reward Centering&#xff08;三&#xff09; 文章概括摘要3 基于值的奖励中心化4 案例研究&#xff1a; 以奖励为中心的 Q-learning5 讨论、局限性与未来工作致谢 文章概括 引用&#xff1a; article{naik2024reward,title{Reward Centering},author{Naik, Abhishek and Wan…
阅读更多...
内部知识库的核心模块是什么？

内部知识库的核心模块是什么？

内容概要 现代企业内部知识库的架构设计遵循系统性、可扩展性与安全性三重原则&#xff0c;其核心模块的协同运作构成完整的知识资产运营体系。在知识存储层&#xff0c;基于结构化分类的存储管理采用多级目录架构&#xff08;如客户服务库、培训学习库&#xff09;&#xff0…
阅读更多...
kafka基本知识

kafka基本知识

什么是 Kafka&#xff1f; Apache Kafka 是一个开源的分布式流处理平台&#xff0c;最初由 LinkedIn 开发&#xff0c;后来成为 Apache 软件基金会的一部分。Kafka 主要用于构建实时数据管道和流处理应用程序。它能够高效地处理大量的数据流&#xff0c;广泛应用于日志收集、数…
阅读更多...
P8716 [蓝桥杯 2020 省 AB2] 回文日期

P8716 [蓝桥杯 2020 省 AB2] 回文日期

1 题目说明 2 题目分析 暴力不会超时&#xff0c;O(n)的时间复杂度&#xff0c; < 1 0 8 <10^8 <108。分析见代码&#xff1a; #include<iostream> #include<string> using namespace std;int m[13]{0,31,28,31,30,31,30,31,31,30,31,30,31};// 判断日期…
阅读更多...
手机时钟精确到秒

手机时钟精确到秒

这里以小米手机 MIUI 系统 举例 进入开发者模式 设置 - 我的设备 - 全部参数与信息 快速连续多次点击 MIUI 版本选框&#xff0c;即可进入开发者模式&#xff1b; 打开时间悬浮窗 设置 - 更多设置 - 开发者选项&#xff1b; 滑动至 输入 模块&#xff0c;开启时间悬浮窗&a…
阅读更多...
京东广告基于 Apache Doris 的冷热数据分层实践

京东广告基于 Apache Doris 的冷热数据分层实践

一、背景介绍 京东广告围绕Apache Doris建设广告数据存储服务&#xff0c;为广告主提供实时广告效果报表和多维数据分析服务。历经多年发展&#xff0c;积累了海量的广告数据&#xff0c;目前系统总数据容量接近1PB&#xff0c;数据行数达到18万亿行&#xff0c;日查询请求量8…
阅读更多...
ubuntu新系统使用指南

ubuntu新系统使用指南

1. 更新源 2. 配置rime 输入法 sudo apt install ibus-rimeibus-setup #打开配置界面添加雾凇拼音 cd ~/Documents/Tool/input_source/plumgit clone --depth 1 https://github.com/rime/plum plum #没有梯子就劝退cd plum/bash rime-install iDvel/rime-ice:others/recipe…
阅读更多...
给小米/红米手机root（工具基本为官方工具）——KernelSU篇

给小米/红米手机root（工具基本为官方工具）——KernelSU篇

目录 前言准备工作下载刷机包xiaomirom下载刷机包【适用于MIUI和hyperOS】“hyper更新”微信小程序【只适用于hyperOS】 下载KernelSU刷机所需程序和驱动文件 开始刷机设置手机第一种刷机方式【KMI】推荐提取boot或init_boot分区 第二种刷机方式【GKI】不推荐 结语 前言 刷机需…
阅读更多...
Liunx（CentOS-6-x86_64）系统安装MySql（5.6.50）

Liunx（CentOS-6-x86_64）系统安装MySql（5.6.50）

一&#xff1a;安装Liunx&#xff08;CentOS-6-x86_64&#xff09; 安装Liunx&#xff08;CentOS-6-x86_64&#xff09; 二&#xff1a;下载MySql&#xff08;5.6.50&#xff09; MySql下载官网 二&#xff1a;安装MySql 2.1 将mysql上传到Liunx 文件地址 /usr/local/ 2…
阅读更多...
2025版-Github账号注册详细过程

2025版-Github账号注册详细过程

目录 1.访问GitHub官网 2. 点击“Sign up”按钮 3. 填写注册信息 4. 验证机器人 5. 点击“Create account”按钮 6. 验证邮箱 7. 完成注册 8. 初始设置&#xff08;可选&#xff09; 9. 开始使用 注意事项 1.访问GitHub官网 打开浏览器&#xff0c;访问 GitHub官网。 …
阅读更多...
基于CentOS7安装kubesphere和Kubernetes并接入外部ES收集日志

基于CentOS7安装kubesphere和Kubernetes并接入外部ES收集日志

一、修改所有节点主机名 主节点就修改成master hostnamectl set-hostname master 然后输入bash刷新当前主机名 工作节点1就修改成node1 hostnamectl set-hostname node1 然后输入bash刷新当前主机名 二、全部节点安装依赖并同步时间 yum -y install socat conntrack ebta…
阅读更多...
halcon 条形码、二维码识别、opencv识别

halcon 条形码、二维码识别、opencv识别

一、条形码 函数介绍 create_bar_code_model * 1.创建条码读取器的模板 * 参数一&#xff1a;通用参数的名称&#xff0c;针对条形码模型进行调整。默认值为空 * 参数二&#xff1a;针对条形码模型进行调整 * 参数三&#xff1a;条形码模型的句柄。 create_bar_code_model (…
阅读更多...
【用deepseek和chatgpt做算法竞赛】——还得DeepSeek来 -Minimum Cost Trees_5

【用deepseek和chatgpt做算法竞赛】——还得DeepSeek来 -Minimum Cost Trees_5

往期 【用deepseek和chatgpt做算法竞赛】——华为算法精英实战营第十九期-Minimum Cost Trees_0&#xff1a;介绍了题目和背景【用deepseek和chatgpt做算法竞赛】——华为算法精英实战营第十九期-Minimum Cost Trees_1&#xff1a;题目输入的格式说明&#xff0c;选择了邻接表…
阅读更多...
红帽7基于kickstart搭建PXE环境

红帽7基于kickstart搭建PXE环境

Kickstart 文件是一种配置文件&#xff0c;用于定义 Linux 系统安装过程中的各种参数&#xff0c;如分区、网络配置、软件包选择等。system-config-kickstart 提供了一个图形界面&#xff0c;方便用户快速生成这些配置文件。 用户可以通过图形界面进行系统安装的详细配置&…
阅读更多...
【Linux网络】TCP/IP地址的有机结合（有能力VS100%？？？），IP地址的介绍

【Linux网络】TCP/IP地址的有机结合（有能力VS100%？？？），IP地址的介绍

目录 1.背景知识&#xff08;更好的理解TCP/IP的结合&#xff09; 1.1远距离的传输要经过很多的子网&#xff0c;很多的路由器 1.2IP在OSI标准的网络层 1.3路由器的多个IP 2.TCP和IP的有机结合 2.1IP确定怎么选择路径&#xff0c;数据链接就是具体的实现 2.2问题背景&am…
阅读更多...
ue5 Arch vis AI traffic system 车辆系统添加不同种类的车

ue5 Arch vis AI traffic system 车辆系统添加不同种类的车

一、前置条件 资源包拥有二、步骤 添加第二辆车 在父级蓝图底下创建子级蓝图 打开子级蓝图 替换骨骼网格体 创建动画蓝图&#xff0c;骨骼选择该骨骼网格体的骨骼 连接动画蓝图 添加动画蓝图 添加资源包
阅读更多...
3分钟idea接入deepseek

3分钟idea接入deepseek

DeepSeek简介 DeepSeek 是杭州深度求索人工智能基础技术研究有限公司开发的一系列大语言模型&#xff0c;背后是知名量化资管巨头幻方量化3。它专注于开发先进的大语言模型和相关技术&#xff0c;拥有多个版本的模型&#xff0c;如 DeepSeek-LLM、DeepSeek-V2、DeepSeek-V3 等&…
阅读更多...
最新文章

Copyright @ 2022~2023