【C++高阶(四)】红黑树深度剖析--手撕红黑树!

💓博主CSDN主页:杭电码农-NEO💓
 
⏩专栏分类:C++从入门到精通⏪
 
🚚代码仓库:NEO的学习日记🚚
 
🌹关注我🫵带你学习C++
  🔝🔝

在这里插入图片描述

红黑树

  • 1. 前言
  • 2. 红黑树的概念以及性质
  • 3. 红黑树为什么更实用?
  • 4. 红黑树模拟实现代码框架
  • 5. 红黑树的插入操作初步分析
  • 6. 红黑树的插入操作详解(一)
  • 7. 红黑树的插入操作详解(二)
  • 8. 红黑树的插入代码实现
  • 9. 总结以及拓展

1. 前言

如果说发明AVL树的人是天才,那么
发明红黑树的人可以称为天才中的
精英!为什么AVL树这么强大但是没啥
人用呢?就是因为红黑树比你还好!

本章重点:

本篇文章着重讲解红黑树的概念以及
性质,以及为了维护红黑树这种性质而
做的限制条件.最后模拟实现红黑树的
插入,带大家熟悉变色和旋转规则!

2. 红黑树的概念以及性质

红黑树的概念:

  • 首先红黑树是一颗二叉搜索树
  • 每个节点都有颜色,红色或黑色
  • 最长路径最多是最短路径的二倍

在这里插入图片描述

红黑树的性质:

  1. 每个结点不是红色就是黑色
  2. 根节点是黑色的
  3. 如果一个节点是红色的
    则它的两个孩子结点是黑色的
  4. 每条路径上的黑色节点数相同
  5. 每个叶子结点都是黑色的
    (此处的叶子结点指的是空结点)
为啥满足了以上性质的红黑树就一定
能做到最长路径最多是最短路径的二倍?
下面我画一个极限情况来分析一下!

在这里插入图片描述

3. 红黑树为什么更实用?

现在将AVL数和红黑树做一个对比:

  • AVL树阐析:

AVL树是一颗高度平衡二叉树,
它的高度差不能大于1,所以AVL
树的查找是妥妥的O(logn),但是
由于AVL树严格的标准,使得在使用
AVL树时会经常旋转,反而增加了时间!

  • 红黑树阐析:

红黑树是一颗接近平衡的二叉树
它最长路径最多是最短路径的二倍
所以查找的效率是:logn~2logn,
然而2logn和logn是一个量级的,
并且红黑树的规则没有这么严格,
不会涉及到更多旋转和变色!

综上所述,红黑树的效率虽然比
AVL树差一点,但是总体来说红黑树胜!

4. 红黑树模拟实现代码框架

首先,每个节点都要存一个颜色,
这里我们使用枚举enum来实现
并且和AVL一样也是三叉链!
请看代码:

enum Colour
{
	RED,
    BLACK
};
template<class K,class V>
struct RBTreeNode
{
	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		,_col(RED)
	{}
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	pair<K, V> _kv; 
	Colour _col;
};

template<class K, class V>
struct RBTree
{
typedef RBTreeNode<K, V> Node;
private:
	Node* _root = nullptr;
};

有了代码框架后,现在来看看插入

5. 红黑树的插入操作初步分析

和AVL树很相似,红黑树的插入
也是分为两步走:

  1. 按照二叉搜索树的规则插入值
  2. 插入后根据颜色或高度做旋转或变色

众所周知啊,第一步很简单
甚至可以将之前的代码抄过来:

bool insert(const pair<K, V>& kv)//第一步:按照二叉搜索树的方式插入值
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_col = BLACK;
		return true;
	}
	Node* cur = _root;
	Node* parent = nullptr;
	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;
	//此时new出来的节点的parent还指向空
	cur->_parent = parent;
	///前面的过程和AVL树一致
}

走到这步后,有个问题,新插入的节点
是选择插入红色还是黑色?

对于这个问题,我们要思考两个点,
一是如果插入的是黑色节点,我们
可能会打破哪个规则?如果是插入
红色节点又可能会打破哪个规则?

  • 插入黑色节点,打破规则四,很难办
    因为每个路径检查起来很难!

  • 插入红色节点,打破规则三,比打破
    四要好一些,因为只用看父亲是否为红

综上所述,插入红色更优!
换句话说,你犯错肯定宁愿犯轻一点
的错误被妈妈打一顿,也不愿意犯很重
的错直接被家族除名了对吧[doge]

