C++的红黑树

目录

基本概念

插入结点的颜色

判断性质是否破坏

调整方式

 u为g的右孩子

u存在且为红

u存在且为黑

u不存在

结论 

红黑树结点定义

代码实现


基本概念

1、红黑树是一种特殊的二叉搜索树,每个结点会增加一个存储位表示结点的颜色(红或黑)

2、红黑树通过对所有从根到叶子的路径上的各个结点的着色方式的限制,确保红黑树中没有一条路径会比其它路径长出两倍,从而使二叉搜索树接近平衡

3、AVL树是一个严格平衡(平衡因子,二叉树能做到的最好的平衡),而红黑树是一个近似平衡插入100万个数据,AVL树会进行大量的旋转,形成的树可能是30层,但是红黑树的旋转会少一些,形成的树可能是60层,但是对于CPU而言其实二者差别也不大

4、红黑树有五个性质(紫色是重点)

  1. 每个结点不是红色就是黑色
  2. 根结点是黑色的
  3. 如果一个结点是红色,则它的两个孩子结点都是黑色(一个黑结点的孩子可以是红也可以是黑的,不可以不存在连续的红红、可以存在连续黑红、红黑和黑黑的结点)
  4. 对于每个结点,该结点到其所有后代叶子结点的简单路径上,均包含相同数目的黑色结点(一个结点向下的每条路径中的黑色结点相同,空结点也是黑色结点)(最难维护的规则)
  5. 每个叶子结点都是黑色的(红黑树中所指的叶子结点是空结点)

5、满足以上五条性质就能保证红黑树的最长路径 <= 最短路径 * 2

  • 最短路径(极端情况):全黑(由性质4可得:其它路径中也有相同数目的黑色结点以及红色结点,但是全黑的路径中没有红色结点)
  • 最长路径(极端情况):一黑一红(不算空结点)
  • 一个红黑树肯定有最长或最短路径,只不过不一定有以上的理想情况下的最短和最长路径,正常情况下最长路径小于最短路径的2倍,极端情况下最长路径可能还会等于最短路径的2倍(没有极端情况就矮子里挑将军了)

插入结点的颜色

问题:插入结点时还可以依据二叉搜索树的插入规则吗?插入结点应该都是什么颜色?

解释:可以且新插入的结点应该都是红色,因为插入结点的颜色是红色那么你只是可能违反性质3如果一个结点是红色,则它的两个孩子结点都是黑色):

        但是如果插入结点的颜色是黑色则一定违法性质4对于每个结点,该结点到其所有后代叶子结点的简单路径上,均包含相同数目的黑色结点):

判断性质是否破坏

        规定cur表示新插入结点,p表示父结点(parent)、g表示爷爷结点(grandfather)、u表示叔叔结点(uncle)

问题:如何确认在插入新结点后,红黑树的性质是否被破坏?

解释:新结点的颜色为红色,如果新结点的父结点颜色为红色,则违法性质3,需要进行调整

补充:p一定为红,g一定为黑,因为新插入结点的颜色是红色,插入该结点导致需要调整只可能是因为该结点的插入导致性质3遭到了破坏,那么p结点一定为红,而g也肯定为黑,因为在新插入结点前整颗红黑树应该是没有错误的(跟AVL树旋转是一个道理)

调整方式

问题:发现红黑树性质被破坏后,如何进行调整?(后面还有更准确的划分)

由上述内容可知,在性质被破坏时cur一定为红、p一定为红、g一定为黑,那么关键点就在于p的兄弟结点u,对u的关注点应该在于它的“位置 + 存在情况”

②u的位置:p为g的左孩子,u就是g的右孩子,p为g的右孩子,u就是g的左孩子

③u的存在情况:u存在且为黑色,u存在且为红色、u不存在

 u为g的右孩子

u存在且为红

解决办法:将p和u变为黑,g变为红(p和u替代了g保证路径上黑色结点数量不变)

