手撕红黑树（map和set底层结构）（2）

@[TOC]红黑树

一 红黑树概念

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

简单来说红黑树通过了对颜色的控制进而对树的长度做出了限制，不再需要平衡因子。
红黑树性质

  1. 每个节点不是红色就是黑色
  2. 根节点为黑色
  3. 如果一个节点是红色，那么他的孩子节点就是黑色。没有连续的红色节点
  4. 对于每个节点，他的所以路径上的黑色节点的数量是相同的。
  5. 每个叶子节点都是黑色的（注意：这里的叶子节点指的是空节点）

红黑树通过这些性质保证了他的高度是合法的。
在这里插入图片描述
红黑树保证的是：最长路径不超过最短路径的两倍

二 红黑树的实现

2.1 红黑树的结构

enum Color
{
	Red,
	Black,
};


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

	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _color(Red)
		, _kv(kv)
	{}
};
template<class K,class V>
class RBtree
{
	typedef RBTreeNode<K, V> Node;
	private:
	Node* _node=nullptr;
}

2.2 红黑树的插入

在这里插入图片描述
我们要注意：我们在插入新节点的时候，默认插入元素的颜色为红色，（黑色节点不好控制，因为要保证全部的路径的黑色节点数量是相同的，插入了一个黑色节点，就不能保证这一原则了）
然后插入元素对整棵树的影响我们就要从局部开始看，

  1. 如果插入元素的父亲为黑色那就不用在变化了；
  2. 插入元素的父亲为红色，此时就出翔了连续的红色节点，我们就要对这颗树进行处理；

我们对第二种情况分类讨论（用上述的图片为例）

第一种：cur为红，p为红，g为黑，u存在且为红

把p和u变为黑色，再把g变成红色；
到这里就要继续分类讨论：

  1. g为根节点，那就把g再变成黑色。
  2. 如果不是根节点，就把g=c，向上继续处理
    注意（p/u是g的左还是右都不影响，同样cur是p的左还是右也不影响）

第二种: cur为红，p为红，g为黑，u不存在/u存在且为黑
（i）u不存在在这里插入图片描述
这里cur一定是新插入的节点，如果cur不是新插入的节点，cur和p一定有一个是黑色的。
（ii）u存在且为黑色在这里插入图片描述
这里的cur就不是新插入的节点，u是黑色那么，每个路径下黑色节点数量一定相同，所以cur原本一定是黑色的，是因为新插入的原因被变成了红色。
以上这两个情况本质上是一种。
这里就要用到旋转，旋转和前面AVL树的旋转一模一样

p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，
p为g的右孩子，cur为p的右孩子，则进行左单旋转
旋转完：p、g变色–p变黑，g变红。

参考下面的图，进一步理解
在这里插入图片描述
在这里插入图片描述
第三种 cur为红，p为红，g为黑，u不存在/u存在且为黑，但这里的左右位置不同

(i) p为g的左，cur为p的右
在这里插入图片描述
在这里插入图片描述
可以看到这里就变回了情况二，根据上面的我们再进行右单旋即可。
在这里插入图片描述
(i) p为g的右，cur为p的左

这个就是先右旋+左旋即可。这个图留个大家去完成。

2.3代码

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

		while (parent && parent->_color == Red)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				//情况一：存在且为红
				if (uncle && uncle->_color == Red)
				{
					//变色
					parent->_color = Black;
					uncle->_color = Black;
					grandfather->_color = Red;
					//向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				//情况二：不存在or存在且为黑
				else
				{
					//旋转+变色
					//    g
					//  p    u
					//c
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_color = Black;
						grandfather->_color = Red;
					}
					else
					{
						//情况三
						//    g
						//  p    u
						//     c  
						RotateL(parent);
						RotateR(grandfather);
						cur->_color = Black;
						grandfather->_color = Red;
					}
					break;
				}
			}
			else//p是g的右孩子
			{
				Node* uncle = grandfather->_left;
				//情况一：存在且为红
				if (uncle && uncle->_color == Red)
				{
					//变色
					parent->_color = Black;
					uncle->_color = Black;
					grandfather->_color = Red;
					//向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				//情况二：不存在or存在且为黑
				else
				{
					//旋转+变色
					//    g
					//  u   p
 					//        c
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_color = Black;
						grandfather->_color = Red;
					}
					else
					{
						//情况三
						//    g
						//  u   p
						//     c
						RotateR(parent);
						RotateL(grandfather);
						cur->_color = Black;
						grandfather->_color = Red;
					}
					break;
				}
			}
		}
		_root->_color = Black;

		return true;
	}

