C++数据结构——红黑树

前言:本篇文章我们继续来分享C++中的另一个复杂数据结构——红黑树。


目录

一.红黑树概念

二.红黑树性质

三.红黑树实现

1.基本框架

2.插入

3.判断平衡

 四.完整代码

总结


一.红黑树概念

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


二.红黑树性质

  1. 每个结点不是红色就是黑色

  2. 根节点是黑色的

  3. 如果一个节点是红色的,则它的两个孩子结点是黑色的(不存在连续的红色节点) 

  4. 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点(每条路径都存在相同数量的黑色节点) 

  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点NULL)

如何理解红黑树最长路径不超过最短路径的二倍呢???

  1.  从性质能够看出,红黑树每一条路径上,都有相同数量的黑色节点
  2. 红黑树每条路径上可以存在连续的黑色节点,但不能存在连续的红色节点
  3. 所以最短路径即为全是黑色节点的路径。
  4. 最长路径则为一黑一红相间的路径。

三.红黑树实现

1.基本框架

红黑树与AVL树相比,多了节点颜色这一信息,为了实现这一信息,我们使用枚举

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:private:Node* _root = nullptr;size_t _size = 0;
};

同时我们多创建一个_size成员变量,用于记录节点数量。 


2.插入

红黑树插入的基本步骤与二叉搜索树和AVL树一样,都是按照左子节点比根节点小,右子节点比根节点大的规则,唯一不同的是,红黑树的插入要考虑其性质。其中最值得注意的性质为:

  1. 不存在连续的红节点
  2. 每条路径上的黑节点数相等

 其中能够看出,第二条才是最关键的,因此我们每次新插入节点时,必须插入红节点

此时我们会面临两种情况

  1. 父节点为黑色,插入即结束,无需调整。
  2. 父节点为红色,不满足上述性质1,需要调整。

下面我们来看特殊情况:

父亲为红节点,那么只有将父节点变为黑色节点,才能够满足性质。

但是如果父亲变为黑节点,就说明该路径上同样多出一个黑节点,而唯一的处理手段,就是让父亲的父亲,也就是爷爷节点,变为红色节点

此时又存在问题,那就是关于父亲的兄弟节点,也就是叔叔节点,那么叔叔节点存在三种情况

  1. 叔叔节点同样为红色。
  2. 叔叔节点不存在。
  3. 叔叔节点为黑色。

如果叔叔节点为红色,为了满足各路径黑节点数量相同,叔叔节点则需要和父节点一起变为黑色

如果叔叔节点不存在,为了满足性质,需要将该子树从爷爷节点的位置进行旋转

如果叔叔节点为黑色,而父节点为红色,如果还要满足性质,说明子节点原本应为黑色,是因为经过了上述的调整而作为爷爷节点变成了红色。此时我们仍需从爷爷节点的位置进行旋转

分析完上述完整情况之后,还有关于新插入节点的两种情况

  1. 父节点为爷爷节点的左子节点,同时新增节点也为父节点的左子节点,为一条斜线。
  2. 父节点为爷爷节点的左子节点,但是新增节点也为父节点的有子节点,为一条折线。

斜线情况下,我们在需要旋转时只需单旋即可;

而当为折线时,就需要进行双旋,先变为斜线,在进行调整。

同时父节点也需要考虑是爷爷节点的左节点还是右节点两种情况,彼此的规则相反

按照上边的步骤,我们能够得出代码情况:

