当前位置: 首页 > news >正文

【C++练级之路】【Lv.16】红黑树(冰与火的碰撞,红与黑的史诗)



快乐的流畅:个人主页


个人专栏:《C语言》《数据结构世界》《进击的C++》

远方有一堆篝火,在为久候之人燃烧!

文章目录

  • 引言
  • 一、红黑树的概念
  • 二、红黑树的模拟实现
    • 2.1 结点
    • 2.2 成员变量
    • 2.3 插入
      • 情况一:uncle在左,parent在右
        • ==如果uncle存在且为红色==:
        • ==如果uncle不存在,或者存在且为黑色==:
      • 情况二:parent在左,uncle在右
        • ==如果uncle存在且为红色==:
        • ==如果uncle不存在,或者存在且为黑色==:
  • 三、红黑树的验证
  • 四、红黑树的性能
    • 4.1 优势
    • 4.2 适用场景

引言

之前学习的AVL树,是一种平衡二叉搜索树,它追求绝对平衡,从而导致插入和删除性能较差。而今天学习的红黑树,是另一种平衡二叉搜索树,它追求相对平衡,使得增删查改的性能都极佳,时间复杂度皆为O(log2N),是数据结构中的精华,天才般的设想!

一、红黑树的概念

红黑树,顾名思义,其节点有红和黑两种颜色。

之所以新增结点颜色的标记,是因为通过结点着色方式的限制,能够让红黑树的最长路径不超过最短路径的两倍,以保证相对平衡。


红黑树满足五条性质:

  1. 所有结点非黑即红
  2. 根结点为黑色
  3. NIL结点为黑色
  4. 红色结点的子结点必为黑色
  5. 任意结点到其叶子NIL结点的所有路径,都包含相同的黑色结点

在红黑树中,NIL节点(也称为空节点)是叶子节点的一种特殊表示。它们不是实际存储数据的节点,而是树结构中的占位符,用于定义树的边界。所有的红黑树都以NIL节点为叶子节点,这些NIL节点在视觉上通常不被画出来。


性质解读:

  • 性质4:表明不能有连续的红色结点
  • 性质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;pair<K, V> _kv;Color _col;RBTreeNode(const pair<K, V>& kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};

细节:

  1. 使用三叉链,增加了指向parent的指针
  2. 使用KV模型,数据存储键值对pair
  3. 结点储存颜色,同时颜色使用枚举
  4. 结点的颜色初始化为红色

说明:为什么结点的颜色初始化为红色呢?因为插入新节点时(不为根部),如果插入黑色,就会直接破坏性质5,导致每条路径黑结点数目不同;而如果插入红色,有可能不会破坏性质4,所以结点初始化为红色更优。

2.2 成员变量

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

2.3 插入

因为红黑树也是二叉搜索树,所以默认成员函数和遍历与之前写的没什么不同,这里重点讲解红黑树的插入。

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->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandparent = parent->_parent;if (grandparent->_right == parent)//uncle在左,parent在右{Node* uncle = grandparent->_left;if (uncle && uncle->_col == RED)//uncle为红,变色+向上调整{parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else//uncle为空或为黑,变色+旋转{if (parent->_right == cur)//左单旋{RotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else//右左旋{RotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}}}else//parent在左,uncle在右{Node* uncle = grandparent->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else{if (parent->_left == cur)//右单旋{RotateR(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else//左右旋{RotateL(parent);RotateR(grandparent);cur->_col = BLACK;grandparent->_col = RED;}}}}_root->_col = BLACK;return true;
}

思路:

  1. 以二叉搜索树的方式正常插入
  2. 讨论并调整结点的颜色,以及调整结构,使之满足红黑树的性质

循环条件:while (parent && parent->_col == RED)

保证了parent存在且为红,grandparent存在且为黑


情况一:uncle在左,parent在右

如果uncle存在且为红色

处理方法:

  1. 将parent和uncle变黑,grandparent变红
  2. cur = grandparent,parent = cur->_parent,继续向上调整
  3. 防止grandparent为根节点却变红,在循环结束后将根节点变为黑色
如果uncle不存在,或者存在且为黑色

当cur在右部外侧时:

处理方法:

  1. 先对grandparent进行左单旋
  2. 再将parent变黑,grandparent变红

当cur在右部内侧时:

处理方法:

  1. 先对parent进行右单旋
  2. 再对grandparent进行左单旋
  3. 最后将cur变黑,grandparent变红

情况二:parent在左,uncle在右

如果uncle存在且为红色

处理方法:

  1. 将parent和uncle变黑,grandparent变红
  2. cur = grandparent,parent = cur->_parent,继续向上调整
  3. 防止grandparent为根节点却变红,在循环结束后将根节点变为黑色
如果uncle不存在,或者存在且为黑色

当cur在左部外侧时:

处理方法:

  1. 先对grandparent进行右单旋
  2. 再将parent变黑,grandparent变红

当cur在左部内侧时:

处理方法:

  1. 先对parent进行左单旋
  2. 再对grandparent进行右单旋
  3. 最后将cur变黑,grandparent变红

红黑树插入的核心口诀uncle存在且为红,变色+向上调整,uncle不存在或为黑,变色+旋转