三 检查函数

	bool Check(Node* cur, int BlackNum, int refBlackNum)
	{
		if (cur == nullptr)
		{
			if (BlackNum != refBlackNum)
			{
				cout << "黑色节点的数量不匹配" << endl;
				return false;
			}
			else
				return true;
		}
		if (cur->_color == Red && cur->_parent->_color == Red)
		{
			cout << "出现了连续的红色节点" << endl;
			return false;
		}
		if (cur->_color == Black)
			++BlackNum;
		return Check(cur->_left, BlackNum, refBlackNum) &&
			Check(cur->_right, BlackNum, refBlackNum);

	}
	bool IsBalance()
	{
		if (_root == nullptr || _root->_color == Red)
			return false;
		//给一个基准值，和其他的黑色节点去比较
		int refBlackNum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_color == Black)
				++refBlackNum;
			cur = cur->_left;
		}
		return Check(_root, 0, refBlackNum);
	}

四 总结

总的来说红黑树的实现和AVL树非常像，他们就是兄弟，红黑树就是把考虑的因素从平衡因子转变成了颜色。

五 完整代码

#pragma once
#include<assert.h>
#include<vector>
enum Color
{
	Red,
	Black,
};


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

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

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

		while (parent && parent->_color == Red)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				//情况一：存在且为红
				if (uncle && uncle->_color == Red)
				{
					//变色
					parent->_color = Black;
					uncle->_color = Black;
					grandfather->_color = Red;
					//向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				//情况二：不存在or存在且为黑
				else
				{
					//旋转+变色
					//    g
					//  p    u
					//c
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_color = Black;
						grandfather->_color = Red;
					}
					else
					{
						//情况三
						//    g
						//  p    u
						//     c  
						RotateL(parent);
						RotateR(grandfather);
						cur->_color = Black;
						grandfather->_color = Red;
					}
					break;
				}
			}
			else//p是g的右孩子
			{
				Node* uncle = grandfather->_left;
				//情况一：存在且为红
				if (uncle && uncle->_color == Red)
				{
					//变色
					parent->_color = Black;
					uncle->_color = Black;
					grandfather->_color = Red;
					//向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				//情况二：不存在or存在且为黑
				else
				{
					//旋转+变色
					//    g
					//  u   p
 					//        c
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_color = Black;
						grandfather->_color = Red;
					}
					else
					{
						//情况三
						//    g
						//  u   p
						//     c
						RotateR(parent);
						RotateL(grandfather);
						cur->_color = Black;
						grandfather->_color = Red;
					}
					break;
				}
			}
		}
		_root->_color = Black;

		return true;
	}

	void RotateL(Node* parent)
	{
		//++rotateSize;

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

	void RotateR(Node* parent)
	{
		//++rotateSize;

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

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

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

	void InOrder()
	{
		_InOrder(_root);
	}

	///
	//检查函数
	bool Check(Node* cur, int BlackNum, int refBlackNum)
	{
		if (cur == nullptr)
		{
			if (BlackNum != refBlackNum)
			{
				cout << "黑色节点的数量不匹配" << endl;
				return false;
			}
			else
				return true;
		}
		if (cur->_color == Red && cur->_parent->_color == Red)
		{
			cout << "出现了连续的红色节点" << endl;
			return false;
		}
		if (cur->_color == Black)
			++BlackNum;
		return Check(cur->_left, BlackNum, refBlackNum) &&
			Check(cur->_right, BlackNum, refBlackNum);

	}
	bool IsBalance()
	{
		if (_root == nullptr || _root->_color == Red)
			return false;
		//给一个基准值，和其他的黑色节点去比较
		int refBlackNum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_color == Black)
				++refBlackNum;
			cur = cur->_left;
		}
		return Check(_root, 0, refBlackNum);
	}
private:
	Node* _root = nullptr;
};