遗留问题:

  • 如果g是根结点,那么在g变红后为了满足性质2,仅需要将g重新变为黑色即可
  • 如果g不是根结点,那么在g变红且g的父结点的颜色是黑色时,不需要继续向上调整
  • 如果g不是根结点,那么在g变红且g的父结点的颜色是红色时,就需要继续向上调整

注意事项:

1、不能在发现新插入结点导致违法性质3后将cur再变为黑,因为那样还不如规定插入结点的颜色为黑色但是那样又一定会违法性质4

2、p和u改变后不能让g仍然为黑,因为如果g不是根结点,那么也会违法性质4

关于cur:无论cur是p的左孩子还是右孩子,当u存在且为红时,调整时只需要调色即可

u存在且为黑

补充:下图演示的是u存在且为红在调整后,向上调节时遇到的u存在且为黑的情况,用一个例子将u存在且为红 + 向上调整 + u存在且为黑的情况都总结了

解决办法:先旋转(以g为旋转点进行LL右单旋),后变色(p变为黑,g变为红)

关于cur:

①上面的cur是p左孩子则以g为旋转点进行LL右单旋,p变黑g变红

②若cur是p的右孩子先以p为旋转点进行左单旋,后以g为旋转点进行右单旋,cur变黑g变红

(颜色改变没有先后顺序,只要发生改变即可,先旋转后变色只是为了理解变色原因)

u不存在

解决办法:先变色(p变为黑,g变为红),后旋转(以g为旋转点进行LL右单旋)

关于cur:

①上面的cur是p左孩子则以g为旋转点进行LL右单旋,p变黑g变红

②若cur是p的右孩子先以p为旋转点进行左单旋,后以g为旋转点进行右单旋,cur变黑g变红

(颜色改变没有先后顺序,只要发生改变即可,先旋转后变色只是为了理解变色原因)

u为g的右孩子的情况不再分析,通过最终代码自己画图感受,主要区别在于旋转方式的不同

结论 

  1. 每一次的调整都可能导致另一次红黑树性质的被破坏
  2. cur和parent均为红色是由“新增”或“向上调整”两种原因导致的,因此无论是这两种的哪一种,只有当cur和parent均不为红时才不需要继续调整(循环)
  3. 红黑树是否调整取决于cur和parent是否均为红,怎么调整取决于叔叔u的情况 + cur是p的哪个孩子

红黑树结点定义

// 结点颜色
enum Color 
{ 
	RED, 
	BLACK
};

// 红黑树节点的定义
template<class ValueType>
struct RBTreeNode
{
	RBTreeNode(const ValueType & data = ValueType(),Color color = RED)
		: _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
		, _data(data), _color(color)
	{}

	RBTreeNode<ValueType>* _pLeft;		// 节点的左孩子
	RBTreeNode<ValueType>* _pRight;		// 节点的右孩子
	RBTreeNode<ValueType>* _pParent;	// 节点的双亲
	ValueType _data;				    // 节点的值域       
	Color _color;						// 节点的颜色        
};
  • 演示的内容与最终代码中变量的名字存在区别

代码实现

#pragma once

#include <iostream>
#include<vector>

using namespace std;

