C++AVL树拓展之红黑树原理及源码模拟

前言:我们之前已经从零开始掌握AVL树http://t.csdnimg.cn/LaVCCicon-default.png?t=N7T8http://t.csdnimg.cn/LaVCC

现在我们将继续学习红黑树的原理并且实现插入等功能,学习本章的前提要求是掌握排序二叉树和AVL树,本章不再提及一些基础知识,防止本文结构臃肿,对二叉排序树和AVL树有兴趣的可以阅读上面链接的文章,很多人可能说既生瑜何生亮,有了AVL树为什么还要红黑树,当然是因为红黑树的效率更高啦,AVL树的平黑太过于依赖平衡因子,稍微不平衡就会旋转,而大量的旋转自然降低了效率,红黑树相对AVL树没有那么平衡,旋转次数也少了,但是查询效率略微的降低就减少了不少的旋转,何乐而不为呢?更何况C++是一门以高效出名的语言。

目录

一,红黑树的基本准则

二,红黑树为什么是平衡的

三,代码实现

1)敲前准备

2)查找

3)插入

4)迭代器


一,红黑树的基本准则

希望大家先记住红黑树本质还是一颗二叉排序树。在二叉排序树的基础上,AVL树是加了平衡因子,来保持树的结构平衡,红黑树则是通过给每个结点标记颜色达到相对平衡。(为什么要平衡是为了提高查询效率,不懂看链接博客)

1)每个结点的颜色不是黑色就是红色

2)红黑树根节点的颜色是黑色的(这条规定会在后面平衡的调整那里给出原因,现在记住即可)

3)红黑树上不能出现两个相邻的红色结点(红黑树平衡的重要准则)

4)每个叶子结点都是黑色的。(注意这里的叶子结点指的是NULL结点)

5)每条路径上的黑色结点的数目都是一样多的

6)最短路径小于最长路径的两倍(这个其实不是原则,是一个推论,下面会讲解,不必纠结)

二,红黑树为什么是平衡的

接下来我们将讨论一下为什么红黑树是平衡的。

讨论这个性质我们要从上面说的红黑树的基本准则入手。红黑树不过三种情况我们分类讨论

1)结点的颜色全是黑色

如果红黑树的结点颜色全是黑色,那么这棵树必定是一个完全二叉树,因为如果不是完全二叉树,红黑树的结点有全是黑色,那就违背了上面的第五条原则(每条路径上的黑色结点的数目都是一样多的)。

得出来红黑树的结点全是黑色的则次数必定平衡。

2)除了根节点其他结点都是红色

这种情况只有四种情况,我直接给大家画出来,记住不能违背上面的第三个准则(红黑树上不能出现两个相邻的红色结点)。

     

如果再插入结点必然出现黑色结点,不满足我们这种情况了。

3)既有红色结点也有黑色结点

首先根据上面的准则,每条路径上的黑色结点数目一样,红色结点不能相邻出现,也就是两个红色结点之间必然有若干个黑色结点,然而每条路径上黑色结点的数目已经固定了,我们现在看极端情况,也就是最短的路径一个红色结点也没有,最长的路径上每个红色结点之间只有一个黑色结点。

从上面的图可以得到最长路径绝对不会超过最短路径的两倍,因为红色结点的数目不会超过黑色结点 ,当然上面是把路径单独列出来了来,实际上是树状结构。

综上所述红黑树的是一个相对平衡的二叉树。

三,代码实现

1)敲前准备

首先我们需要一个标记位来记录当前结点的颜色,我们采用枚举类型,可读性强

enum color {
	red,
	black
};

结点里面的内容应该包括什么呢?data存储数据,三个指针,一个parent指针,一个leftchild和rightchild指针,结构体里面应该包括我们刚刚的枚举。

template<class T>
struct RBTreeNode {
	RBTreeNode(T data) {
		_pParent = NULL;
		_pLeft = NULL;
		_pRight = NULL;
		_data = data;
		c = red;
	}
	RBTreeNode() {
		_pParent = NULL;
		_pLeft = NULL;
		_pRight = NULL;
		c = red;
	}
	color c;
	RBTreeNode* _pParent;
	RBTreeNode* _pLeft;
	RBTreeNode* _pRight;
	T _data;
};

那么大致框架就搭起来了

enum color {
	red,
	black
};
template<class T>
struct RBTreeNode {
	RBTreeNode(T data) {
		_pParent = NULL;
		_pLeft = NULL;
		_pRight = NULL;
		_data = data;
		c = red;
	}
	RBTreeNode() {
		_pParent = NULL;
		_pLeft = NULL;
		_pRight = NULL;
		c = red;
	}
	color c;
	RBTreeNode* _pParent;
	RBTreeNode* _pLeft;
	RBTreeNode* _pRight;
	T _data;
};
template<class T>
class RBTree
{
private:
	Node* _pHead; //哨兵位
	size_t _size;//结点个数
};
2)查找

