数据结构——红黑树

目录

概念

性质

结点的定义 

插入

调整

当p是g的左孩子时

当p为g的右孩子时

插入完整代码

红黑树的检测

红黑树完整代码（包括测试数据）

 

概念

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

性质

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

结点的定义 

//给出枚举变量，以便于方便区分红黑结点
enum Colour
{
	RED,
	BLACK,
};

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

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

注意：这里待插入结点的默认颜色给的也有说法，如果你插入的是一个黑色结点，百分之百会违反性质4，但是如果我们插入的是红结点则可能违反性质3。

所以我们把结点的默认颜色给为红色，以便于我们做更少的调整。 

插入

其实插入跟我们前面学习的二叉搜索树的插入方法是一样的，这里我就不多做阐述。而我们主要关注的是红黑树的调整。这里的调整不同于AVL树，而是根据红黑树特殊的性质进行调整的。

调整

我们根据叔叔是否存在和颜色来分情况考虑。

结点说明：

p--parent

g--grandfater

u--uncle

当p是g的左孩子时

情况一：如果u存在且为红

 

 1、如果g为根节点，则进行第一步颜色调整之后还需要把g的颜色调整为红色，以保证根节点是黑色的。

2、如果g不为根节点，则颜色调整之后还需要向上继续进行调整。

注意：这种情况无论cur在p的左还是右调整步骤是一样的，因为不涉及到旋转。

情况二：如果u不存在/存在且为黑（直线）

 1、这里的关键就是u存在且为黑，我们可以发现g的右子树上多了一个黑结点，那么就不能很好的满足g的左右子树黑结点的数量是一致的这个性质，那么我们推算出该cur结点一定是从情况1转化过来的，也就是这颗树的cur子树是先经过了情况一，才到这一步的。

2、u不存在时直接进行一个形如我们AVL树学习的右单旋，然后进行颜色调整就可以解决。

情况三：如果u不存在/存在且为黑（折线）

 

1、u存在且为黑（折线）与直线的u存在且为黑一样，由于插入前左右黑结点数量就不平衡，所以肯定是首先经过了情况一。具体步骤就是进行两次旋转+调整颜色。

2、u不存在（折线）由于折线的情况，因此也是经过两次旋转+调整颜色。

当p为g的右孩子时

情况一：如果u存在且为红 

由于这一步并没有经过旋转，因此整个调整过程与p为g的左孩子时完全一样。

情况二：如果u不存在/存在且为黑（直线）

由于p相对于g的位置发生了改变此时的直线就是一个左边高。仿照p为g的左孩子。

情况三：如果u不存在/存在且为黑（折线）

只是折线的方向与p为g的左孩子相反罢了，其余一样，仿照p为g的左孩子。

插入完整代码

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

		while (parent && parent->_col == RED)
		{
			Node* grandfater = parent->_parent;
			if (grandfater->_left == parent)
			{
				Node* uncle = grandfater->_right;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfater->_col = RED;
					cur = grandfater;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)//无论是否有uncle 都这样旋转     //直线
					{
						RotateR(grandfater);
						parent->_col = BLACK;
						grandfater->_col = RED;
					}
					else
					{
						RotateL(parent);
						RotateR(grandfater);
						cur->_col = BLACK;
						grandfater->_col = RED;
					}
					break;
				}
			}
			else
			{
				Node* uncle = grandfater->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfater->_col = RED;

					cur = grandfater;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)//无论是否有uncle 都这样旋转     //直线
					{
						RotateL(grandfater);
						parent->_col = BLACK;
						grandfater->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandfater);
						cur->_col = BLACK;
						grandfater->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return true;
	}

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

			subL->_parent = ppNode;
		}
	}

红黑树的检测

1、检测每条路径的黑色结点数量是否相同。

2、是否存在连续的两个红结点。