//插入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 (kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//parent是黑色就结束while (parent && parent->_col == RED){Node* Grandfather = parent->_parent;if (parent == Grandfather->_left){Node* uncle = Grandfather->_right;if (uncle && uncle->_col == RED)//叔叔存在且为红,直接变色{parent->_col = BLACK;uncle->_col = BLACK;Grandfather->_col = RED;//继续往上处理cur = Grandfather;parent = Grandfather->_parent;}else//叔叔不存在或叔叔存在但为黑{if (cur == parent->_left)//左边直接右旋{RotateR(Grandfather);parent->_col = BLACK;Grandfather->_col = RED;}else//右边则左右双旋{RotateL(parent);RotateR(Grandfather);cur->_col = BLACK;Grandfather->_col = RED;}break;}}else{Node* uncle = Grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;Grandfather->_col = RED;cur = Grandfather;parent = Grandfather->_parent;}else{if (cur == parent->_right){RotateL(Grandfather);Grandfather->_col = RED;parent->_col = BLACK;}else{RotateR(parent);RotateL(Grandfather);cur->_col = BLACK;Grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}

 需要考虑的情况确实很多,但如果自己画图认真分析,理解起来还是易如反掌的


3.判断平衡

判断红黑树的平衡,我们自然要从其性质入手:

  1. 首先就是判断根节点是否为黑色
  2. 其次容易判断的是是否有两个相邻的红色节点,注意这里我们不去判断一个节点与其子节点,反而去判断一个节点与其父节点。因为如果判断子节点,则可能需要判断两次,而父节点则只需判断一次
  3. 最后就是判断所有路径上的黑节点数量是否相同

其中前两种都比较容易想到代码方式,最重要的是如何比较黑节点的数量

我们可以通过增加参数的方式。来记录到达每个节点位置时,该路径上出现过的黑节点的数量。而如何进行比较,因为每条路径上黑节点的数量都必须相同,所以我们直接记录一下最左边的一条路径上黑节点的数量,然后求出一条路径上的黑节点数之后,就进行比较即可

	//判断平衡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);}bool Check(Node* root, int BlackNum,const int refnum){if (root == nullptr){if (refnum != BlackNum){cout << "存在黑色节点个数不相等" << endl;return false;}cout << BlackNum << endl;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);}

 四.完整代码

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 (kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//parent是黑色就结束while (parent && parent->_col == RED){Node* Grandfather = parent->_parent;if (parent == Grandfather->_left){Node* uncle = Grandfather->_right;if (uncle && uncle->_col == RED)//叔叔存在且为红,直接变色{parent->_col = BLACK;uncle->_col = BLACK;Grandfather->_col = RED;//继续往上处理cur = Grandfather;parent = Grandfather->_parent;}else//叔叔不存在或叔叔存在但为黑{if (cur == parent->_left)//左边直接右旋{RotateR(Grandfather);parent->_col = BLACK;Grandfather->_col = RED;}else//右边则左右双旋{RotateL(parent);RotateR(Grandfather);cur->_col = BLACK;Grandfather->_col = RED;}break;}}else{Node* uncle = Grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;Grandfather->_col = RED;cur = Grandfather;parent = Grandfather->_parent;}else{if (cur == parent->_right){RotateL(Grandfather);Grandfather->_col = RED;parent->_col = BLACK;}else{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;elseppNode->_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->_left == parent)ppNode->_left = subR;elseppNode->_right = subR;subR->_parent = ppNode;}}//遍历void InOrder(){inOrder(_root);cout << endl;}void inOrder(const Node* root){if (root == nullptr){return;}inOrder(root->_left);cout << root->_kv.first << ':' << root->_kv.second << endl;inOrder(root->_right);}//判断平衡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);}bool Check(Node* root, int BlackNum,const int refnum){if (root == nullptr){if (refnum != BlackNum){cout << "存在黑色节点个数不相等" << endl;return false;}cout << BlackNum << endl;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);}
private:Node* _root = nullptr;//size_t _size = 0;
};

总结

关于红黑树的知识就分享这么多,喜欢本篇文章记得一键三连,我们下期再见!

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

一个不知名的开源项目可以带来多少收入

起源 2020 年新冠疫情开始蔓延&#xff0c;当时我在同时经营 3 个不同的公司。除了其中的体育赛事平台因为疫情关门大吉之外&#xff0c;另外两个公司并没有受影响&#xff0c;营收和利润反而都持续增加。但是连续几个月不能出远门&#xff0c;也不能随便见朋友和客户&#xff…