enum Colour
{
	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;
	Colour _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:
	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;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		// 当parent指向的结点不为空,且parent指向的结点的颜色不为黑色就继续向上调整(因为cur和parent均为红可能是由新增和向上调整导致的,因此无论是这两种情况的哪一种,
		// 只有当cur和parent均不为红时才结束循环)
		while (parent && parent->_col == RED)
		{
			
			Node* grandfather = parent->_parent;//通过父亲找到爷爷,父亲的父亲信息是爷爷

			//红黑树的关键点在于判断叔叔的情况
			if (parent == grandfather->_left)//如果父亲是爷爷的左孩子,那么叔叔就只能是爷爷的右孩子
			//这里if中的叔叔一直都是爷爷的右孩子,不过还会存在为红、为黑、不存在的三种情况
			{
				Node* uncle = grandfather->_right;

				
				// 如果叔叔存在且叔叔的颜色是红色,则直接将叔叔和父亲的颜色都变为黑色,将爷爷的颜色变为红色
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 防止修改颜色导致上方出现新的两个连续的红色结点,需要移动指针继续向上处理
					cur = grandfather;//cur指向爷爷结点
					parent = cur->_parent;//parent指向的是cur的父结点(cur向上走,parent也要向上走)
				}
				else // 叔叔不存在,或者存在且为黑
				{
					if (cur == parent->_left)//如果cur是父亲的左孩子,进行LL右单,旋转后将父亲的颜色变为黑,将爷爷的颜色变为红
					{
						//     g  
						//   p   u
						// c 
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//      g  
						//   p     u
						//      c 
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}



			else//如果父亲结点是爷爷结点的右孩子,那么叔叔结点就是爷爷结点的左孩子
			{
				Node* uncle = grandfather->_left;
				// 叔叔存在且为红,-》变色即可
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else // 叔叔不存在,或者存在且为黑
				{
					// 情况二:叔叔不存在或者存在且为黑
					// 旋转+变色
					//      g
					//   u     p
					//            c
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//		g
						//   u     p
						//      c
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
		}

		_root->_col = BLACK;//不管最后整棵红黑树的根结点是什么颜色(因为向上调整可能会导致根结点颜色变为红色,也有可能根结点也颜色不变)
		//我们这里都直接重新将根结点的颜色设置为黑色,这样就不需要再在循环中去判断是否到达根结点
		return true;
	}

	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;
			_root->_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;

		subR->_left = parent;
		Node* ppNode = parent->_parent;

		parent->_parent = subR;

		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_right == parent)
			{
				ppNode->_right = subR;
			}
			else
			{
				ppNode->_left = subR;
			}
			subR->_parent = ppNode;
		}
	}

	//对用户暴露的中序遍历红黑树接口
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	//判断红黑树是否平衡
	bool IsBalance()
	{
		//首先根结点颜色得为黑
		if (_root->_col == RED)
		{
			return false;
		}

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

			cur = cur->_left;
		}

		return Check(_root, 0, refNum);
	}

private:
	bool Check(Node* root, int blackNum, const int refNum)
	{
		if (root == nullptr)
		{
			//cout << blackNum << endl;
			if (refNum != blackNum)
			{
				cout << "存在黑色节点的数量不相等的路径" << endl;
				return false;
			}

			return true;
		}

		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << root->_kv.first << "存在连续的红色节点" << endl;
			return false;
		}

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

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

	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;
};


//测试红黑树能否正常使用
void TestRBTree1()
{
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14,8, 3, 1, 10, 6, 4, 7, 14, 13 };
	RBTree<int, int> t1;
	for (auto e : a)
	{
		if (e == 10)
		{
			int i = 0;
		}

		// 1、先看是插入谁导致出现的问题
		// 2、打条件断点,画出插入前的树
		// 3、单步跟踪,对比图一一分析细节原因
		t1.Insert({e,e});

		std::cout << "Insert:" << e << "->" << t1.IsBalance() << std::endl;
	}

	t1.InOrder();

	std::cout << t1.IsBalance() << std::endl;
}

//测试红黑树对百万数据处理所需时间
void TestRBTree2()
{
	const int N = 1000000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
		//cout << v.back() << endl;
	}

	size_t begin2 = clock();
	RBTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
		//cout << "Insert:" << e << "->" << t.IsBalance() << endl;
	}
	size_t end2 = clock();

	std::cout << t.IsBalance() << std::endl;
}

~over~

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

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

相关文章

超前预热|博睿数据将应邀出席双态IT用户大会,分享《构建云原生时代的一体化智能可观测性》

5月31日&#xff0c;第十二届双态IT用户大会将于成都盛大开幕&#xff0c;此次大会由DCMG和双态IT论坛联合主办&#xff0c;聚焦“信创时代的组织级云原生能力建设”和“组织级云原生运维能力建设”两大会议主题&#xff0c;旨在推动双态IT落地与创新&#xff0c;为企业数字化转…