附上旋转的实现

void RotateL(Node* parent)
{Node* grandparent = parent->_parent;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;parent->_parent = subR;if (grandparent){if (grandparent->_right == parent){grandparent->_right = subR;}else{grandparent->_left = subR;}}else{_root = subR;}subR->_parent = grandparent;
}void RotateR(Node* parent)
{Node* grandparent = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subLR->_parent = parent;}subL->_right = parent;parent->_parent = subL;if (grandparent){if (grandparent->_right == parent){grandparent->_right = subL;}else{grandparent->_left = subL;}}else{_root = subL;}subL->_parent = grandparent;
}

三、红黑树的验证

bool IsBalance()
{if (_root && _root->_col == RED){cout << "根结点为红色" << endl;return false;}int benchMark = 0;//基准值Node* cur = _root;while (cur){if (cur->_col == BLACK){++benchMark;}cur = cur->_right;}return Check(_root, 0, benchMark);
}bool Check(Node* root, int blackNum, int benchMark)
{if (root == nullptr){if (blackNum != benchMark){cout << "某条路径黑色结点数量不相等" << endl;return false;}return true;}if (root->_col == BLACK){++blackNum;}if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << "存在连续的红色结点" << endl;return false;}return Check(root->_left, blackNum, benchMark)&& Check(root->_right, blackNum, benchMark);
}

细节:

  1. 验证根节点是否为黑
  2. 先计算出一条路径的黑色结点个数作为基准值,再在递归中比较每条路径的黑色结点是否相等
  3. 若该节点为红,检测其parent是否为红,判断是否存在连续的红色节点

四、红黑树的性能

4.1 优势

红黑树是高效的平衡二叉树,增删改查的时间复杂度都是O( l o g 2 N log_2 N log2N),红黑树不追求绝对平衡,其只需保证最长路径不超过最短路径的2倍,相对AVL树而言,降低了插入和旋转的次数

4.2 适用场景

因此,在经常进行增删的结构中性能比AVL树更优,而且红黑树实现比较简单,所以实际运用中红黑树更多。


真诚点赞,手有余香

相关文章:

【C++练级之路】【Lv.16】红黑树(冰与火的碰撞,红与黑的史诗)

快乐的流畅&#xff1a;个人主页 个人专栏&#xff1a;《C语言》《数据结构世界》《进击的C》 远方有一堆篝火&#xff0c;在为久候之人燃烧&#xff01; 文章目录 引言一、红黑树的概念二、红黑树的模拟实现2.1 结点2.2 成员变量2.3 插入情况一&#xff1a;uncle在左&#xff…...

政安晨:【Keras机器学习实践要点】(三)—— 编写组件与训练数据

政安晨的个人主页&#xff1a;政安晨 欢迎 &#x1f44d;点赞✍评论⭐收藏 收录专栏: TensorFlow与Keras实战演绎机器学习 希望政安晨的博客能够对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff01; 介绍 通过 Keras&#xff0c;您可以编写自定…...

数据库系统概论(超详解!!!) 第四节 关系数据库标准语言SQL(Ⅲ)

1.连接查询 连接查询&#xff1a;同时涉及多个表的查询 连接条件或连接谓词&#xff1a;用来连接两个表的条件 一般格式&#xff1a; [<表名1>.]<列名1> <比较运算符> [<表名2>.]<列名2> [<表名1>.]<列名1> BETWEEN [&l…...

如何使用Python进行网络安全与密码学【第149篇—密码学】

&#x1f47d;发现宝藏 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。【点击进入巨牛的人工智能学习网站】。 用Python进行网络安全与密码学&#xff1a;技术实践指南 随着互联网的普及&#xff0c;网络…...

应急响应-Web2

应急响应-Web2 1.攻击者的IP地址&#xff08;两个&#xff09;&#xff1f; 192.168.126.135 192.168.126.129 通过phpstudy查看日志&#xff0c;发现192.168.126.135这个IP一直在404访问 &#xff0c; 并且在日志的最后几条一直在访问system.php &#xff0c;从这可以推断 …...

复试专业前沿问题问答合集8-1——CNN、Transformer、TensorFlow、GPT

复试专业前沿问题问答合集8-1——CNN、Transformer、TensorFlow、GPT 深度学习中的CNN、Transformer、TensorFlow、GPT大语言模型的原理关系问答: Transformer与ChatGPT的关系 Transformer 是一种基于自注意力机制的深度学习模型,最初在论文《Attention is All You Need》…...

用Python做一个植物大战僵尸

植物大战僵尸是一个相对复杂的游戏&#xff0c;涉及到图形界面、动画、游戏逻辑等多个方面。用Python实现一个完整的植物大战僵尸游戏是一个大工程&#xff0c;但我们可以简化一些内容&#xff0c;做一个基础版本。 以下是一个简化版的植物大战僵尸游戏的Python实现思路&#…...

Win11文件右键菜单栏完整显示教程