Kafka学习-Java使用Kafka

文章目录 前言一、Kafka1、什么是消息队列offset 2、高性能topicpartition 3、高扩展broker 4、高可用replicas、leader、follower 5、持久化和过期策略6、消费者组7、Zookeeper8、架构图 二、安装Zookeeper三、安装Kafka四、Java中使用Kafka1、引入依赖2、生产者3、消费者4、运…

【C语言】/*操作符(下)*/

目录 一、操作符的分类 二、二进制和进制转换 2.1 进制 2.2 进制之间的转换 三、原码、反码、补码 四、单目操作符 五、逗号表达式 六、下标引用操作符[] 七、函数调用操作符() 八、结构体成员访问操作符 8.1 直接访问操作符(.) 8.2 间接访问操作符(->) 九、操作符…

【Spring】初识 Spring AOP(面向切面编程)

目录 1、介绍AOP 1.1、AOP的定义 1.2、AOP的作用 1.3、AOP的核心概念及术语 2、AOP实现示例 3、EnableAspectJAutoProxy注解 1、介绍AOP 1.1、AOP的定义 AOP&#xff08;Aspect Orient Programming&#xff09;&#xff0c;直译过来就是面向切面编程&#xff0c;AOP 是一…

[动画详解]LeetCode151.翻转字符串里的单词

&#x1f496;&#x1f496;&#x1f496;欢迎来到我的博客&#xff0c;我是anmory&#x1f496;&#x1f496;&#x1f496; 又和大家见面了 欢迎来到动画详解LeetCode算法系列 用通俗易懂的动画让算法题不再神秘 先来自我推荐一波 个人网站欢迎访问以及捐款 推荐阅读 如何低成…

十二生肖Midjourney绘画大挑战:释放你的创意火花

随着AI艺术逐渐进入大众视野&#xff0c;使用Midjourney绘制十二生肖不仅能够激发我们的想象力&#xff0c;还能让我们与传统文化进行一场新式的对话。在这里&#xff0c;我们会逐一提供给你创意满满的绘画提示词&#xff0c;让你的作品别具一格。而且&#xff0c;我们还精选了…

Python进行excel处理-01

最近干采购&#xff0c;每个月要对供应商的对账单&#xff0c;对对应的采购订单号和物料编号的价格和数量&#xff0c;是不是和物料管控总表里面的价格数量是不是一致&#xff0c;于是写了一个代码。 从总表里面找到&#xff0c;对账单里对应采购订单和物料编码的数据&#xf…

vscode 通过ssh 远程执行ipynb +可以切换conda env

主要是保证几个点 远程服务器python 环境没问题 conda这些也都有的ssh的账户 是有conda权限的没有免密就输入密码 免密教程就是最基本的那种 公钥copy过去就行了vscode 那几个插件都要装好 开始操作 首先 vscode 点击左侧工具栏中的扩展&#xff0c;搜索“ssh”&#xff0c;…

计算机vcruntime140.dll找不到如何修复,分享5种靠谱的修复教程

当您在运行某个应用程序或游戏时遇到提示“找不到vcruntime140.dll”&#xff0c;这通常意味着系统中缺少了Visual C Redistributable for Visual Studio 2015或更高版本的一个重要组件。这个错误通常发生在运行某些程序时&#xff0c;系统无法找到所需的动态链接库文件。小编将…

(四十二)第 6 章 树和二叉树(树的二叉链表(孩子-兄弟)存储)

1. 背景说明 2. 示例代码 1) errorRecord.h // 记录错误宏定义头文件#ifndef ERROR_RECORD_H #define ERROR_RECORD_H#include <stdio.h> #include <string.h> #include <stdint.h>// 从文件路径中提取文件名 #define FILE_NAME(X) strrchr(X, \\) ? strrch…

15-ps命令

常用选项 aux axjf a&#xff1a;显示一个终端所有的进程u&#xff1a;显示进程的归属用户及内存使用情况x&#xff1a;显示没有关联控制终端j&#xff1a;显示进程归属的进程组idf&#xff1a;以ASCII码的形式显示出进程的层次关系 ps aux其中| more是只显示一部分内容&…