查找还是一个老套路,大于当前结点找右边,小于当前结点找左边,直到找到或者为空,属实是老生常谈了,这里不过多介绍。

// 检测红黑树中是否存在值为data的节点,存在返回该节点的地址,否则返回nullptr
	Node* _Find(const T& data) {
		Node* cur = _pHead->_pParent;//从根节点开始
		while (cur&&cur!=_pHead) {
			if (data < cur->_data)  //小于找左边
				cur = cur->_pLeft;
			else if (data > cur->_data) {   //大于找右边
				cur = cur->_pRight;
			}
			else
				return cur;   //找到返回
		}
		return NULL;  //找不到
	}
3)插入

插入的第一件事就是找到应该插入的位置,这个简单,这个逻辑和查找一样。插入之后的颜色应该是红色还是黑色值得商榷,但仔细考虑,如果插入黑色的话就违背了每条路径上的黑色结点个数相等的原则,插入红色则可能碰到连续的红色结点,那到底是插入红色还是黑色呢?我们现在来讨论一下。

如果插入黑色结点的话,那么完全是牵一发而动全身,因为根据结点规则每条路径上的黑色结点的数目都是一样多的,我们需要把所有路径的黑色结点数目全部增加一个,这显然不是一个明智之举。那我们只剩下一个选择了,插入的新结点默认为红色结点,接下来我们需要分情况讨论。

1)插入结点的父亲结点是黑色,如果是黑色插入红色节点不需要改变任何结点,因为完全满足红黑树的规则,既没有连续的红色结点,每条路径的黑色结点数也都相同。

2)如果是父亲是红色的结点呢?

     注:圆形代表一个结点,长方形代表很多种可能

这种情况我们需要看parent的兄弟结点的颜色了,接下来又要分情况讨论

1)兄弟节点是红色,这种情况我们把两个兄弟节点全变成黑色,把爷爷结点变成红色,然后继续递归往上,往上有两种可能,一种是一直递归到根节点,然后根节点变成红色,最后我们强制把根节点变成黑色就行了,并不会违背任何原则。当然可能中途兄弟节点是黑色,这个时候我们需要使用下面情况2的旋转来弥补了。

2)兄弟节点是黑色的时候,证明单纯靠变色已经无法将这颗红黑树拉上正途了,我们不得已采取暴力手段旋转了,旋转结果仍然需要遵守红黑树原则。这里面又分为好几种情况

旋转具体详细过程,参考我的往期博客

http://t.csdnimg.cn/a13umicon-default.png?t=N7T8http://t.csdnimg.cn/a13um

1)左旋(之所以每个节点下面都可能有节点是因为,新插入的节点不可能碰到这种情况,只可能是情况1向上递归解决的时候出现的)

void RotateL(Node* pParent)
	{
		Node* pSubR = pParent->_pRight;
		Node* pSubRL = pSubR->_pLeft;

		pParent->_pRight = pSubRL; //防止访问空结点
		if (pSubRL)
			pSubRL->_pParent = pParent;

		pSubR->_pLeft = pParent;
		Node* pPParent = pParent->_pParent;
		pSubR->_pParent = pPParent;
		pParent->_pParent = pSubR;

		if (pPParent == _pHead)     //根节点单独处理
			_pHead->_pParent = pSubR;
		else
		{
			if (pParent == pPParent->_pLeft)
				pPParent->_pLeft = pSubR;
			else
				pPParent->_pRight = pSubR;
		}
	}

2)右旋

 

void RotateR(Node* pParent)
	{
		Node* pSubL = pParent->_pLeft;
		Node* pSubLR = pSubL->_pRight;

		pParent->_pLeft = pSubLR;
		if (pSubLR)       //防止访问空结点
			pSubLR->_pParent = pParent;

		pSubL->_pRight = pParent;

		Node* pPParent = pParent->_pParent;
		pParent->_pParent = pSubL;
		pSubL->_pParent = pPParent;

		if (pPParent == _pHead)      //根节点单独处理
			_pHead->_pParent = pSubL;
		else
		{
			if (pParent == pPParent->_pLeft)
				pPParent->_pLeft = pSubL;
			else
				pPParent->_pRight = pSubL;
		}
	}

3)右旋加左旋

4)左旋加右旋

 双旋代码复用单旋就行了