6. 红黑树的插入操作详解(一)

如果插入的节点的父亲是黑色节点,
那么正是我们想看见的,不用管它了!

那么如果插入的节点的父亲是红色呢?
很明显,这违反了规则三,有连续的红色
节点,所以此时需要做处理了!

先来看一个最简单的情况:

在这里插入图片描述

其实红黑树插入节点后的变色和
旋转规则主要是看叔叔,叔叔的情况
不同,那么对应的处理手段就不同,这里
只通过简单变色手段就可以满足规则了!
并且在上图中,将爷爷变成红色后可能会
出现问题,因为爷爷的父亲不知道是红色
还是黑色,所以要不断向上做判断

若不向上更新,可能会有这种情况:

在这里插入图片描述

7. 红黑树的插入操作详解(二)

当讲解完最简单的情况后,还剩下两种
情况,这两种情况内部又可细分出几种
情况,请同学们耐心学习!

情况二:cur为红.p为红.g为黑.u不存在/为黑
(并且cur和p都是左或右)

在这里插入图片描述
在这里插入图片描述

p为g的左孩子,cur为p的左孩子,则右单旋
p为g的右孩子,cur为p的右孩子,则左单旋
p,g变色—p变黑，g变红

情况三:cur为红.p为红.g为黑.u不存在/为黑
(并且若p是g的左,cur就是p的右)

在这里插入图片描述

p为g的左孩子,cur为p的右孩子,则做左单旋
p为g的右孩子,cur为p的左孩子,则做右单旋
则转换成了情况二

至此,红黑树的插入的所有情况都
讲解完毕,接下来就是代码实现了!

8. 红黑树的插入代码实现

在整个大情况分类中,可以归为两类
一是叔叔为红色,二是叔叔为黑色或者
叔叔不存在,我们围绕着这两个大方向写!

//走到这一步后,就已经找到cur和parent了!
while (parent && parent->_col == RED)//当parent为黑就不用往上更新了
{
	if (parent == _root)
	{
		_root->_col = BLACK;
		break;
	}
	Node* grandf = parent->_parent;
	assert(grandf);
	assert(grandf->_col == BLACK);
	Node* uncle = nullptr;
	if (parent == grandf->_left)//判断叔叔在par的左还是右
		uncle = grandf->_right;
	else uncle = grandf->_left;
	if (uncle == nullptr || uncle->_col == BLACK)//uncle为空或为黑有四种情况来变色＋旋转
	{
		if (parent == grandf->_left && cur == parent->_left)//左左->右旋＋变色
		{
			RotateR(grandf);
			parent->_col = BLACK;
			grandf->_col = RED;
			break;
		}
		else if (parent == grandf->_right && cur == parent->_right)//右右->左旋+变色
		{
			RotateL(grandf);
			parent->_col = BLACK;
			grandf->_col = RED;
			break;
		}
		else if (parent == grandf->_left && cur == parent->_right)//左右->先左旋再右旋再变色
		{
			RotateL(parent);
			RotateR(grandf);
			cur->_col = BLACK;
			grandf->_col = RED;
			break;
		}
		else if (parent == grandf->_right && cur == parent->_left)//右左->先右旋再左旋再变色
		{
			RotateR(parent);
			RotateL(grandf);
			cur->_col = BLACK;
			grandf->_col = RED;
			break;
		}
	}
	else if (uncle && uncle->_col == RED)//叔叔为红,直接变色,不旋转
	{
		parent->_col = BLACK;
		uncle->_col = BLACK;
		grandf->_col = RED;
		cur = grandf;
		parent = cur->_parent;//将parent更新后往上传!
	}
	_root->_col = BLACK;
}

可以发现一个问题,只要是叔叔的颜色
是黑色或叔叔不存在的情况下,执行完
旋转＋变色后都直接break了,这是因为
在这种情况下,父亲节点都被变成了黑色,
也就没必要继续往上了!并且在红黑树的
左旋和右旋中,代码其实和AVL树的旋转是
一模一样的,所以直接copy一份就行了!

若你不清楚旋转的代码,请看这篇文章:

AVL树模拟实现!

9. 总结以及拓展

AVL树和红黑树的代码实现都只讲解
了插入操作,因为删除操作太复杂了,
并且就算实现了删除操作也没有太大
的实际意义,所以只需要了解插入即可!

并不是需要你真正的会手撕!

拓展阅读:

红黑树的删除图解