bool Check(Node* root, int blackNum, const int ref)
	{
		if (root == nullptr)
		{
			//cout << blackNum << endl;
			if (blackNum != ref)
			{
				cout << "违反规则：本条路径的黑色节点的数量跟最左路径不相等" << endl;
				return false;
			}

			return true;
		}

		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "违反规则：出现连续红色节点" << endl;
			return false;
		}

		if (root->_col == BLACK)
		{
			++blackNum;
		}

		return Check(root->_left, blackNum, ref)
			&& Check(root->_right, blackNum, ref);
	}

	bool IsBalance()
	{
		if (_root == nullptr)
		{
			return true;
		}

		if (_root->_col != BLACK)
		{
			return false;
		}

		int ref = 0;
		Node* left = _root;
		while (left)
		{
			if (left->_col == BLACK)
			{
				++ref;
			}

			left = left->_left;
		}

		return Check(_root, 0, ref);
	}

红黑树完整代码（包括测试数据）

//给出枚举变量，以便于方便区分红黑结点
enum Colour
{
	RED,
	BLACK,
};

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

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

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->_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);
		cur->_col = RED;
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		while (parent && parent->_col == RED)
		{
			Node* grandfater = parent->_parent;
			if (grandfater->_left == parent)
			{
				Node* uncle = grandfater->_right;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfater->_col = RED;
					cur = grandfater;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)//无论是否有uncle 都这样旋转     //直线
					{
						RotateR(grandfater);
						parent->_col = BLACK;
						grandfater->_col = RED;
					}
					else
					{
						RotateL(parent);
						RotateR(grandfater);
						cur->_col = BLACK;
						grandfater->_col = RED;
					}
					break;
				}
			}
			else
			{
				Node* uncle = grandfater->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfater->_col = RED;

					cur = grandfater;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)//无论是否有uncle 都这样旋转     //直线
					{
						RotateL(grandfater);
						parent->_col = BLACK;
						grandfater->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandfater);
						cur->_col = BLACK;
						grandfater->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return true;
	}

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

			subL->_parent = ppNode;
		}
	}

	void Inorder()
	{
		_Inorder(_root);
	}

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

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

	bool Check(Node* root, int blackNum, const int ref)
	{
		if (root == nullptr)
		{
			//cout << blackNum << endl;
			if (blackNum != ref)
			{
				cout << "违反规则：本条路径的黑色节点的数量跟最左路径不相等" << endl;
				return false;
			}

			return true;
		}

		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "违反规则：出现连续红色节点" << endl;
			return false;
		}

		if (root->_col == BLACK)
		{
			++blackNum;
		}

		return Check(root->_left, blackNum, ref)
			&& Check(root->_right, blackNum, ref);
	}

	bool IsBalance()
	{
		if (_root == nullptr)
		{
			return true;
		}

		if (_root->_col != BLACK)
		{
			return false;
		}

		int ref = 0;
		Node* left = _root;
		while (left)
		{
			if (left->_col == BLACK)
			{
				++ref;
			}

			left = left->_left;
		}

		return Check(_root, 0, ref);
	}

private:
	Node* _root = nullptr;
};

void test_RBTree1()
{
	//写入几个树进行验证
	//int a[] = { 8, 3, 1,10,6,4,7,14,13 };
	int a[] = { 8, 3, 1,10,6,4 };
	//int a[] = { 16, 3, 7, 11};
	//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	RBTree<int, int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
		if (e == 4)
		{
			int i = 0;
		}
	}
	t.Inorder();
	cout << t.IsBalance();

}
void test_RBTree2()
{
	srand(time(0));
	const size_t N = 100000;
	RBTree<int, int> t;
	for (size_t i = 0; i < N; i++)
	{
		size_t x = rand();
		t.Insert(make_pair(x, x));
	}
	t.Inorder();
	cout << t.IsBalance() << endl;
}

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

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

相关文章

如何有效备考PMP？

如何有效备考PMP？

随着PMP证书含金量直线上升&#xff01;现在PMP证书就跟黄金一样&#xff0c;即保值又升值。 今天小编应势出一篇关于如何高效备考PMP的方法&#xff0c;在备考生快过来看看吧&#xff01; 1、准备好所需要的教材&#xff0c;视频&#xff0c;试题内容 备考备考&#xff0c;你…
阅读更多...
蓝桥杯刷题冲刺 | 倒计时5天

蓝桥杯刷题冲刺 | 倒计时5天

作者&#xff1a;指针不指南吗 专栏&#xff1a;蓝桥杯倒计时冲刺 &#x1f43e;马上就要蓝桥杯了&#xff0c;最后的这几天尤为重要&#xff0c;不可懈怠哦&#x1f43e; 文章目录1.方格迷宫2.字符串删减1.方格迷宫 题目 链接&#xff1a; 4943. 方格迷宫 - AcWing题库 给定一…
阅读更多...
Sam Altman专访：GPT-4没太让我惊讶，ChatGPT则让我喜出望外