插入代码:

bool _Insert(const T& data) {
		if (_Find(data)) {
			cout << "元素已经存在" << endl;
			return false;
		}
		//插入第一个元素的时候
		if (_pHead->_pParent == _pHead) {
			Node* root = new Node(data);
			root->c = black;
			root->_pParent = _pHead;
			_pHead->_pParent = root;
			_pHead->_pLeft = root;
			_pHead->_pLeft = root;
			return 1;
		}
		Node* cur = _pHead->_pParent;
		Node* parent=cur;
		//找该插入的位置
		while (cur&&cur!=_pHead) {
			parent = cur;
			if (cur->_data > data) {
				cur = cur->_pLeft;
			}
			else if (cur->_data < data) {
				cur = cur->_pRight;
			}
			else {
				cout << "值:" << data << "已经存在" << endl;
				return 0;
			}
		}
		//插入
		cur = new Node(data);
		if (parent->_data > data) {
			parent->_pLeft = cur;
			cur->_pParent = parent;
		}
		else {
			parent->_pRight = cur;
			cur->_pParent = parent;
		}
		//调整
		Node* gparent = parent->_pParent;
		Node* uncle = _pHead;
		while (gparent&&parent->c != black) {
			if (gparent->_pLeft == parent) {
				uncle = gparent->_pRight;
			}
			else {
				uncle = gparent->_pLeft;
			}
			if (!uncle || uncle->c == black)
				break;
			else {
				uncle->c = black;
				gparent->c = red;
				parent->c = black;
			}
			cur = gparent;;
			parent = cur->_pParent;
			gparent = parent->_pParent;
		}
		if (cur == parent->_pLeft && parent == gparent->_pLeft && (uncle == NULL || uncle->c == black)) {
			RRotate(gparent); //左旋情况
			parent->c = black;
			gparent->c = red;
		}
		if (cur == parent->_pRight && parent == gparent->_pRight && (uncle == NULL || uncle->c == black)) {
			LRotate(gparent);  //右旋情况
			parent->c = black;
			gparent->c = red;
		}
		if (cur == parent->_pLeft && parent == gparent->_pRight && (uncle == NULL || uncle->c == black)) {
			RRotate(parent); //右左双旋
			LRotate(gparent);
			cur->c = black;
			gparent->c = red;
		}
		if (cur == parent->_pRight&& parent == gparent->_pLeft && (uncle == NULL || uncle->c == black)) {
			LRotate(parent);  //左右双旋
			RRotate(gparent);
			cur->c = black;
			gparent->c = red;
		}
		_pHead->_pLeft = LeftMost();
		_pHead->_pRight = RightMost();
		RightMost()->_pRight = _pHead;
		_pHead->_pParent->c = black;
		_size++;
		return 1;
	}
4)迭代器

迭代器属于老生常谈了,就是运算符重载,我们这里不做过多讲解,但是我们这里面有两个难点,就是++,--拿的是哪个结点?

首先看4的下一个下一个结点是什么(也就是++)?如果右子树不为空的话,下一个结点是右子树的最左结点。

那7的下一个结点是什么呢?当右子树为空时,一直递归向上直到这个这颗子树是某个结点的左孩子,这个结点就是下一个结点。

struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef typename RBTreeIterator<T> Self;
public:
Self& operator++() {
		if (_pNode->_pRight != NULL) //右子树不为空的情况下
		{
			_pNode = _pNode->_pRight;
			if (_pNode->_pParent->_pParent == _pNode) {
				RBTreeIterator<T> ret(_pNode);
				return ret;
			}
			while (_pNode->_pLeft != NULL)
				_pNode = _pNode->_pLeft;

			RBTreeIterator<T> ret(_pNode);
			return ret;
		}
		while (_pNode != _pNode->_pLeft) {       //一直递归向上直到这个这颗子树是某个结点的左孩子
			if (_pNode->_pParent->_pParent == _pNode) {
				RBTreeIterator<T> ret(NULL);
				return ret;
			}
			_pNode = _pNode->_pParent;
		}
		RBTreeIterator<T> ret(_pNode->_pParent);
		return ret;
	}
};

那--呢?也就是上一个结点。例如4,当左孩子不为空时,左子树的最右结点就是你的上一个结点。

如果最子树为空呢?例如5,那就一直向上递归,直到这颗子树是某个结点的右孩子,这个结点就是上一个结点。

struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef typename RBTreeIterator<T> Self;
public:	
Self& operator--() {
		if (_pNode->_pLeft != NULL) { //左子树为空的情况
			_pNode = _pNode->_pLeft;
			while (_pNode->_pRight) {
				_pNode = _pNode->_pRight;
			}
			Self a(_pNode);
			return a;
		}
		else {   //一直向上递归,直到这颗子树是某个结点的右孩子
			while (_pNode->_pParent->_pRight != _pNode) {
				if (_pNode->_pParent->_pParent == _pNode) {
					RBTreeIterator<T> ret(NULL);
					return ret;
				}
				_pNode = _pNode->_pParent;
			}
			Self a(_pNode->_pParent);
			return a;
		}
	}
};

其他的运算符重载没啥难度,大家完全可以靠自己敲出来。

这篇博客花了作者大量心思,希望大家你点赞+收藏+转发。如果博客有不对的地方,可以评论区讨论。

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

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

相关文章

LeetCode-560. 和为 K 的子数组【数组 哈希表 前缀和】

LeetCode-560. 和为 K 的子数组【数组 哈希表 前缀和】 题目描述&#xff1a;解题思路一&#xff1a;一边算前缀和一边统计。这里用哈希表统计前缀和出现的次数&#xff0c;那么和为k的子数组的个数就是当前前缀和-k的个数&#xff0c;即preSums[presum - k]。画个图表述就是&a…

sparksql执行流程

1. SparkSQL的自动优化 我们前面的文章已经说过spark RDD定义好后&#xff0c;执行经过DAG sechduler划分号内存管道、逻辑任务&#xff0c;然后经由task scheduler来分配到具体worker来管理运行&#xff0c;RDD的运行会完全按照开发者的代码执行 如果开发者水平有限&#xff…

一文了解JAVA的常用API

目录 常用kpimathSystemRuntimeObjectObjectsBigIntegerBigDecima正则表达式包装类 常用kpi 学习目的&#xff1a; 了解类名和类的作用养成查阅api文档的习惯 math 工具类。因为是工具类&#xff0c;因此直接通过类名.方法名(形参)即可直接调用 abs&#xff1a;获取参数绝对…

Spring如何进行事务管理?什么是面向切面编程?

喜欢就点击上方关注我们吧&#xff01; 本篇将带你快速了解Spring事务管理以及面向切面编程(AOP)相关知识。 一、事务 1、概述 1&#xff09;事务是一组操作的集合&#xff0c;是一个不可分割的工作单位&#xff0c;这些操作要么同时成功&#xff0c;要么同时失败。 2&#xff…

八股 -- C#

面向对象 &#xff08;三大特性&#xff09; 三大特性目的是为了提供更好的代码组织、可维护性、扩展性和重用性 C#基础——面向对象 - 知乎 (zhihu.com) 封装 理解&#xff1a; 你不需要了解这个方法里面写了什么代码&#xff0c;你只需要了解这个方法能够给你返回什么数据&…

矩阵乘法优化:GEMM中如何将大矩阵切割成小矩阵

论文自然还是 Anatomy of High-Performance Matrix Multiplication。 如何拆分 一个矩阵乘法有 6 种拆分方式&#xff0c;其中对 row-major 效率最高的是&#xff1a; 第一次拆分 先做第一次拆分&#xff0c;取 A 的 kc 列&#xff08;PanelA&#xff09;和 B 的 kc 行&…

基于 7 大城市实景数据,清华大学团队开源 GPD 模型

城市&#xff0c;是人们安居乐业的故土&#xff0c;是政府开展经济建设的基石&#xff0c;承载着细腻的人文情怀与宏伟的国家发展脉络。长期以来&#xff0c;管理者一直在探寻更加高效、科学的城市治理方法&#xff0c;解决不同地区资源供给不平衡、交通拥挤、人口流失等问题。…

Qt项目通过.pri文件将众多文件按功能模块分类显示,开发大型项目必备

Chapter1 Qt项目通过.pri文件将众多文件按功能模块分类显示&#xff0c;开发大型项目必备 Chapter2 在Qt项目中添加pri文件 原文链接&#xff1a;在Qt项目中添加pri文件_qtpri-CSDN博客 前言 一般我们创建Qt项目工程的时候&#xff0c;都是直接把所有的项目&#xff0c;头文…

Chatopera 云服务的智能问答引擎实现原理,如何融合 #聊天机器人 技术 #Chatbot #AI #NLP

观看视频 Bilibili: https://www.bilibili.com/video/BV1pZ421q7EH/YouTube: https://www.youtube.com/watch?vx0d1_0HQa8o 内容大纲 提前在浏览器打开网址&#xff1a; Chatopera 云服务&#xff1a;https://bot.chatopera.comChatopera 入门教程&#xff1a;https://dwz…