syncthing文件夹同步与版本管理

1 前言 syncthing可以用来同步文件夹里的所有文件&#xff0c;并且有不错的版本管理&#xff0c;基本每次更改文件&#xff0c;20-40秒就被扫描到了&#xff0c;非常丝滑&#xff1b;这次以此来同步obsidian的插件和文件&#xff0c;达到多端同步&#xff1b; 我家里有一台台…

【C语言回顾】联合和枚举

前言1. 联合体1.1 联合体的声明1.2 联合体的特点1.3 联合体的使用 2. 枚举2.1 枚举的声明2.2 枚举的特点2.3 枚举的使用 结语 #include<GUIQU.h> int main { 上期回顾: 【C语言回顾】结构体 个人主页&#xff1a;C_GUIQU 专栏&#xff1a;【C语言学习】 return 一键三连;…

x264 码率控制 MBtree 原理:mbtree_propagate_list 函数分析

mbtree_propagate_list 函数功能 是视频编码中宏块树传播算法的一部分,用于在编码决策过程中更新参考帧的传播成本。这个过程特别关注于如何处理运动向量(Motion Vectors, MVs)以及如何根据这些MVs对参考帧的成本进行加权,从而影响最终的编码选择。 该函数作为x264编码器…

【Android】联系人列表补充

真布局--叠起来垂直管 效果展示 部分代码&#xff08;在activity_main&#xff09;里面 <FrameLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"…

二十五、openlayers官网示例CustomOverviewMap解析——实现鹰眼地图、预览窗口、小窗窗口地图、旋转控件

官网demo地址&#xff1a; Custom Overview Map 这个示例展示了如何在地图上增加一个小窗窗口的地图并跟随着地图的旋转而旋转视角。 首先加载了一个地图。其中 DragRotateAndZoom是一个交互事件&#xff0c;它可以实现按住shift键鼠标拖拽旋转地图。 const map new Map({int…

Java分支结构详解

Java分支结构详解 前言一、if 语句基本语法表示一表示二表示三 代码示例判定一个数字是奇数还是偶数判定一个数字是正数还是负数判定某一年份是否是闰年 注意要点悬垂 else 问题代码风格问题分号问题 二、switch 语句基本语法代码示例根据 day 的值输出星期 注意事项break 不要…

QtCreator,动态曲线实例

样式图&#xff1a; .ui 在sloem1.ui文件中&#xff0c;拖入一个label控件&#xff0c; 头文件.h #include "QtGui/QPainter.h" #include "QtCore/QTimer.h"protected:bool eventFilter(QObject *obj,QEvent *event);void labelPaint();public slots: /…

Element Plus/vue3 无限级导航实现

在使用element plus 时&#xff0c;最初要使用的就是导航组件了&#xff0c;官网上看到的也就是写死的一级/二级导航&#xff0c;那么如何设计一个无限级且动态的导航呢&#xff1f;毋庸置疑&#xff0c;递归。废话不多说&#xff0c;直接看代码和效果&#xff1a; 代码&#x…

我在去哪儿薅到了5块钱火车票代金券,速薅

哈哈&#xff0c;亲爱的薅羊毛小伙伴们&#xff01; 刚刚在去哪儿大佬那儿发现了一个超级薅羊毛福利&#xff01;我只花了短短两分钟&#xff0c;就搞到了一张5块钱火车票代金券&#xff0c;简直是天上掉馅饼的节奏啊&#xff01; 话不多说&#xff0c;薅羊毛的姿势给你们摆好…

树的非递归遍历(层序)

层序是采用队列的方式来遍历的 就比如说上面这颗树 他层序的就是&#xff1a;1 24 356 void LevelOrder(BTNode* root) {Que q;QueueInit(&q);if (root){QueuePush(&q, root);}while (!QueueEmpty(&q)){BTNode* front QueueFront(&q);QueuePop(&q);print…