Sam Altman专访：GPT-4没太让我惊讶，ChatGPT则让我喜出望外

导读ChatGPT、GPT-4 无疑是 2023 年年初人工智能界最大的「爆款」。3 月 26 日&#xff0c;OpenAI CEO、ChatGPT 之父 Sam Altman 接受了著名学者与科技播客、麻省理工大学研究员 Lex Fridman 的专访&#xff0c;Sam 分享了从OpenAI内部视角如何看待ChatGPT和GPT-4的里程碑式意…
阅读更多...
分享：数据库存储与索引技术（三）LSM树实现案例

分享：数据库存储与索引技术（三）LSM树实现案例

欢迎访问 OceanBase 官网获取更多信息&#xff1a;https://www.oceanbase.com/ 本文来自OceanBase社区分享&#xff0c;仅限交流探讨。原作者马伟&#xff0c;长期从事互联网广告检索系统的研发&#xff0c;对数据库&#xff0c;编译器等领域也有浓厚兴趣。 文章目录1. MemTab…
阅读更多...
2.2.2 第2遍：程序细节

2.2.2 第2遍：程序细节

这段话主要解释了C程序中#include指令和头文件的作用。头文件包含了编译器所需的信息&#xff0c;例如函数名、常量、以及如何使用它们等。在C程序中&#xff0c;头文件通常用于包含库函数&#xff0c;例如stdio.h文件中包含了输入和输出函数&#xff08;如printf()&#xff09…
阅读更多...
LCHub：ChatGPT4和低代码来临，程序员面临下岗?

LCHub：ChatGPT4和低代码来临，程序员面临下岗?

一个网友吐槽道： “ 建站出来了，你们说程序员会失业。 低代码出来了，你们说程序员会失业。 Copilot出来了，你们说程序员会失业。 Chatgpt出来了，你们说程序员会失业 虽然这只是网友的吐槽，但却引起了小编的好奇。为何程序员那么容易被新技术取代？今天小编打算跟大家…
阅读更多...
Waline在Butterfly主题中的应用

Waline在Butterfly主题中的应用

LeanCloud 设置 (数据库) 国内版的LeanCloud需要绑定域名&#xff0c;所以我们直接选择国外版的LeanCloud 登陆注册 注册&#xff1a;点击这里进行跳转注册成功后进入控制台&#xff0c;选择 创建应用 。 创建完成后进入应用&#xff0c;下拉找到 设置 , 会有 AppID 、AppK…
阅读更多...
ASO优化之应用商店关键词的实现

ASO优化之应用商店关键词的实现

投放正确的合适的关键词&#xff0c;能够确保我们的应用获得更高的相关性和知名度。如果我们已经完成研究并想要竞争目标关键词&#xff0c;就需要在商品详情中去实施投放它们。 要在 Google Play Store 中投放——我们要打开 Google Play 控制台并点击“主要应用详情”选项卡…
阅读更多...
基于模型预测控制(MPC)的微电网调度优化的研究（Matlab代码实现）

基于模型预测控制(MPC)的微电网调度优化的研究（Matlab代码实现）

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…
阅读更多...
VMware创建和使用虚拟网络

VMware创建和使用虚拟网络

文章目录如何打开虚拟网络编辑器让虚拟机使用有线、无线网卡1. 点击“添加网络”2. 虚拟机使用电脑自带无线网卡3. 虚拟机使用电脑自带有线网卡重置虚拟网络在使用虚拟机的过程中&#xff0c;有时会需要让虚拟机使用物理机的网络设备直接与外部连接&#xff0c;例如让虚拟机通过…
阅读更多...
Win11启用IE方法

Win11启用IE方法

呉師傅 Win11是微软目前的最新系统&#xff0c;尽管该系统非常不错&#xff0c;但是还是有很多不一样的地方&#xff0c;有的用户发现Win11没有了IE浏览器&#xff0c;那么Win11没有IE浏览器怎么办呢&#xff0c;有的旧网页需要IE浏览器才能进入&#xff0c;下面就给大家提供一…
阅读更多...
怎么把两个音频合成一个