void TestRBTree1()
{
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	int a[] = { 4, 2, 6, 1, 14,16};
	RBTree<int, int> t;
	for (auto e : a)
	{
		if (e == 16)
		{
			int x = 0;
		}
		t.Insert(make_pair(e, e));

		// 1、先看是插入谁导致出现的问题
		// 2、打条件断点，画出插入前的树
		// 3、单步跟踪，对比图一一分析细节原因
		cout << e << "->" << t.IsBalance() << endl;
	}

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

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

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

相关文章

54-摄像头DVP接口电路设计

54-摄像头DVP接口电路设计

视频链接 摄像头电路设计-DVP接口01_哔哩哔哩_bilibili 摄像头DVP接口电路设计 1、摄像头简介 1.1、Camera介绍 在各类信息中&#xff0c;图像含有最丰富的信息&#xff0c;作为机器视觉领域的核心部件&#xff0c;摄像头被广泛应用。 目前市面上最常用的摄像头为OV5640。…
阅读更多...
【面试必备】Python 快问快答

【面试必备】Python 快问快答

什么是 Python&#xff0c;它有哪些主要特点 答&#xff1a;Python 是一种高级解释型编程语言&#xff0c;以简单易读著称。其主要特点包括动态类型、自动内存管理&#xff08;垃圾回收&#xff09;、丰富的标准库以及对多种编程范式&#xff08;过程式、面向对象、函数式&…
阅读更多...
内容营销ROI提升秘籍：Kompas.ai的高效内容分析

内容营销ROI提升秘籍：Kompas.ai的高效内容分析

在内容营销的领域中&#xff0c;投资回报率&#xff08;ROI&#xff09;是衡量营销活动成效的关键指标。一个高ROI的内容营销策略不仅能够为企业带来直接的经济收益&#xff0c;还能够提升品牌价值和市场影响力。本文将深入探讨内容营销中ROI的重要性&#xff0c;介绍Kompas.ai…
阅读更多...
【嵌入式】Arduino IDE + ESP32开发环境配置

【嵌入式】Arduino IDE + ESP32开发环境配置

一 背景说明 最近想捣鼓一下ESP32的集成芯片&#xff0c;比较了一下&#xff0c;选择Arduino IDE并添加ESP32支持库的方式来开发&#xff0c;下面记录一下安装过程以及安装过程中遇到的坑。 二 下载准备 【1】Arduino IDE ESP32支持一键安装包&#xff08;非常推荐&#xff0…
阅读更多...
canvas 学习

canvas 学习

最近的项目涉及到 canvas 相关的知识&#xff0c;就在网站上找资源先大概了解一下&#xff0c;然后再细细研究。 看到了一篇 “canvas详细教程” 的资源&#xff0c;感觉十分不错&#xff0c;就分享给大家&#xff1a; canvas详细教程! ( 近1万字吐血总结)这期是潘潘整理的万…
阅读更多...
C++入门（3）

C++入门（3）

文章目录 C入门auto同一行中定义多个变量auto不能推到的场景基于范围的for循环(C11)10. 指针空值nullptr(C11) C入门 auto auto&#xff1a;C11中&#xff0c;标准委员会赋予了auto全新的含义即&#xff1a;auto不再是一个存储类型指示符&#xff0c;而是作为一个新的类型指示…
阅读更多...
基于ontape的备份与恢复实验

基于ontape的备份与恢复实验

通过本文的备份恢复实验&#xff0c;我们可以深入了解ontape的使用方法和原理&#xff0c;包括如何进行完整备份、增量备份以及如何利用备份文件进行数据恢复。 1. 配置onconfig参数 通过修改onconfig参数文件&#xff0c;或使用onmode -wf命令&#xff0c;设置备份默认使用的…
阅读更多...
pmp好考么？知道这些PMP一个多月拿下~

pmp好考么？知道这些PMP一个多月拿下~

过来人想说的是PMP考试没那么难&#xff0c;学习也没那么复杂的&#xff0c;只要能好好学基础知识&#xff0c;积累实践案例&#xff0c;接着多做做题摸清题意套路&#xff0c;考试的时候就跟考科一似的。 尽管听上去描述的可能过于简单&#xff0c;但事实便是如是&#xff0c…
阅读更多...
容器云平台运维的范围与架构设计新思潮

容器云平台运维的范围与架构设计新思潮

容器云平台运维的范围与架构设计 【导读】容器云平台有其独特的特点&#xff0c;不同于传统系统的运维。本文分享了作者对容器云平台运维范围和运维架构设计的思考与实践。 一、容器云平台运维范围 &#xff08;一&#xff09; 梳理要运维哪些内容 作为运维专家&#xff0c;…
阅读更多...
被删除的照片和视频能找回吗？如何恢复手机删除的照片和视频？

被删除的照片和视频能找回吗？如何恢复手机删除的照片和视频？

手机里的照片和视频是我们记录生活的每一个瞬间&#xff0c;也是工作学习等场合经常用到的东西&#xff0c;一旦不慎丢失&#xff0c;将对我们造成很大损失。那么我们该如何恢复手机删除的照片和视频呢&#xff1f;通过掌握正确的恢复方法&#xff0c;能够最大程度地保护手机中…
阅读更多...
【Leetcode笔记】501.二叉搜索树中的众数

【Leetcode笔记】501.二叉搜索树中的众数

文章目录 题目要求ACM 模式代码知识点 题目要求 给你一个含重复值的二叉搜索树&#xff08;BST&#xff09;的根节点 root &#xff0c;找出并返回 BST 中的所有 众数&#xff08;即&#xff0c;出现频率最高的元素&#xff09;。 如果树中有不止一个众数&#xff0c;可以按 …
阅读更多...
PDF文件去除文字水印

PDF文件去除文字水印

文章目录 0、背景1、准备工作2、查看是否是文字水印3、批量去除水印 0、背景 本文主题为去除PDF文件中的水印。源文件来自这里。防止丢失&#xff0c;我在这里做个记录&#xff0c;感谢原作者的付出&#xff0c;也欢迎大家关注原作者。 1、准备工作 下载Adobe Acrobat DC软件…
阅读更多...
GUI测试首推！TestComplete 帮助有效缩短 40-50% 测试时长！

GUI测试首推！TestComplete 帮助有效缩短 40-50% 测试时长！

TestComplete 是一款自动化UI测试工具&#xff0c;这款工具目前在全球范围内被广泛应用于进行桌面、移动和Web应用的自动化测试。 TestComplete 集成了一种精心设计的自动化引擎&#xff0c;可以自动记录和回放用户的操作&#xff0c;方便用户进行UI&#xff08;用户界面&…
阅读更多...
C++ 面向对象-封装

C++ 面向对象-封装

C 是一种多范式编程语言&#xff0c;它支持面向对象编程&#xff08;OOP&#xff09;范式。面向对象编程是一种程序设计思想&#xff0c;其中程序由对象组成&#xff0c;每个对象都是一个实例&#xff0c;具有数据和相关操作。在C中&#xff0c;实现面向对象编程主要通过类和对…
阅读更多...
Vue3、 Vue2 Diff算法比较

Vue3、 Vue2 Diff算法比较

Vue2 Diff算法 源码位置：src/core/vdom/patch.ts 源码所在函数：updateChildren() 源码讲解： 有新旧两个节点数组：oldCh和newCh； 有下面几个变量： oldStartIdx 初始值=0 oldStartVnode 初始值=oldCh[0] oldEndIdx 初始值=oldCh.length - 1 oldEndVnode 初始值=oldCh[ol…
阅读更多...
如何在PostgreSQL中设置定期任务（如定时备份、数据分析等），并使用pgAgent或其他方式实现

如何在PostgreSQL中设置定期任务（如定时备份、数据分析等），并使用pgAgent或其他方式实现

文章目录 使用pgAgent实现定期任务步骤一&#xff1a;安装pgAgent步骤二&#xff1a;配置pgAgent步骤三&#xff1a;创建和调度任务示例代码&#xff1a; 使用操作系统的任务调度功能实现定期任务步骤一&#xff1a;编写脚本步骤二&#xff1a;设置cron任务示例代码&#xff1a…
阅读更多...
ssh日志的独立与ssh远程日志

ssh日志的独立与ssh远程日志

日志相关介绍&#xff1a; 1.系统日志&#xff1a;是记录了历史事件&#xff1a;包括时间地点人物事件等。日志级别&#xff1a;事件的关键性程度&#xff0c;Loglevel。 级号消息级别说明0EMERG紧急会导致主机系统不可用的的情况1ALERT警告必须马上采取措施解决的问题2CRIT严…
阅读更多...
vue3实现全局事件总线

vue3实现全局事件总线

1、vue3中使用全局事件总线是变化最大的。在vue2中&#xff0c;我们在new Vue中在beforeCreate钩子函数中使用vue.prototype.$busthis来创建全局事件总线。vue3中我需要借助第三方库来完成创建全局事件总线。 2、安装依赖 npm i mitt -s3、封装event-bus.js文件 import mitt …
阅读更多...
【白菜学习问问问系列】if __name__ == ‘__main__‘:怎么理解

【白菜学习问问问系列】if __name__ == ‘__main__‘:怎么理解

可以让.py文件既可以当成一个模块调用&#xff0c;也可以单独的作为一个函数执行
阅读更多...
【基础算法】双指针

【基础算法】双指针

1.移动零 移动零 思路&#xff1a; 利用双指针算法 cur&#xff1a;从左往右扫描数组&#xff0c;遍历数组 dest&#xff1a;处理好的区间包括dest dest初始化为-1&#xff0c;因为刚开始dest前应该没有非零元素。 即将非零元素移到dest之前即可 class Solution { public…
阅读更多...
最新文章

Copyright @ 2022~2023