Docker Compose使用

Docker-Compose是什么 docker建议我们每一个容器中只运行一个服务,因为doker容器本身占用资源极少&#xff0c;所以最好是将每个服务单独分割开来&#xff0c;但是这样我们又面临了一个问题&#xff1a; 如果我需要同时部署好多个服务&#xff0c;难道要每个服务单独写Docker…

202473读书笔记|《但愿呼我的名为旅人:松尾芭蕉俳句300》——围炉夜话,身顿心安,愿每个人都能在爱里自由驰骋

202473读书笔记|《但愿呼我的名为旅人&#xff1a;松尾芭蕉俳句300》——围炉夜话&#xff0c;身顿心安&#xff0c;愿每个人都能在爱里自由驰骋 &#x1f60d;&#x1f60d;&#x1f929;&#x1f929; 译者序正文二正文三正文四正文五正文六正文七 《但愿呼我的名为旅人&…

网站笔记:huggingface——can you run it?

Can You Run It? LLM version - a Hugging Face Space by Vokturz 1 配置设置部分 Model Name就是需要测量的模型名称 GPU Vendor ——GPU供应商 Filter by RAM (按RAM过滤) 筛选出所有内存容量在选择范围之间的GPU GPU 下拉菜单选择具体的GPU型号 LoRa % trainable param…

MT3608B是一个恒定频率,6引脚SOT23电流模式升压转换器用于小型,低功耗应用的目的芯片IC

一般说明 该MT3608B是一个恒定频率&#xff0c;6引脚SOT23电流模式升压转换器用于小型&#xff0c;低功耗应用的目的。该MT3608B开关在1.2MHz&#xff0c;并允许使用微小&#xff0c;低成本的电容器和电感2毫米或更少的高度。内部软启动的结果在小浪涌电流和延长电池寿…

Linux网络——端口号理解与UDP协议

前言 在之前&#xff0c;我们学习了UDP通信与套接字编程&#xff0c;了解到需要使用端口号来表示网络中的数据需要传输到哪个进程&#xff0c;同时使用套接字的进行了UDP的通信。但当时在应用层&#xff0c;我们仅仅是浮于表面进行了初步的使用&#xff0c;今天我们来深入的理…

面试八股之MySQL篇1——慢查询定位篇

&#x1f308;hello&#xff0c;你好鸭&#xff0c;我是Ethan&#xff0c;一名不断学习的码农&#xff0c;很高兴你能来阅读。 ✔️目前博客主要更新Java系列、项目案例、计算机必学四件套等。 &#x1f3c3;人生之义&#xff0c;在于追求&#xff0c;不在成败&#xff0c;勤通…

卷积神经网络(CNN)详细介绍及其原理详解

卷积神经网络&#xff08;Convolutional Neural Networks&#xff0c;简称CNN&#xff09;是深度学习中非常重要的一类神经网络&#xff0c;主要用于图像识别、图像分类、物体检测等计算机视觉任务。本文将详细介绍卷积神经网络的基本概念、结构组成及其工作原理&#xff0c;并…

IIS网站搭建

1、添加网站 2、命名加上端口方便查看端口占用情况&#xff08;可有可无&#xff09; 3、导入sql文件&#xff0c;数据库打开——新建数据库——建好的数据库右键运行sql文件——打开路径网站下面的install文件下的sql——选中之后点开始——左侧页面的右键刷新就会显示。

2024最新 Jenkins + Docker 实战教程(四) - 编写自己的Springboot项目实现自动化部署

&#x1f604; 19年之后由于某些原因断更了三年&#xff0c;23年重新扬帆起航&#xff0c;推出更多优质博文&#xff0c;希望大家多多支持&#xff5e; &#x1f337; 古之立大事者&#xff0c;不惟有超世之才&#xff0c;亦必有坚忍不拔之志 &#x1f390; 个人CSND主页——Mi…