怎么把两个音频合成一个

在创作音乐、制作视频等领域&#xff0c;经常需要将音频文件进行合并处理&#xff0c;但对于没有专业工具和知识的朋友来说&#xff0c;音频合并可能是一项复杂的任务。本篇文章就要为大家介绍合并音频的方法&#xff0c;让大家能够快速地将音频文件合并成需要的部分&#xff0…
阅读更多...
leaflet: 地图上叠加日夜区域（126）

leaflet: 地图上叠加日夜区域（126）

第126个 点击查看专栏目录 本示例的目的是介绍如何在vue+leaflet中显示日夜交替叠加区域。 直接复制下面的 vue+openlayers源代码，操作2分钟即可运行实现效果. 文章目录 示例效果配置方式示例源代码（共68行）安装插件相关API参考：专栏目标示例效果 配置方式 1）查看基础设…
阅读更多...
ChatGPT能胜任高级程序员吗？

ChatGPT能胜任高级程序员吗？

与开发人员信任的其他软件开发工具不同&#xff0c;AI工具在训练、构建、托管和使用方式等方面都存在一些独特的风险。 自2022年底ChatGPT发布以来&#xff0c;互联网上便充斥着对其几乎相同比例的支持和怀疑的论调。不管你是否喜欢它&#xff0c;AI正在逐步进入你的开发组织。…
阅读更多...
【设计模式】Bridge Design pattern 桥接模式

【设计模式】Bridge Design pattern 桥接模式

1.桥接模式要解决的问题 多个维度的变化引起的继承组合指数级增长 例子 一个物体有不同形状和不同颜色&#xff0c;如何用类来表示它们&#xff0c;这里包含了两个变化维度&#xff0c;一个是物体的形状&#xff0c;一个是颜色 继承的方式 如果使用继承的方式&#xff0c;此…
阅读更多...
抖音seo优化系统常见的交付形式|技术开发

抖音seo优化系统常见的交付形式|技术开发

1. 一次性交付&#xff1a;将整个SEO优化系统一次性交付给客户&#xff0c;包括相关的文档、工具和数据分析报告&#xff0c;由客户自行操作和维护。 2. 阶段性交付&#xff1a;将SEO优化系统分为不同的阶段进行交付&#xff0c;每个阶段完成后进行检查和评估&#xff0c;根据…
阅读更多...
2. [手把手教你搭建] 之 在linux上搭建mysql

2. [手把手教你搭建] 之 在linux上搭建mysql

1. 首先下载mysql安装包&#xff0c;这里一般有如下2种下载方式 wgt方式下载&#xff1a;进入服务器中的package目录&#xff08;注&#xff1a;该目录是我自己创建的&#xff0c;用于存放所有应用的安装包&#xff0c;您也可以随便创建其他名称的目录来存放安装包&#xff09…
阅读更多...
k8s部署

k8s部署

kubernetes简要 Kubernetes 是用于自动部署, 扩展和管理容器化应用程序的开源系统. 它将组成应用程序的容器组合成逻辑单元, 以便于管理和服务发现 kubernetes功能简介 服务发现和负载均衡 存储编排 自动部署和回滚 自动完成装箱计算 自我修复 密钥与配置管理 Kuberne…
阅读更多...
算法题记录

算法题记录

力扣的算法题&#xff1a;1154 给你一个字符串 date &#xff0c;按 YYYY-MM-DD 格式表示一个 现行公元纪年法 日期。返回该日期是当年的第几天。 示例 1&#xff1a; 输入&#xff1a;date “2019-01-09” 输出&#xff1a;9 解释&#xff1a;给定日期是2019年的第九天。 示例…
阅读更多...
【数据结构与算法】查找(Search)【详解】

【数据结构与算法】查找(Search)【详解】

文章目录查找查找概论一、查找的基本概念顺序表查找一、定义二、算法有序表查找一、折半查找二、插值查找三、斐波那契查找线性索引查找一、稠密索引二、分块索引三、倒排索引二叉树排序与平衡二叉树一、二叉排序树1、定义2、二叉排序树的常见操作3、性能分析二、平衡二叉树1、…
阅读更多...
最新文章

Copyright @ 2022~2023