【C++进阶06】红黑树图文详解及C++模拟实现红黑树
一、红黑树的概念及性质
1.1 红黑树的概念
AVL树用平衡因子让树达到高度平衡
红黑树可以认为是AVL树的改良
通过给每个节点标记颜色让树接近平衡
以减少树在插入节点的旋转
在每个结点新增一个存储位表示结点颜色
可以是Red或Black
通过对任何一条从根到叶子的路径上
各个结点着色方式的限制
红黑树确保没有一条路径会比其他路径长出
俩倍,因而是接近平衡的
1.2 红黑树的性质
- 每个结点不是红色就是黑色
- 根节点是黑色的
如果一个节点是红色的
则它的两个孩子结点是黑色的
对于每个结点
从该结点到其所有后代叶结点的简单路径上
均包含相同数目的黑色结点
- 每个叶子结点都是黑色的
(此处的叶子结点指的是空结点)
为啥满足上面性质的红黑树就能保证
其最长路径节点个数不会超过最短路径
节点个数的两倍?
由性质3可得出不能出现连续红色节点
由性质4可得出每条路径有相同黑色节点数量
极限情况下
最短路径:
全黑
最长路径:
一黑一红
由此可得出
最长路径不会超过最短路径的两倍
1.3 为什么更常用红黑树而不是AVL树?
AVL树: 是一颗高度平衡的二叉树
查找效率: O ( l o g N ) O(logN) O(logN)
但是这样的效率是在插入元素时
经常性的旋转换来的
红黑树: 是一颗接近平衡的二叉树
假设全部黑节点有N个
整棵树的节点数量:[N, 2N]之间
最短路径长度: O ( l o g N ) O(logN) O(logN)
最长路径长度: O ( 2 l o g N ) O(2logN) O(2logN)
查找效率: O ( 2 l o g N ) O(2logN) O(2logN)
10亿数据AVL树最多查找30次
红黑树最多也就查找60次
对于cpu的运行速度来说几乎可以忽略不计
但红黑树的规则相对于AVL树没那么严格
在插入元素时,不会经常旋转
所以综合而言红黑树更胜一筹
如图: 对于AVL树必定旋转
红黑树则不用
二、红黑树模拟实现的基本框架
2.1 红黑树节点的定义
跟AVL树一样
只是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;
};
2.2 红黑树的插入
还是和AVL树一样
bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);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->_left = cur;}else{parent->_right = cur;}// new的节点的parent还指向空cur->_parent = parent;// 插入黑色节点还是红色节点?return true;}
插入走到这里如果是AVL树
此时需要更新平衡因子
红黑树采用的是标记节点颜色
让树达到平衡
需要考虑的是插入什么颜色的节点?
插入黑色节点
会违反规则4,影响到每条路径插入红色节点
如果插入节点的父节点也是红色节点
则会违反规则3影响当前局部节点
很明显插入红色节点更划算
所有插入的节点都默认是红色
如果违反红黑树的规则,再进行调整
三、对插入节点调整的解析
如果插入节点的父节点为黑
则无需处理
如果为红,则分为三种情况
情况一:
cur为红,p为红,g为黑,u存在且为红
cur为当前节点,p为父节点
g为祖父节点,u为叔叔节点
把p和u变黑,g变红
如果grandfather的parent也为红
把grandfather改为cur
继续按刚才的步骤往后迭代
如果grandfather为根节点
把grandfather改为黑色
颜色调整结束
情况二:
cur为红,p为红,g为黑
u不存在或u存在且为黑
此树可能是完整树也可能是子树
u节点不存在
p为g的左孩子,cur为p的左孩子
则进行右单旋转
相反
p为g的右孩子,cur为p的右孩子
则进行左单旋转
p、g变色–p变黑,g变红
下图则是u节点存在的情况
c为下面4种情况的
任意一种包含一个黑节点的红黑树
d和e可能是空或者一个红节点
插入新节点,更新完后
继续往后更新
就是情况二的u存在的情况
情况三:
cur为红,p为红,g为黑
u不存在或u存在且为黑
跟情况二完全类似
只是情况三为双旋
情况二是单旋
p为g的左孩子,cur为p的右孩子
则针对p做左单旋转
相反
p为g的右孩子,cur为p的左孩子
则针对p做右单旋转
则转换成了情况2
此图为u不存在
u存在参考情况二
四、红黑树插入代码的全部实现
详解都在代码注释
各位友友们请耐心看完
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);if (parent->_kv.first > kv.first){parent->_left = cur;}else{parent->_right = cur;}// new的节点的parent还指向空cur->_parent = parent;// 如果新插入节点破坏了红黑树规则// 则更新节点颜色while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;// 情况1:u存在且为红,变色处理,并继续往上处理if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续往上调整cur = grandfather;parent = cur->_parent;}else // 情况2+3:u不存在或者u存在且为黑,旋转+处理{// 如果插入节点在父节点的左,c、p、g呈一条斜线// g// p u// cif (parent->_left == cur){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED; }else{// 插入节点在父节点的右,c、p、g呈一条折线// g// p u// cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;// parent->_col = RED; // 父亲本就是红,变一下双重保险grandfather->_col = RED;}break;}}else // (grandfather->_right == parent){Node* uncle = grandfather->_left;// 情况1:u存在且为红,变色处理,并继续往上处理if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续往上调整cur = grandfather;parent = cur->_parent;}else // 情况2+3:u不存在或者u存在且为黑,旋转+处理{// g// u p// cif (parent->_right == cur){RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK; // 做个双保险,无论那种情况把根都变成黑的return true;
}
五、红黑树全部代码模拟实现
gitee链接
✨✨✨✨✨✨✨✨
本篇博客完,感谢阅读🌹
如有错误之处可评论指出
博主会耐心听取每条意见
✨✨✨✨✨✨✨✨
相关文章:

【C++进阶06】红黑树图文详解及C++模拟实现红黑树
一、红黑树的概念及性质 1.1 红黑树的概念 AVL树用平衡因子让树达到高度平衡 红黑树可以认为是AVL树的改良 通过给每个节点标记颜色让树接近平衡 以减少树在插入节点的旋转 在每个结点新增一个存储位表示结点颜色 可以是Red或Black 通过对任何一条从根到叶子的路径上 各个结点…...
2023年最严重的10起0Day漏洞攻击事件
根据谷歌公司威胁分析小组去年 7 月发布的报告显示,2022 年全球共有 41 个 0day 漏洞被利用和披露。而研究人员普遍认为,2023 年被利用的 0Day 漏洞数量会比 2022 年更高,这些危险的漏洞被广泛用于商业间谍活动、网络攻击活动以及数据勒索攻击…...

Linux之Iptables简易应用
文档形成时期:2009-2024年 和iptables打交道有15年了,经过无数实践后,形成一个简易应用文档。 文档主题是简易应用,所以其原理不详述了。 因软件世界之复杂和个人能力之限,难免疏漏和错误,欢迎指正。 文章目…...

树状结构查询 - 华为OD统一考试
OD统一考试 分值: 200分 题解: Java / Python / C++ 题目描述 通常使用多行的节点、父节点表示一棵树,比如: 西安 陕西 陕西 中国 江西 中国 中国 亚洲 泰国 亚洲 输入一个节点之后,请打印出来树中他的所有下层节点。 输入描述 第一行输入行数,下面是多行数据,每行以…...

版本控制系统教程
1.Git的基本介绍 1.1 Git的概念 Git是一个开源的分布式版本控制系统,用于敏捷高效地处理任何或小或大的项目.Git是Linus Torvalds为了帮助管理Linux内核开发而开发的一个开放源码的版本控制软件.Git与常用的版本控制工具CVS,Subversion等不同ÿ…...

Java多线程并发篇----第十篇
系列文章目录 文章目录 系列文章目录前言一、start 与 run 区别二、JAVA 后台线程三、什么是乐观锁前言 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站,这篇文章男女通用,看懂了就去分享给你的码吧。 一、start 与 r…...

模型\视图一般步骤:为什么经常要用“选择模型”QItemSelectionModel?
一、“使用视图”一般的步骤: //1.创建 模型(这里是数据模型!) tabModelnew QSqlTableModel(this,DB);//数据表 //2.设置 视图的模型(这里是数据模型!) ui->tableView->setModel(tabModel); 模型种类: QStringListModel…...

C#,愚弄数(Hoax Number)的计算方法与源代码
一、愚弄数(Hoax Number) 愚弄数(Hoax Number)是一种组合数字, 其数字总和等于其不同质因数的数字总和。 注:1不被视为质数, 因此它不包含在不同质因数的总和中。 有些愚弄数(Hoax Number)数字也…...

