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

第八节：红黑树（初阶）

news 来源：原创 2025/8/18 3:48:16

【本节要点】

红黑树概念
红黑树性质
红黑树结点定义
红黑树结构
红黑树插入操作的分析

一、红黑树的概念与性质

1.1 红黑树的概念

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

红黑树构造：[10(黑)] /        \[5(红)]     [20(黑)]/     \       /     \[3(黑)] [8(黑)] [15(红)] [25(红)]/  \    /  \     /  \    /  \NIL NIL  NIL NIL  NIL NIL NIL NIL

1.2 红黑树的性质

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

以上五点性质可以保证：其最长路径中节点个数不会超过最短路径节点个数的两倍。

二、红黑树结点定义

// 结点的颜色
enum Colour
{RED,BLACK,
};// 红黑树结点的定义
template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv;            // 结点的键值对RBTreeNode<K, V>* _left;   // 结点的左孩子RBTreeNode<K, V>* _right;  // 结点的右孩子RBTreeNode<K, V>* _parent; // 结点的双亲（红黑树需要旋转，为了实现简单所以给出该结点）Colour _col;               // 结点的颜色// 结点的构造函数RBTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}
};

注意：红黑树定义结点时，默认结点颜色为红色，这一设计选择直接增加红黑树的平衡维护效率和整体性能，大大减少时间复杂度。

三、红黑树的结构

// 以本数组为例
num[3, 5, 8, 10, 15, 20, 25]

红黑树构造：[10(黑)] /        \[5(红)]     [20(黑)]/     \       /     \[3(黑)] [8(黑)] [15(红)] [25(红)]/  \    /  \     /  \    /  \NIL NIL  NIL NIL  NIL NIL NIL NIL

图示说明

根结点标记：根结点 10 为黑色，符合性质2（根结点必黑）
红色结点规则：红色结点 5、15、25 的子结点均为黑色，满足性质3（红色结点不连续）
黑高一致性验证：从根结点到任意 NIL 的路径黑色结点数均为 2
NIL结点处理：所有叶子结点显式标记为 NIL（黑色），符合性质5
最长/最短路径对比

路径类型示例路径结点数比例
最短路径 10→20→NIL 2 1:1
最长路径 10→5→3→NIL 3 1.5:1
理论极限 红黑交替路径（未出现） ≤4 ≤2:1

路径类型	示例路径	结点数	比例
最短路径	10→20→NIL	2	1:1
最长路径	10→5→3→NIL	3	1.5:1
理论极限	红黑交替路径（未出现）	≤4	≤2:1

四、红黑树的插入操作

                              [开始插入新结点Z]│▼┌─────────执行标准BST插入─────────┐│                                │▼                                ▼[Z设为红色]                   [保持BST性质]│▼┌─────父结点P是否为红色？─────┐│                            │▼ (是)                       ▼ (否)[存在双红冲突需处理]               [插入完成]│▼┌────叔结点U的颜色？────┐│                      │▼ (红色)               ▼ (黑色/NIL)
[Case1: 颜色翻转]     [判断冲突结构类型]│                      │▼                      ├─────────────────────────┐
[将P、U设为黑色]           ▼                         ▼│               [Z-P-G呈三角型]            [Z-P-G呈直线型]▼                      │                         │
[将G设为红色]        [Case2: 旋转父结点]      [Case3: 旋转祖父结点]│                      │                         │▼                      ▼                         ▼
[以G为新Z向上回溯]   [转为直线型冲突]         [交换颜色并旋转]│▼[调整完成]│▼[最终确保根结点为黑]

4.1 基本BST插入阶段

插入位置遵循二叉搜索树规则
新结点初始颜色必须为红色（最小化规则破坏）

4.2 冲突检测阶段

要素1：父结点状态判断
要素2：叔结点颜色判定
要素3：冲突结构类型识别

4.3 典型场景演练

场景1：叔结点为红（Case1）
         G(黑)                 G(红)/   \     颜色翻转     /   \P(红) U(红)  →       P(黑) U(黑)/                   /Z(红)              Z(红)