🔎 下期预告:哈希表,哈希桶 🔍

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

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

相关文章

第95步 深度学习图像目标检测：Faster R-CNN建模

第95步 深度学习图像目标检测：Faster R-CNN建模

基于WIN10的64位系统演示 一、写在前面 本期开始&#xff0c;我们学习深度学习图像目标检测系列。 深度学习图像目标检测是计算机视觉领域的一个重要子领域&#xff0c;它的核心目标是利用深度学习模型来识别并定位图像中的特定目标。这些目标可以是物体、人、动物或其他可识…
阅读更多...
【追求卓越12】算法--堆排序

【追求卓越12】算法--堆排序

引导 前面几节&#xff0c;我们介绍了有关树的数据结构&#xff0c;我们继续来介绍一种树结构——堆。堆的应用场景有很多&#xff0c;比如从大量数据中找出top n的数据&#xff1b;根据优先级处理网络请求&#xff1b;这些情景都可以使用堆数据结构来实现。 什么是堆&#xf…
阅读更多...
3.11-容器的资源限制

3.11-容器的资源限制

这一小节我们来看一下如何限制容器的资源&#xff0c;比如CPU和内存。 我们先来看一下对内存的限制。 --memory和--memory-swap这两个参数&#xff0c;如果我们只限定了--memory&#xff0c;没有限定--memory-swap&#xff0c;那么--memory-swap的大小就会和--memory大小一样。…
阅读更多...
Cesium实现热力图功能

Cesium实现热力图功能

效果图如下&#xff1a; <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"widthdev…
阅读更多...
数字化时代的政务服务：构建便捷高效的线上政务大厅

数字化时代的政务服务：构建便捷高效的线上政务大厅

引言&#xff1a; 随着数字化时代的来临&#xff0c;如何通过线上政务大厅搭建一个便捷高效的服务平台&#xff0c;以更好地满足公众需求值得探究。线上政务大厅是政务服务的新方式&#xff0c;但搭建线上政务大厅并不是一件容易的事情&#xff0c;需要精心的规划和设计。 一…
阅读更多...
常量字符串（const）

常量字符串（const）

数组名就是地址&#xff0c;str1与str2是两个不同的数组&#xff0c;虽然内容相同&#xff0c;但是地址不同&#xff0c;故为no const char * str是常量字符串&#xff0c;如果已有相同内容str3&#xff0c;则写入相同内容的str4是不会再开辟新的空间了&#xff0c;因为常量已…
阅读更多...
react中模块化样式中:global的作用

react中模块化样式中:global的作用

在react中如果是通过import styles from ./index.less这种方式模块化引入样式的话&#xff0c;那么编译后的less文件里的样式名都会自动添加后缀。而:global的作用就是不让类名添加后缀
阅读更多...
故障识别：CNN-BiLSTM-SelfAttention时空特征融合多头自注意力机制的故障识别程序，数据由Excel导入，直接运行！

故障识别：CNN-BiLSTM-SelfAttention时空特征融合多头自注意力机制的故障识别程序，数据由Excel导入，直接运行！

适用平台&#xff1a;Matlab2023版及以上 本程序参考中文EI期刊《基于CNN-BiLSTM 的滚动轴承变工况故障诊断方法法》&#xff0c;程序注释清晰&#xff0c;干货满满&#xff0c;下面对文章和程序做简要介绍。 在CNN-BiLSTM-SelfAttention故障识别模型中&#xff0c;结合了卷积…
阅读更多...
指标管理系统

指标管理系统

参考 指标系统业务操作流程 阿里大数据开发治理平台
阅读更多...
开源一个局域网文件共享工具

开源一个局域网文件共享工具

shigen日更文章的博客写手&#xff0c;擅长Java、python、vue、shell等编程语言和各种应用程序、脚本的开发。记录成长&#xff0c;分享认知&#xff0c;留住感动。 hello&#xff0c;夜深了&#xff0c;又是shigen深夜写博客的时间啦&#xff0c;今天分享的内容是《开源一个局…
阅读更多...
OpenGeometry 开源社区特聘子虔科技云CAD专家 共建云几何内核

OpenGeometry 开源社区特聘子虔科技云CAD专家 共建云几何内核

11月5日&#xff0c;由广东省工业和信息化厅、广东省科学技术厅、广东省教育厅、深圳市人民政府主办的2023工业软件生态大会在广东省深圳市召开。 开幕式上&#xff0c;备受关注的云几何内核开源平台——OpenGeometry开源社区正式发布。这意味着在几何引擎领域将通过开源这个模…
阅读更多...
2023年亚太地区数学建模大赛 C 题