c JPEG编码,此程序没有处现MCU中亮度分量的排序
#include <stdio.h> #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #include <stdlib.h> #include <unistd.h> #include <sys/ioctl.h> #include <linux/videodev2.h> //v4l2 头文件 #include <strin…...

前端规范扩展
前端编程规范是基于原有vue2基础上那套《编码风格及标准》上,应用于vue3、typescript、vite2基础上延伸出来的扩展补充,持续完善 一、编码规范 ESLint 代码检测工具 Pretter 代码格式化工具配合双校验代码 Git 规范 - 编码工具 vscode 同步参考文档中…...

【AI视野·今日NLP 自然语言处理论文速览 第七十二期】Mon, 8 Jan 2024
AI视野今日CS.NLP 自然语言处理论文速览 Mon, 8 Jan 2024 Totally 17 papers 👉上期速览✈更多精彩请移步主页 Daily Computation and Language Papers DeepSeek LLM: Scaling Open-Source Language Models with Longtermism Authors DeepSeek AI Xiao Bi, Deli Ch…...

RT-Thread基于AT32单片机的CAN应用
1 硬件电路 2 RT-Thread驱动配置 RT-Studio中没有CAN相关的图形配置,需要手动修改board.h。在board.h的末尾,增加相关的BSP配置。 #define RT_CAN_USING_HDR #define BSP_USING_CAN13 IO配置 at32_msp.c中的IO配置是PB9和PB10,掌上实验室V…...

LeetCode---121双周赛---数位dp
题目列表 2996. 大于等于顺序前缀和的最小缺失整数 2997. 使数组异或和等于 K 的最少操作次数 2998. 使 X 和 Y 相等的最少操作次数 2999. 统计强大整数的数目 一、大于等于顺序前缀和的最小缺失整数 简单的模拟题,只要按照题目的要求去写代码即可,…...

RT-Thread I/O设备模型
I/O设备模型 绝大部分的嵌入式系统都包括一些I/O(Input/Output,输入/输出)设备,例如仪器上的数据显示屏、工业设备上的串口通信、数据采集设备上用于保存数据的Flash或SD卡,以及网络设备的以太网接口等,都…...

CloudCompare——拟合空间球
目录 1.拟合球2.软件操作3.算法源码4.相关代码 本文由CSDN点云侠原创,CloudCompare——拟合空间球,爬虫自重。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫与GPT生成的文章。 1.拟合球 源码里用到了四点定球,…...

哪个牌子的护眼台灯适合学生?2024护眼台灯推荐
不知道各位父母对孩子的视力健康有没有关注,我国儿童青少年的近视率高达52.7%,也就是说,平均是个儿童中就有五个儿童存在视力问题,而且近视发生年龄提前至3到7岁。作为一名眼部护理博主,孩子从小看书、看屏幕起&#x…...

适用于动态 IT 环境的服务器流量监控软件
服务器在网络性能中起着至关重要的作用,这意味着保持其最佳容量至关重要。企业需要将 AI、ML 和云技术融入其 IT 中,从而提供充分的敏捷性、安全性和灵活性,在这方面,服务器流量监控已成为当务之急。通过定期监控通信、跟踪流量上…...
Java的Jar包和War包
在Java中,JAR(Java Archive)和WAR(Web Archive)都是用于打包和分发Java应用程序的压缩文件格式。它们在不同的应用场景中使用: JAR(Java Archive): 用途: 主要…...
第二十一章 javascript数据代理(数据劫持)
文章目录 一、数据劫持对象的访问器属性 二、Object.defineProperty()三、Proxy()四、补充1. Object类新增方法2. Array类新增方法 一、数据劫持 数据劫持:能够拦截到数据被使用或被修改的时机,在这个时机除了可以获取数据的值或对数据的值进行修改之外…...

苹果电脑RAW图像处理软件Capture One Pro 22 mac软件介绍
Capture One Pro 22 for mac是一款专业的RAW文件转换器和图像编辑软件,拥有更新的处理引擎、市场领先的性能和强大的新功能,可为 500 多台高端相机提供具有美丽色彩和令人难以置信的细节的终极图像质量。 Capture One Pro 22 for Mac版软件介绍 Capture…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...

Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...

C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill
视觉语言模型(Vision-Language Models, VLMs),为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展,机器人仍难以胜任复杂的长时程任务(如家具装配),主要受限于人…...
Redis:现代应用开发的高效内存数据存储利器
一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...