检测要点：

确认U存在且为红

将冲突标记上移给G

继续以G作为新Z向上检测

场景2：叔结点为黑-三角型（Case2）
     G(黑)            G(黑)/               /P(红)   →      Z(红)\           /Z(红)     P(红)
检测要点：

判断Z是P的右子结点

识别为三角型冲突

转换为直线型处理

场景3：叔结点为黑-直线型（Case3）
      G(黑)             P(黑)/               /   \P(红)   →      Z(红) G(红)/Z(红)
检测要点：

确认Z是P的左子结点

直接触发祖父旋转

完成颜色交换

4.4 总结

冲突检测阶段通过三级条件筛选（父结点状态→叔结点颜色→冲突结构类型），将复杂的平衡问题分解为可控的局部操作。这种分层检测机制：

确保90%以上的插入操作只需1次检测即可完成
将最坏情况的时间复杂度严格控制在O(log n)
为后续的旋转/颜色调整提供精准的操作依据

该设计体现了红黑树"以检测换计算，以分类求高效"的核心优化思想，是其能在大规模数据场景下保持卓越性能的关键所在。

以上就是红黑树初阶知识的了解，接下来我会继续更新红黑树进阶：红黑树的模拟实现、使用红黑树底层对map和set容器的模拟实现。制作不易，请大家多多点赞收藏啦！！

第八节：红黑树（初阶）

【本节要点】红黑树概念红黑树性质红黑树结点定义红黑树结构红黑树插入操作的分析一、红黑树的概念与性质 1.1 红黑树的概念红黑树 ，是一种二叉搜索树 ，但在每个结点上增加一个存储位表示结点的颜色，可以是 Red和 Black 。通过对任何…...

编程日记 2025/8/18 3:48:16

【C++标准库类型】深入理解C++中的using声明：从基础到实践

目录一、using声明基础 1.1 基本语法形式 1.2 典型应用场景 1.3 作用域规则二、关键注意事项 2.1 命名冲突处理 2.2 头文件使用规范 2.3 与typedef的对比三、面向对象中的应用 3.1. 解除派生类名称隐藏（核心应用） 3.2. 构造函数继承&#…...

编程日记 2025/8/17 10:09:23

蓝桥杯2024年第十五届省赛真题-回文数组

题目描述小蓝在无聊时随机生成了一个长度为 n 的整数数组，数组中的第 i 个数为ai，他觉得随机生成的数组不太美观，想把它变成回文数组，也是就对于任意i ∈ [1, n] 满足 ai an−i1 。小蓝一次操作可以指定相邻的两个数&#xff0c…...

编程日记 2025/8/16 9:51:09

多数元素——面试经典150题（力扣）

题目给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。示例 1： 输入：nums [3,2,3] 输出：3 …...

编程日记 2025/8/15 16:41:05

QT中委托QStyledItemDelegate的使用

目录一、子类化委托二、委托方法实现 1）createEditor 2）setEditorData 3）setModelData 4）updateEditorGeometry 三、委托使用四、总结 Qt的数据容器控件采用模型/视图(model/view)架构设计。模型用于存放控件的数据，视图则用于显示编辑数据，而委托则是…...

编程日记 2025/8/16 10:41:10

android 调用wps打开文档并感知保存事件

需求场景在项目开发中会碰到需要调用WPS打开Word,Excel,Ppt等Office系列文档的情况，网上目前少有正式介绍如何调用相关API打开文档，并实现文档编辑后回传给三方应用，本人在逛WPS社区时发现解锁WPS二次开发新世界：Android开发用…...

编程日记 2025/8/16 9:52:11

前端 Webpack 面试题

1、什么是 Webpack？它有什么作用？ Webpack 是一个前端资源打包工具，用于将 JavaScript、CSS、图片等项目资源进行模块化管理和打包。它能够将复杂的项目结构转化为浏览器友好的代码，提高前端项目的开发效率和性能。模块打包：Webpack 将项目中的各个模块及依赖打包成一个…...

