红黑树原理 部分模拟实现

1.红黑树的概念及性质

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

那么红黑树是如何确保没有一条路径会比其他路径长出两倍的呢？要弄清楚这点首先要引入红黑树的性质：

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的（没有连续的红结点）
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
由红黑树的性质可知可能出现的最短的路径是全黑，而最长的路径是黑红交替，因此没有一条路径会比其他路径长出两倍。

2.红黑树的部分实现

  2.1首先要定义红黑树结点：

enum color
{
	RED,
	BLACK
};

template<typename K,typename V>
struct RB_Node
{
	RB_Node<K, V>* _left;
	RB_Node<K, V>* _right;
	RB_Node<K, V>* _parent; //父节点指针
	pair<K, V> _kv;         //节点的值域
	color _col;             //颜色
	RB_Node(const pair<K, V>& kv) :
		_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_kv(kv),
		_col(RED)           //初始颜色为红色
	{}
};

2.2红黑树的插入

插入时先按照搜索二叉树的插入逻辑插入节点，后边在分情况进行变色/旋转处理

注意我们插入的节点默认是红色的，因为根据性质来说我们需要保证每条路径的黑色节点个数一样，如果我们插入的是黑色节点那么就需要控制其他所有路径下的黑色节点数量+1，这是很难做到的。

二叉搜索树的插入逻辑：

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

下面来讨论变色和旋转逻辑：

假设我们插入节点的父节点是黑色，实际上我们不需要做任何调整，但是如果父节点是红色的话就违反了红黑树的性质需要做出调整，（我们调整应该是一直向上的直到cur节点是根节点或者父节点为黑色）如下图这是可能出现的一种情况。

情况一当叔叔节点为红色时：