【实战】算法思路总结

面试过程中&#xff0c;总是被拷打&#xff0c;信心都要没了。但是也慢慢摸索出一些思路&#xff0c;希望对大家有帮助。 &#xff08;需要多用一下ACM模式&#xff0c;力扣模式提供好了模板&#xff0c;自己在IDEA里面写的话&#xff0c;还是会有些陌生&#xff09; 0、基本…

Edge(微软)——一款充满创新精神的浏览器

随着科技的不断进步&#xff0c;互联网浏览器已经成为我们日常生活中不可或缺的工具。在这个领域&#xff0c;微软Edge作为一款新型的浏览器&#xff0c;凭借其独特的功能和优秀的性能&#xff0c;逐渐在市场上占据了一席之地。本文将深入探索微软Edge的特点、优势以及它如何改…

Acrobat Pro DC 2023 for Mac:PDF处理的终极解决方案

Acrobat Pro DC 2023 for Mac为Mac用户提供了PDF处理的终极解决方案。它具备强大的文档处理能力&#xff0c;无论是查看、编辑还是创建PDF文件&#xff0c;都能轻松胜任。在编辑功能方面&#xff0c;Acrobat Pro DC 2023支持对文本、图像进行精准的修改和调整&#xff0c;还能添…

一台linux通过另一台linux访问互联网-TinyProxy

参考&#xff1a; https://blog.csdn.net/weixin_41831919/article/details/113061317https://www.yuncongz.com/archives/1.htmlhttps://blog.csdn.net/aoc68397/article/details/101893369 环境&#xff1a;ubuntu 18.04 机器1: IP 219.216.65.252 (可以访问外网) 机器2: IP…

廉洁教育vr虚拟全景展览馆成为社会普法的重要基石

廉政教育是社会文明的重要基石&#xff0c;也是我们每个人的责任与担当。在这个数字化、信息化的新时代&#xff0c;我们特别推出廉政3D线上数字展厅&#xff0c;为公众打造一个沉浸式、互动式的廉政教育新平台。 走进廉政3D线上数字展厅&#xff0c;就如同置身于一个充满智慧与…

[笔试训练](二十二)064:添加字符065:数组变换066:装箱问题

目录 064:添加字符 065:数组变换 066:装箱问题 064:添加字符 添加字符_牛客笔试题_牛客网 (nowcoder.com) 题目&#xff1a; 题解&#xff1a; 枚举所有A&#xff0c;B字符串可能的对应位置&#xff0c;得出对应位置不同字符数量的最小情况 两字符串的字符数量差n-m&…

Keil编程不同驱动文件引用同一个常量的处理方法

基础不牢&#xff0c;地动山摇&#xff0c;最近单片机编程又遇到一个基础问题。 我在头文件中定义了一个常量同时给两个驱动文件使用&#xff0c;封装的时候编译没问题&#xff0c;但是在main函数中引用驱动函数的时候就出现了重定义的问题&#xff0c;如下如所示。 解决方法很…

搜索引擎的设计与实现(三)

目录 5 系统详细实现 5.1实现环境配置 5.2功能实现 5.2.1 建立索引 5.2.2 文件搜索实现 5.2.3 数据库的连接配置 5.2.4 数据库搜索实现 5.2.5 后台数据编辑实现 前面内容请移步 搜索引擎的设计与实现&#xff08;二&#xff09; 免费源代码&毕业设计论文 搜索…

Linux学习笔记1---Windows上运行Linux

在正点原子的教程中学习linux需要安装虚拟机或者在电脑上安装一个Ubuntu系统&#xff0c;但个人觉得太麻烦了&#xff0c;现在linux之父加入了微软&#xff0c;因此在Windows上也可以运行linux 了。具体方法如下&#xff1a; 一、 在Windows上的设置 在window的搜索框内&#…