编程日记 2025/8/16 12:06:03

05延迟任务精准发布文章（redis实现延迟任务、分布式锁）

上架不代表发布(需要发布app端才会显示文章） 1)文章定时发布 2)延迟任务概述 2.1)什么是延迟任务定时任务：有固定周期的，有明确的触发时间延迟队列：没有固定的开始时间，它常常是由一个事件触发的，而在…...

编程日记 2025/8/16 11:19:05

十六、从零搭建一个 Vue 3 后台管理系统：完整实战教程

Vue 3 作为当下最为流行的前端框架之一，凭借其简洁的 API 以及强大的性能，已然成为构建后台管理系统的首选工具。本文将一步一步地引导你从零开始搭建一个 Vue 3 后台管理系统，内容涵盖路由、权限管理、状态管理等核心功能，并且会…...

编程日记 2025/8/16 9:53:05

never_give_up

一个很有意思的题： never_give_up - Bugku CTF平台注意到注释里面有1p.html，我们直接在源代码界面看，这样就不会跳转到它那个链接的： 然后解码可得： ";if(!$_GET[id]) {header(Location: hello.php?id1);exi…...

编程日记 2025/8/17 11:47:52

DeepSeek结合Mermaid绘图（流程图、时序图、类图、状态图、甘特图、饼图）转载

思维速览： 本文将详细介绍如何利用DeepSeek结合Mermaid语法绘制各类专业图表，帮助你提高工作效率和文档质量。 ▍DeepSeek入门使用请看：deepseek保姆级入门教程（网页端使用本地客户端部署使用技巧） DeepSeek官网…...

编程日记 2025/8/16 9:45:14

「基于大模型的智能客服系统」语义理解、上下文记忆与反馈机制设计

网罗开发 （小红书、快手、视频号同名） 大家好，我是展菲，目前在上市企业从事人工智能项目研发管理工作，平时热衷于分享各种编程领域的软硬技能知识以及前沿技术，包括iOS、前端、Harmony OS、Java、Python等…...

编程日记 2025/8/16 9:45:26

【后端】【django】导出 API 文档的几种方法

在 Django 项目里，导出 API 文档是很常见的需求，一般可以借助第三方库来实现。使用 drf-yasg 导出 Swagger/OpenAPI 格式文档 drf-yasg 是一个用于 Django REST framework 的工具，能够自动生成 Swagger 和 OpenAPI 格式的 API 文档。步骤…...

编程日记 2025/8/16 9:45:11

【HarmonyOS Next之旅】DevEco Studio使用指南(二)

目录 1 -> 工程模板介绍 2 -> 创建一个新的工程 2.1 -> 创建和配置新工程 2.1.1 -> 创建HarmonyOS工程 2.2.2 -> 创建OpenHarmony工程 1 -> 工程模板介绍 DevEco Studio支持多种品类的应用/元服务开发，预置丰富的工程模板，可以根…...

编程日记 2025/8/17 14:37:56

鸿蒙Next开发与实战经验总结

文章目录 1. 鸿蒙Next概述与开发环境搭建1.1 鸿蒙Next的核心特性1.2 开发环境搭建与工具链安装步骤工具链 1.3 第一个鸿蒙Next应用代码示例流程图 2. 鸿蒙Next应用架构与设计模式2.1 应用架构解析2.2 常用设计模式2.3 组件化开发实践 3. UI开发与布局系统3.1 基础UI组件3.2 布局…...

编程日记 2025/8/16 9:45:16

uniapp实现 uview1 u-button的水波纹效果

说明： 由于uview2已经移除水波纹效果，这边又觉得那个效果好看，所以开发这个功能(原谅我不会录动图) 效果： 具体代码： <view class"ripple-container" touchstart"handleTouchStart" touchend&…...

编程日记 2025/8/16 9:53:55

Linux练级宝典-＞任务管理和守护进程