具体代码（注意根节点只能是黑色）

		while (parent && (parent->_col == RED))
		{
			node* grandparent = parent->_parent;
			node* uncle = nullptr;
			if (grandparent->_left == parent)
			{
				uncle = grandparent->_right;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;
					//继续向上处理
					cur = grandparent;
					parent = grandparent->_parent;
				}

情况二当叔叔不存在或者为黑色时（需要旋转加变色）：

具体旋转逻辑可以去看我前一篇博客http://t.csdnimg.cn/6ae1v

情况二又分为两种情况：

情况2.1（p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转）：

情况2.2（cur为红，p为红，g为黑，u不存在/u存在且为黑p为g的左孩子，cur为p的右孩子则针对p做左单旋转；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转则转换成了情况2.1）：

具体代码（上边全是grandparent->_left == parent，但是grandparent->_right== parent）处理的逻辑是一样或对称的，可以根据代码自行理解：

while (parent && (parent->_col == RED))
		{
			node* grandparent = parent->_parent;
			node* uncle = nullptr;
			if (grandparent->_left == parent)
			{
				uncle = grandparent->_right;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;
					//继续向上处理
					cur = grandparent;
					parent = grandparent->_parent;
				}
				else //叔叔不存在或者叔叔为黑色 旋转
				{
					if (parent->_left == cur)
					{
						RotateR(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					else
					{
						RotateL(parent);
						RotateR(grandparent);

						cur->_col = BLACK;
						grandparent->_col = RED;
					}
				}
				break;
			}
			else
			{
				uncle = grandparent->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;
					//继续向上处理
					cur = grandparent;
					parent = grandparent->_parent;
				}
				else //叔叔不存在或者叔叔为黑色 旋转
				{
					if (parent->_right == cur)
					{
						RotateL(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandparent);

						cur->_col = BLACK;
						grandparent->_col = RED;
					}
				}
				break;
			}
		}

3.源码

#pragma once
#include <iostream>
using namespace std;
enum color
{
	RED,
	BLACK
};

template<typename K,typename V>
struct RB_Node
{
	RB_Node<K, V>* _left;
	RB_Node<K, V>* _right;
	RB_Node<K, V>* _parent;
	pair<K, V> _kv;
	color _col;
	RB_Node(const pair<K, V>& kv) :
		_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_kv(kv),
		_col(RED)
	{}
};

template<typename K, typename V>
class RBTree
{
	typedef RB_Node<K, V> node;
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 (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new node(kv);
		if (cur->_kv.first > parent->_kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		while (parent && (parent->_col == RED))
		{
			node* grandparent = parent->_parent;
			node* uncle = nullptr;
			if (grandparent->_left == parent)
			{
				uncle = grandparent->_right;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;
					//继续向上处理
					cur = grandparent;
					parent = grandparent->_parent;
				}
				else //叔叔不存在或者叔叔为黑色 旋转
				{
					if (parent->_left == cur)
					{
						RotateR(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					else
					{
						RotateL(parent);
						RotateR(grandparent);

						cur->_col = BLACK;
						grandparent->_col = RED;
					}
				}
				break;
			}
			else
			{
				uncle = grandparent->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;
					//继续向上处理
					cur = grandparent;
					parent = grandparent->_parent;
				}
				else //叔叔不存在或者叔叔为黑色 旋转
				{
					if (parent->_right == cur)
					{
						RotateL(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandparent);

						cur->_col = BLACK;
						grandparent->_col = RED;
					}
				}
				break;
			}
		}
		_root->_col = BLACK;
		return true;
	}
	void RotateL(node* parent)
	{
		node* subr = parent->_right;
		node* subrl = subr->_left;
		node* ppnode = parent->_parent;

		parent->_right = subrl;
		parent->_parent = subr;
		subr->_left = parent;
		if (subrl)
			subrl->_parent = parent;

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

		subl->_right = parent;
		node* ppnode = parent->_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;
		}
	}
private:
	void _InOrder(node* root)
	{
		if (root == nullptr)
			return;

		_InOrder(root->_left);
		cout << root->_kv.first << endl;
		_InOrder(root->_right);
	}
public:
	void InOrder()
	{
		_InOrder(_root);
	}
private:
	node* _root = nullptr;
};

4.红黑树与AVL树的对比

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

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

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

相关文章

Redis和PHP的Bitmap于二进制串的相互转换

Redis和PHP的Bitmap于二进制串的相互转换

Redis和PHP的Bitmap于二进制串的相互转换 场景 错题集的存储&#xff0c;需要有正确的题号id集合&#xff0c;错误的题号id集合&#xff0c;两者并集后在全量题的集合中取反就是未答题号id 选型 基于场景的数据结构设计&#xff0c;有试过列表等&#xff0c;测试结果&#xff1…
阅读更多...
python笔记----少儿编程课程

python笔记----少儿编程课程

第1课&#xff1a; 认识新朋友-python 知识点&#xff1a; 1、在英文状态下编写Python语句。 2、内置函数print()将结果输出到标准的控制台上&#xff0c;它的基本语法格式如下&#xff1a; print("即将输出的内容") #输出的内容要用引号引起来&#xff0c;可…
阅读更多...
【Ant Design Vue的更新日志】

【Ant Design Vue的更新日志】

&#x1f308;个人主页: 程序员不想敲代码啊 &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共…
阅读更多...
SAP 创建BP 提示 CVI_MAPPING 011

SAP 创建BP 提示 CVI_MAPPING 011

原因编号不是外部给号的问题
阅读更多...
腾讯云TI平台的大模型精调解决方案

腾讯云TI平台的大模型精调解决方案

腾讯云TI平台的大模型精调解决方案 随着人工智能和大数据技术的快速发展&#xff0c;大模型在各行各业的应用日益广泛。然而&#xff0c;大规模模型的训练和部署面临着诸多挑战&#xff0c;包括训练资源的高效利用、模型训练的稳定性和国产化适配需求。腾讯云TI平台凭借其强大…
阅读更多...
智能网络构建：探索大模型在网络领域的应用

智能网络构建：探索大模型在网络领域的应用

网络领域以其高度复杂性和快速迭代为特点&#xff0c;完成从网络设计、配置、诊断到安全的网络任务需要广泛的专业知识。这些任务的固有复杂性&#xff0c;加上网络技术和协议不断变化的格局&#xff0c;为传统基于机器学习的方法带来了显著的障碍。这些方法在泛化和自动化网络…
阅读更多...
已训练好模型如何测试自己数据

已训练好模型如何测试自己数据

1、前言 上一篇博客详细介绍了利用MNIST数据集训练模型，得到了训练参数，那么如何将这训练好的模型，用于训练自己的数据呢？本博客详细介绍，如何利用上篇博客训练好的模型参数，来预测自己的数据集。 2、测试数据 2.1 数据准备 在测试自己数据前，确保你的数据格式与训练时…
阅读更多...
【linux/shell案例实战】解决Linux和Windows的换行符CRLF和LF问题

【linux/shell案例实战】解决Linux和Windows的换行符CRLF和LF问题

目录 一.什么是Linux 和 Windows 的换行符 CRLF 和 LF 二.使用Linux 中命令 dos2unix 和 unix2dos 实现CRLF 和LF的转换 三.使用 windows 中的代码编辑器实现 CRLF 和 LF 的转换&#xff08;Notepad&#xff09; 一.什么是Linux 和 Windows 的换行符 CRLF 和 LF CR是Carria…
阅读更多...
EDA 虚拟机 Synopsys Sentaurus TCAD 2018.06-SP2 CentOS7.9

EDA 虚拟机 Synopsys Sentaurus TCAD 2018.06-SP2 CentOS7.9

下载地址&#xff08;制作不易&#xff0c;下载使用需付费&#xff0c;不能接受的请勿下载&#xff09;&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1358rH_Ner1TYdc_TgoXrew?pwdyq3p 提取码&#xff1a;yq3p
阅读更多...
瑞文标准IQ智商测验题其中三项

瑞文标准IQ智商测验题其中三项

最近在网上看到想尝试一下&#xff0c;看到这三个题目感觉挺有意识&#xff01;&#xff01;&#xff01;
阅读更多...
如何进行黄金期货日内波段交易-EE trade

如何进行黄金期货日内波段交易-EE trade

日内波段交易是一种在单个交易日内抓取较大波段趋势的方法&#xff0c;旨在利用市场的短期波动获取利润。黄金期货市场由于其高波动性和高杠杆性&#xff0c;成为日内波段交易的理想选择。以下是黄金期货日内波段交易的详细策略和方法。 一、日内波段交易整体设计思想 1. 顺应…
阅读更多...
Redis数据迁移-RedisShake

Redis数据迁移-RedisShake

redis-shake是阿里云Redis团队开源的用于Redis数据迁移和数据过滤的工具。 一、基本功能 redis-shake它支持解析、恢复、备份、同步四个功能 恢复restore&#xff1a;将RDB文件恢复到目的redis数据库。 备份dump&#xff1a;将源redis的全量数据通过RDB文件备份起来。 解析deco…
阅读更多...
VUE中，table border属性的不同使用方式

VUE中，table border属性的不同使用方式

在vue中&#xff0c;使用table&#xff0c;在给table设置边框属性时&#xff0c;按照以往的习惯&#xff1a; <table border"1px solid"><table> 这种写法&#xff0c;产生的效果如下&#xff1a;下边、右边的边框明显和上边、左边不同。border属性设置…
阅读更多...
DBA联创：区块链的架构正在不断趋同

DBA联创：区块链的架构正在不断趋同

原文标题&#xff1a;《We’re All Building the Same Thing》 撰文&#xff1a;Jon Charbonneau&#xff0c;DBA 联创 编译&#xff1a;Tia&#xff0c;Techub News 介绍 这篇文章分析了以下内容 异步执行——为什么高性能集成区块链&#xff08;例如 Solana 和 Monad&…
阅读更多...
芒果YOLOv10改进64：主干Backbone篇RepVGG结构：简单但功能强大的卷积神经网络架构

芒果YOLOv10改进64：主干Backbone篇RepVGG结构：简单但功能强大的卷积神经网络架构

💡本篇内容：YOLOv10改进RepVGG结构：简单但功能强大的卷积神经网络架构 💡🚀🚀🚀本博客 改进源代码改进 适用于 YOLOv10 按步骤操作运行改进后的代码即可 💡本文提出改进 原创 方式：二次创新，YOLOv10 应部分读者要求，新增一篇RepVGG 论文理论部分 + 原创最…
阅读更多...
滑动窗口算法——部分OJ题详解

滑动窗口算法——部分OJ题详解

目录 关于滑动窗口 部分OJ题详解 209.长度最小的子数组 3.无重复字符的最长字串 1004.最大连续1的个数Ⅲ 1658.将x减到0的最小操作数 904.水果成篮 438.找到字符串中所有字母异位词 30.串联所有单词的子串 76.最小覆盖子串 关于滑动窗口 其实滑动窗口也是通过双指针…
阅读更多...
气膜移动宴会厅：现代化宴会解决方案—轻空间

气膜移动宴会厅：现代化宴会解决方案—轻空间

随着社会经济的发展和人们生活水平的提高&#xff0c;各类宴会、庆典和活动的需求日益增加。然而&#xff0c;传统的宴会厅受限于固定的地点和昂贵的建设成本&#xff0c;无法灵活应对不同规模和地点的需求。在此背景下&#xff0c;气膜移动宴会厅作为一种创新的解决方案&#…
阅读更多...
北京小程序开发如何选择开发团队与开发语言？

北京小程序开发如何选择开发团队与开发语言？

随着移动互联网的飞速发展&#xff0c;小程序的开发与使用也变得越来越频繁。对于商户来说&#xff0c;市面上的小程序开发团队数量众多又鱼龙混杂&#xff0c;应该如何选择合适的开发团队与开发语言呢&#xff1f; 一&#xff0e; 北京小程序的开发语言的种类及不同 北京小程…
阅读更多...
吉时利 Keithley2461 数字源表

吉时利 Keithley2461 数字源表

Keithley2461吉时利SMU高电流数字源表 2461 型图形化高电流数字 SourceMeter SMU 2461 高电流 SMU 凭借其 10A/1000W 脉冲电流和 7A/100W 直流电流能力以及双 18 位 1MS/s 数字转换器&#xff0c;优化用于检定和测试高功率材料、器件和模块&#xff0c;例如碳化硅 (SiC)、氮化…
阅读更多...
修改 app id - 鸿蒙 HarmonyOS Next

修改 app id - 鸿蒙 HarmonyOS Next

修改项目 app id 后通过真机 build run 的时候抛出了如下异常; 项目中更改后的配置与真机的不匹配; {app: {bundleName: "com.xxxxxx.xxx_harmony",vendor: "xxxxxx",versionCode: 1,versionName: "3.5.00",icon: "$media:app_icon",…
阅读更多...
最新文章

Copyright @ 2022~2023