近日公司电脑升级了win11&#xff0c;发现了一个小麻烦事&#xff0c;如下图&#xff1a; 当我想使用svn或git的时候必须要多点一下&#xff0c;这忍不了&#xff0c;无形之中加大了工作量&#xff01; 于是&#xff0c;菜单全显示教程如下&#xff1a; 第一步&#xff1a;管…...

【Python实用标准库】argparser使用教程

argparser使用教程 1.介绍2.基本使用3.add_argument() 参数设置4.参考 1.介绍 &#xff08;一&#xff09;argparse 模块是 Python 内置的用于命令项选项与参数解析的模块&#xff0c;其用主要在两个方面&#xff1a; 一方面在python文件中可以将算法参数集中放到一起&#x…...

伦敦金与纸黄金有什么区别?怎么选?

伦敦金与纸黄金都是与黄金相关的投资品种&#xff0c;近期黄金市场的上涨吸引了投资者的关注&#xff0c;那投资者想开户入场成为黄金投资者应该选择纸黄金还是伦敦金呢&#xff1f;两者有何区别呢&#xff1f;下面我们就来讨论一下。 伦敦金是一种起源于伦敦的标准化黄金交易合…...

化工企业能源在线监测管理系统,智能节能助力生产

化工企业能源消耗量极大&#xff0c;其节能的空间也相对较大&#xff0c;所以需要控制能耗强度&#xff0c;保持更高的能源利用率。 化工企业能源消耗现状 1、能源管理方面 计量能源消耗时&#xff0c;计量器具存在问题&#xff0c;未能对能耗情况实施完全计量&#xff0c;有…...

C/C++ 一些使用网站收集...

C/C 标准 各种语言协议标准文档 open-std.org 网站 C语言标准文档 open-std.org C基金会网站 C/C 标准库网站 c/c 标准库 cplusplus.com 网站 c/c标准库 cppreference.com 网站 C Core Guidelines【isocpp.org】 C/C 发展 C现有状态及未来规划【isocpp.org】...

2024可以搜索夸克网盘的方法

截止2024可以搜索夸克网盘的方法 6miu盘搜 6miu盘搜是一个强大的网盘搜索工具,它汇集了多个网盘平台的资源,包括百度网盘、163网盘、金山快盘等,可以帮助用户快速找到所需的资料。6miu盘搜的一个显著特点是它的资源更新速度快,可以搜索到最新的资源。此外,6miu盘搜的界面清爽…...

2024年最新阿里云服务器价格表_CPU内存+磁盘+带宽价格

2024年阿里云服务器租用费用&#xff0c;云服务器ECS经济型e实例2核2G、3M固定带宽99元一年&#xff0c;轻量应用服务器2核2G3M带宽轻量服务器一年61元&#xff0c;ECS u1服务器2核4G5M固定带宽199元一年&#xff0c;2核4G4M带宽轻量服务器一年165元12个月&#xff0c;2核4G服务…...

300.【华为OD机试】跳房子I(时间字符串排序—JavaPythonC++JS实现)

本文收录于专栏:算法之翼 本专栏所有题目均包含优质解题思路,高质量解题代码(Java&Python&C++&JS分别实现),详细代码讲解,助你深入学习,深度掌握! 文章目录 一. 题目二.解题思路三.题解代码Python题解代码JAVA题解代码C/C++题解代码JS题解代码四.代码讲解(Ja…...

linux ln Linux 系统中用于创建链接(link)的命令

linux 命令基础汇总 命令&基础描述地址linux curl命令行直接发送 http 请求Linux curl 类似 postman 直接发送 get/post 请求linux ln创建链接&#xff08;link&#xff09;的命令创建链接&#xff08;link&#xff09;的命令linux linklinux 软链接介绍linux 软链接介绍l…...

mysql按照查询条件进行排序和统计一个字段中每个不同数值出现的次数

1.比如学生表 如何显示查询结果的顺序根据放置的顺序查询 <select id"selectNames" resultType"Student">select * from student_table where 11<if test"studentList! null">and name in<foreach item"item" ind…...

深度学习基础知识

本文内容来自https://zhuanlan.zhihu.com/p/106763782 此文章是用于学习上述链接&#xff0c;方便自己理解的笔记 1.深度学习的网络结构 深度学习是神经网络的一种特殊形式&#xff0c;典型的神经网络如下图所示。 神经元&#xff1a;表示输入、中间数值、输出数值点。例如&…...

UE4_旋转节点总结一

一、Roll、Pitch、Yaw Roll 围绕X轴旋转 飞机的翻滚角 Pitch 围绕Y轴旋转 飞机的俯仰角 Yaw 围绕Z轴旋转 飞机的航向角 二、Get Forward Vector理解 测试&#xff1a; 运行&#xff1a; 三、Get Actor Rotation理解 运行效果&#xff1a; 拆分旋转体测试一&a…...

Dockerfile将jar部署成docker容器

将jar包copy到linux&#xff0c;新建Dockerfile文件 -rw-r--r-- 1 root root 52209844 Mar 25 22:55 data-sharing-0.0.1-SNAPSHOT.jar -rwxrwxrwx 1 root root 227 Mar 25 22:57 Dockerfile [rootlocalhost mnt]# pwd /mntDockerfile内容 # 指定基础镜像 FROM java:8-a…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...