任务管理进程组概念每个进程除了进程ID以外，还有一个进程组，进程组就是一个或多个进程的集合同一个进程组，代表着他们是共同作业的，可以接收同一个终端的各种信号，进程组也有其唯一的进程组号。还有一个组长进程&a…...

编程日记 2025/8/16 12:56:24

金融行业替换传统的FTP传输系统的必要性

在如今这个数字化飞速发展的时代，金融行业对于信息安全性和数据传输效率的要求简直高得离谱。可是呢，你可能想不到，很多金融机构竟然还在用传统的FTP（文件传输协议）来处理日常的数据交换。 FTP在过去几十年里确实是网络…...

编程日记 2025/8/16 12:13:16

C# backgroundworker类(后台线程)

概念在C#程序中，经常会有一些耗时较长的CPU密集型运算，如果直接在 UI 线程执行这样的运算就会出现UI不响应的问题。解决这类问题的主要途径是使用多线程，启动一个后台线程，把运算操作放在这个后台线程中完成。但是原生接口的线程…...

编程日记 2025/8/16 11:30:46

OpenAI智能体初探：使用 OpenAI Responses API 在 PDF 中实现检索增强生成（RAG）

大家好，我是大 F，深耕AI算法十余年，互联网大厂技术岗。知行合一，不写水文，喜欢可关注，分享AI算法干货、技术心得。欢迎关注《大模型理论和实战》、《DeepSeek技术解析和实战》，一起探索技术的无限可能！引子在信息爆炸的时代，从大量 PDF 文档中快速准确地检索信息…...

编程日记 2025/8/16 9:45:24

SqlServer数据库报错紧急或可疑无法访问的修复过程，亲测有效。

当 SQL Server 数据库被标记为 SUSPECT 状态时，表示数据库可能由于事务日志损坏、数据文件丢失或其他严重问题而无法正常启动。以下是一个详细的恢复步骤，基于搜索结果中的信息和常见的最佳实践： 恢复步骤 1. 确认数据库状态将database-n…...

编程日记 2025/8/18 1:35:01

12.31[net]review

复用（Multiplexing）的概念定义：在传输层，复用是指多个应用进程可以使用同一个传输层协议（如 TCP 或 UDP）来发送数据。从应用层的角度看，不同的应用进程（如网页浏览器、邮件客户端等…...

编程日记 2025/8/16 9:50:12

Redis超高并发分key实现

Redis扛并发的能力是非常强的，所以高并发场景下经常会使用Redis，但是Redis单分片的写入瓶颈在2w左右，读瓶颈在10w左右，如果在超高并发下即使是集群部署Redis，单分片的Redis也是有可能扛不住的，如下图所示&a…...

编程日记 2025/8/16 9:51:21

Houdini学习笔记

1. Houdini中一次只能显示一个物体如果要都显示需要 merge 节点粉色的是以参考显示 2.对任意一个节点按F1 可以弹出houdini官方文档 3. 恢复视角 Space H,居中 Space G 居中选中物体...

编程日记 2025/8/16 11:54:49

Ubuntu 22.04使用pigz多线程快速解压/压缩文件

最近搞项目，资料太大，解压时间太久，于是想办法解决。开贴记录。 1.安装pigz sudo apt install pigz 2.解压资料解压命令为 tar --use-compress-programpigz -xvpf ***.tar.gz 将最后的部分***.tar.gz换成你自己的文件即可例如 ti…...

编程日记 2025/8/16 12:56:32

子数组问题——动态规划

个人主页：敲上瘾-CSDN博客动态规划基础dp：基础dp——动态规划-CSDN博客多状态dp：多状态dp——动态规划-CSDN博客目录一、解题技巧二、最大子数组和三、乘积最大子数组四、最长湍流子数组五、单词拆分一、解题技巧区分子数组&…...

编程日记 2025/8/16 11:18:46

汉桑科技IPO：潜藏两大风险公众投资者权益或受损