微机原理-基于8086电压报警器系统仿真设计

**单片机设计介绍&#xff0c;微机原理-基于8086电压报警器系统仿真设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于8086的电压报警器系统仿真设计概要主要涉及到系统的整体架构设计、硬件组成、软件逻辑设计以及仿真环境…

【智能算法】黄金正弦算法(GSA)原理及实现

目录 1.背景2.算法原理2.1算法思想2.2算法过程 3.结果展示4.参考文献 1.背景 2017年&#xff0c;Tanyildizi等人受到正弦函数单位圆内扫描启发&#xff0c;提出了黄金正弦算法&#xff08;Golden Sine Algorithm, GSA&#xff09;。 2.算法原理 2.1算法思想 GSA来源于正弦函…

前端学习<二>CSS基础——14-CSS3属性详解:Web字体

前言 开发人员可以为自已的网页指定特殊的字体&#xff08;将指定字体提前下载到站点中&#xff09;&#xff0c;无需考虑用户电脑上是否安装了此特殊字体。从此&#xff0c;把特殊字体处理成图片的方式便成为了过去。 支持程度比较好&#xff0c;甚至 IE 低版本的浏览器也能…

C语言内存函数(超详解)

乐观学习&#xff0c;乐观生活&#xff0c;才能不断前进啊&#xff01;&#xff01;&#xff01; 我的主页&#xff1a;optimistic_chen 我的专栏&#xff1a;c语言 点击主页&#xff1a;optimistic_chen和专栏&#xff1a;c语言&#xff0c; 创作不易&#xff0c;大佬们点赞鼓…

安全用电监控系统在工厂的研究与应用论述

摘 要&#xff1a;随着社会时代的发展&#xff0c;人们的安全意识越来越强烈&#xff0c;在人们生活和工作中离不开各种用电设备&#xff0c;用电设备的安全使用是保障人们生命安全的重要内容。工厂因自身厂内工作环境的特殊性&#xff0c;用电设备的种类多且复杂&#xff0c;如…

【数据结构与算法初阶(c语言)】插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序-全梳理(万字详解,干货满满,建议三连收藏)

目录 1.排序的概念及其运用 1.1排序的概念 1.2排序运用 1.3常见的排序算法 2.插入排序 2.1 原理演示&#xff1a;​编辑 2.2 算法实现 2.3 算法的时间复杂度和空间复杂度分析 3.希尔排序 3.1算法思想 3.2原理演示 3.3代码实现 3.4希尔算法的时间复杂度 4.冒泡排序 4.1冒泡排…

二、图的表示和带权图

文章目录 1、图的表示1.1 邻接矩阵1.2 邻接表1.3 关联矩阵 2、带权图2.1 最短路径问题2.2 中国邮递员问题2.3 旅行商问题 THE END 1、图的表示 1.1 邻接矩阵 \qquad 将图的所有顶点分别构成一个二维矩阵的行列&#xff0c;将顶点之间的边关系表示在构成的矩阵之中&#xff0c;…

在CentOS 8.5.2111下安装vncserver

# 参考&#xff1a; 如何在 CentOS 8/RHEL 8 上安装配置 VNC 服务器 安装CentOS 8.5.2111 及 vncserver # 标准安装步骤 安装GNOME桌面环境使用屏幕号:1。安装VNC服务器&#xff08;tigervnc-server tigervnc&#xff09;设置VNC密码设置VNC服务器配置文件开启vnc服务。开放防…

FX110网:货币交易5个亏损典型,你有中招吗?

人生百年几今日&#xff0c;今日不为真可惜&#xff01;若言姑待明朝至&#xff0c;明朝又有明朝事。很多投资朋友总是抱怨&#xff0c;为什么总是看见别人赚钱&#xff0c;自己一进场就亏损&#xff0c;那么在这里投资失败无非两点&#xff1a;一是自身原因&#xff0c;自己没…

SAP 销售分销中的免费货物

销售业务中&#xff0c;免费货物在您与客户协商价格时起着重要作用。在零售、化工或消费品这样的行业部门中&#xff0c;通常以免费货物的形式向客户提供折扣。 作为用户&#xff0c;业务用户希望能自动确定免费货物并将它们归入销售凭证中。同时需要向成本控制部门提供免费货物…

密码算法概论

基本概念 什么是密码学&#xff1f; 简单来说&#xff0c;密码学就是研究编制密码和破译密码的技术科学 例题&#xff1a; 密码学的三个阶段 古代到1949年&#xff1a;具有艺术性的科学1949到1975年&#xff1a;IBM制定了加密标准DES1976至今&#xff1a;1976年开创了公钥密…