2023年亚太地区数学建模大赛 C 题

我国新能源电动汽车的发展趋势 新能源汽车是指以先进技术原理、新技术、新结构的非常规汽车燃料为动力来源&#xff08;非常规汽车燃料指汽油、柴油以外的燃料&#xff09;&#xff0c;将先进技术进行汽车动力控制和驱动相结合的汽车。新能源汽车主要包括四种类型&#xff1a;…
阅读更多...
【追求卓越01】数据结构--数组

【追求卓越01】数据结构--数组

引导 这一章节开始&#xff0c;正式进入数据结构与算法的学习过程中。由简到难&#xff0c;先开始学习最基础的数据结构--数组。 我相信对于数组&#xff0c;大家肯定是不陌生&#xff0c;因为数组在大多数的语言中都有&#xff0c;也是大家在编程中常常会接触到的。我不会说数…
阅读更多...
免费分享自建GPT网站，畅享无限创意！

免费分享自建GPT网站，畅享无限创意！

PS&#xff1a;该文章基本为GPT3.5 撰写 这里与大家分享一个令人兴奋的消息&#xff1a;我建立了一个全新的GPT网站&#xff0c;并且我将免费提供给大家使用&#xff01;这个网站基于最新的GPT-3.5 Turbo模型&#xff0c;能够为您带来无限的创意和惊喜。 在这个免费的GPT网站…
阅读更多...
一条命令彻底卸载Linux自带多个版本jdk

一条命令彻底卸载Linux自带多个版本jdk

一条命令彻底卸载Linux自带多个版本jdk 检查系统已经安装的jdk rpm -qa | grep java卸载所有已经安装的 jdk xargs 将参数逐个传递 将已安装的 java 程序逐个当做参数传递给 rpm -e --nodeps rpm -qa | grep java | xargs rpm -e --nodeps再次检查系统已经安装的jdk rpm -qa | …
阅读更多...
python-opencv划痕检测

python-opencv划痕检测

python-opencv划痕检测 这次实验&#xff0c;我们将对如下图片进行划痕检测&#xff0c;其实这个比较有难度&#xff0c;因为清晰度太差了。 我们做法如下&#xff1a; &#xff08;1&#xff09;读取图像为灰度图像&#xff0c;进行自适应直方图均衡化处理&#xff0c;增强图…
阅读更多...
基于爬行动物算法优化概率神经网络PNN的分类预测 - 附代码

基于爬行动物算法优化概率神经网络PNN的分类预测 - 附代码

基于爬行动物算法优化概率神经网络PNN的分类预测 - 附代码 文章目录 基于爬行动物算法优化概率神经网络PNN的分类预测 - 附代码1.PNN网络概述2.变压器故障诊街系统相关背景2.1 模型建立 3.基于爬行动物优化的PNN网络5.测试结果6.参考文献7.Matlab代码 摘要&#xff1a;针对PNN神…
阅读更多...
梦开始的地方——Adobe Premiere Pro

梦开始的地方——Adobe Premiere Pro

今天&#xff0c;我们来说说一款老生常谈的相信也是很多人都经常迫切需要的软件。Adobe Premiere Pro&#xff0c;简称Pr&#xff0c;是由Adobe公司开发的一款视频编辑软件。 Premiere Pro是视频编辑爱好者和专业人士必不可少的视频编辑工具。它可以提升您的创作能力和创作自由…
阅读更多...
Leetcode—6.N字形变换【中等】

Leetcode—6.N字形变换【中等】

2023每日刷题&#xff08;三十七&#xff09; Leetcode—6.N字形变换 算法思想 参考k神的题解 实现代码 class Solution { public:string convert(string s, int numRows) {if(numRows < 2) {return s;}vector<string> rows(numRows);int flag -1;int i 0;for(…
阅读更多...
使用docker命令_进入容器_登录mysql服务_并执行sql语句---Docker工作笔记005

使用docker命令_进入容器_登录mysql服务_并执行sql语句---Docker工作笔记005

今天就用到了,不得不说用docker用到的还是少,记录一下,常用的也就这些吧. 首先执行: docker ps [root@localhost dataease-1.18.9]# docker ps CONTAINER ID IMAGE COMMAND CREATED …
阅读更多...
最新文章

Copyright @ 2022~2023