冰山之所以危险，是因为只有八分之一在水面上。 ——语出小说家海明威。引言野村证券提供的一份报告显示，2025年前两个月，我国出口同比增长仅有2.3%，与去年四季度9.9%的增长显著下滑。与此同时，从2月1日开始&a…...

编程日记 2025/8/16 11:31:18

【3DGS】SuperSplat本地运行+修改监听端口+导入ply模型+修剪模型+在线渲染3DGS网站推荐

SuperSplat官网代码：https://github.com/playcanvas/supersplat 本地安装和运行 Clone the repository: git clone https://github.com/playcanvas/supersplat.git cd supersplat Install dependencies: npm install Build SuperSplat and start a local web ser…...

编程日记 2025/8/16 11:21:24

整数与字节序列相互转换

以下函数是用于二进制编解码的核心工具函数，实现 32/64 位整数与字节流之间的高效转换。操作逻辑：将整数的每个字节依次写入缓冲区，从最低有效字节到最高有效字节内存布局：假设 value0x12345678，地址由低到高依次是0…...

编程日记 2025/8/16 9:52:38

嵌入式软件测试的东方智慧：WinAMS工具的技术哲学与实践启示——一名汽车电子工程师的七年工具演进观察

引言：在丰田精益生产线上诞生的测试哲学 2017年参与某日系车企的ECU（电子控制单元）联合开发时，我第一次在名古屋工厂见到产线旁部署的WinAMS测试站。不同于欧美工具强调的“全流程覆盖”，这个诞生于日本制造业精益文化…...

编程日记 2025/8/15 19:44:22

卫星遥感赋能气象服务：精准预测，智享生活

卫星遥感技术作为现代气象服务的“千里眼”和“顺风耳”，正以前所未有的精度和效率，革新着我们对天气的观测、预报与应对方式。今天，就让我们一同探索卫星遥感在气象服务中的奇妙应用。星图云开放平台：专业气象的智慧之选高精度…...

编程日记 2025/8/15 23:03:34

多个nodejs版本切换使用教程

想要多个nodejs版本来回切换TOC 先卸载本地已安装的nodejs下载安装nvm ,下载地址：https://github.com/coreybutler/nvm-windows/releases打开链接后 ，选择 nvm-setup.exe 安装，安装路径避免空格和中文（如 D:\nvm） 选择…...

编程日记 2025/8/17 16:13:48

Vue.js 3 的设计思路：从声明式UI到高效渲染机制

目录一、声明式UI与虚拟DOM的灵活性二、渲染器：虚拟DOM到真实DOM的桥梁三、组件的本质与实现四、编译与运行时的协同优化五、性能与可维护性的权衡总结 Vue.js 3 作为新一代前端框架，其设计理念在声明式UI描述、虚拟DOM优化、组件化架构…...

编程日记 2025/8/16 12:03:43

Python控制语句 ——break和continue

1.以下关于Python循环结构的描述中,错误的是() 。 A、break用来结束当前当次语句，但不跳出当前的循环体。 B、遍历循环中的遍历结构可以是字符串、文件、组合数据类型和range函数等。 C、Python通过for，while等保留字构建循环结构。 D、continue只结束本次循环。答案：A。在…...

编程日记 2025/8/17 13:00:36

Linux websocket服务器、配网方法、QT客户端程序

一、linux websocket服务器参考下面的代码编译和运行 websocket_for_linux: c语言实验websocket通信，含服务端和客户端示例代码二、网络配置 Linux本地开启server和client，可正常通信。换局域网另外一台PC后无法测试通过。解决办法：…...

编程日记 2025/8/16 11:26:38

Python网络爬虫之requests库的使用方法

requests库是Python中用于发送HTTP请求的一个重要库，在实际应用中，它被广泛用于爬取网页数据、调用API接口等。本节将详细讲解requests库的使用流程，包括发送HTTP请求、携带请求参数、处理服务器响应以及错误处理，帮助读者掌握requests库的基本使用方法。 1. 使用requests库…...

编程日记 2025/8/16 12:17:31

一、初识Docker【安装基础案例】

开始学习docker容器技术，本文介绍如何安装docker、基本概念和一个简单的容器案例。 1. 安装docker 1.1 yum源方式安装 # step 1: 安装必要的一些系统工具 sudo yum install -y yum-utils# Step 2: 添加软件源信息 yum-config-manager --add-repo <https://mir…...

编程日记 2025/8/16 11:17:16

stm32 f4 flash 调用时卡死

【HAL库】STM32F407----内部Flash的读写_stm32f407 flash-CSDN博客参照此博客，如果调用flash 卡死的原因是谢日adress不准确，得到0x08010000 成功运行...

编程日记 2025/8/16 12:48:10

uv pip install -r requirements.txt-报错，python版本过低

升级Python版本（推荐） browser-use0.1.40 需要 Python ≥3.11，但你的环境是 Python 3.10.12。升级Python版本是最直接的解决方案： 安装Python 3.11： 使用 pyenv（Linux/macOS）：pyenv…...

编程日记 2025/8/17 14:37:09

c++ 中的float和double 的区别开发过程中使用哪个更好

在 C 中，float 和 double 都是用于表示浮点数的数据类型，但它们在精度、存储空间和性能方面有所不同。 1. float 和 double 的主要区别特性floatdouble占用内存4 字节（32 位）8 字节（64 位）精度约 6-7 位有…...

编程日记 2025/8/16 12:02:07

工厂模式加策略模式 -- 具体实现

这里写目录标题定义接口定义抽象类定义主处理器分支处理器定义工厂demo 定义接口 public interface EntityHandler extends InitializingBean {MatchContentDTO match(MatchEntityDTO matchEntityDTO);String supportEntityType(); }定义抽象类 public abstract class Abstr…...

编程日记 2025/8/16 12:59:59

Redis7——进阶篇（五）

前言：此篇文章系本人学习过程中记录下来的笔记，里面难免会有不少欠缺的地方，诚心期待大家多多给予指教。基础篇： Redis（一）Redis（二）Redis（三）Redis&#x…...

编程日记 2025/8/16 9:53:13

什么是全栈？

🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点下班 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 📃文章前言 🔷文章均为学习工…...

编程日记 2025/8/16 11:22:18

vue3实现虚拟滚动Vue-Virtual-Scroller

前端优化不可不避的一谈之虚拟滚动：众所周知，滚动是直挺挺的往dom树加东西，如果滚太多滚到万级，渲染过多就会卡顿，而vue-virtual-scroll的灵活懒渲染就能解决这个问题 1，下载与配置 npm install --save v…...

编程日记 2025/8/16 11:47:28

Flutter Dart 运算符全面解析

引言在 Dart 语言中，运算符是用于执行各种操作的特殊符号。这些操作可以是算术运算、逻辑运算、比较运算等。了解并熟练运用这些运算符是进行 Flutter 开发的基础。本文将详细介绍 Dart 中常见的运算符，并结合代码示例进行说明。 1. 算术运算符算术…...

编程日记 2025/8/16 11:24:41

XXE-labs靶场通关攻略

1.把相关压缩包放到www根目录下 2.解压，并且把php_xxe放在www目录下 3.进行访问发现是登陆页面 4.随便试试账号密码进行抓包 5.发送到重放器，发现username是回显点 6.可以利用xxe漏洞 <?xml version"1.0"?> //xml声明不重要&#x…...

编程日记 2025/8/18 2:02:57

Redis 主从复制详解：实现高可用与数据备份

目录引言 1. 什么是 Redis 主从复制？ 1.1 定义 1.2 核心概念 2. Redis 主从复制的工作原理 2.1 复制流程 2.2 复制流程图 3. Redis 主从复制的配置方法 3.1 通过配置文件配置主节点配置从节点配置 3.2 通过命令行配置设置从节点取消从节点 4. Re…...

编程日记 2025/8/16 11:56:56