C++ --红黑树

发布时间：2026/10/14 6:41:19

C++ --红黑树
红黑树的五大性质每个节点是红色或黑色根节点是黑色所有叶子NIL空节点都是黑色红色节点的两个子节点都是黑色即不能有连续的红节点从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点黑色高度一致节点定义与辅助函数#include iostream using namespace std; enum Color { RED, BLACK }; templatetypename Key, typename Value struct RBNode { Key key; Value value; Color color; RBNode* left; RBNode* right; RBNode* parent; RBNode(Key k, Value v, Color c RED) : key(k), value(v), color(c), left(nullptr), right(nullptr), parent(nullptr) {} };辅助函数// 判断节点颜色空节点视为黑色 templatetypename Key, typename Value bool isRed(RBNodeKey, Value* node) { return node ! nullptr node-color RED; } // 左旋 templatetypename Key, typename Value void leftRotate(RBNodeKey, Value* root, RBNodeKey, Value* x) { RBNodeKey, Value* y x-right; x-right y-left; if (y-left) y-left-parent x; y-parent x-parent; if (!x-parent) root y; else if (x x-parent-left) x-parent-left y; else x-parent-right y; y-left x; x-parent y; } // 右旋对称 templatetypename Key, typename Value void rightRotate(RBNodeKey, Value* root, RBNodeKey, Value* y) { RBNodeKey, Value* x y-left; y-left x-right; if (x-right) x-right-parent y; x-parent y-parent; if (!y-parent) root x; else if (y y-parent-left) y-parent-left x; else y-parent-right x; x-right y; y-parent x; }旋转的具体步骤插入前的核心认知1为什么新节点必须是红色核心原因如果插入黑色节点会立即违反性质5黑色高度一致因为这条路径多了一个黑色节点修复起来需要调整整棵树。而插入红色节点只可能违反性质4不能有连续红节点这种冲突是局部的可以通过旋转和变色在有限范围内修复。插入操作的两阶段阶段操作复杂度阶段1标准BST插入找到位置挂载新红节点O(log n)阶段2修复红黑性质处理连续红冲突O(log n) 但旋转次数≤2阶段1标准BST插入templatetypename Key, typename Value void insert(RBNodeKey, Value* root, Key key, Value value) { // 步骤1创建新节点红色 RBNodeKey, Value* z new RBNodeKey, Value(key, value, RED); // 步骤2BST查找插入位置 RBNodeKey, Value* y nullptr; // y最终指向z的父节点 RBNodeKey, Value* x root; // x是游标指针 while (x ! nullptr) { y x; // 记录父节点 if (key x-key) x x-left; else if (key x-key) x x-right; else { // 键已存在更新值释放新节点 x-value value; delete z; return; } } // 步骤3挂载新节点 z-parent y; if (y nullptr) { root z; // 树为空新节点就是根 } else if (key y-key) { y-left z; } else { y-right z; } // 步骤4修复红黑性质 insertFixup(root, z); }细节解读y指针记录当前节点的父节点如果树为空新节点直接成为根但根必须是黑色修复阶段会处理。如果键已存在我们直接更新值并返回不进行任何颜色修复。阶段2插入修复修复的触发条件只有一种情况需要修复父节点是红色因为新节点也是红色形成连续红。如果父节点是黑色树已经满足所有红黑性质无需任何操作。修复的总体策略while (父节点是红色) { 判断父节点是祖父的左孩子还是右孩子对称处理 获取叔叔节点的颜色 if (叔叔是红色) { 处理情况1颜色翻转 } else { // 叔叔是黑色或null if (当前节点是父节点的内侧孩子) { 处理情况2旋转父节点转换为情况3 } 处理情况3旋转祖父节点 变色 } } 最后确保根是黑色三种情况详解假设父节点是祖父的左孩子情况1叔叔是红色G(黑) G(红) / \ ---- / \ P(红) U(红) P(黑) U(黑) / / z(红) z(红)操作将父节点P设为黑色将叔叔U设为黑色将祖父G设为红色为了保持黑色高度将z指针上移到G继续循环检查为什么这样做有效局部黑色高度不变原来路径G-P-z有1个黑G现在G-P有1个黑PG-U有1个黑U黑色高度保持。但祖父变红后可能与其父节点形成连续红所以需要继续向上检查。代码实现if (isRed(y)) { // y是叔叔节点 z-parent-color BLACK; y-color BLACK; z-parent-parent-color RED; z z-parent-parent; // 上移两层 }情况2叔叔是黑色叔叔节点为空也默认是黑色NIL且z是父节点的右孩子内侧情况G(黑) G(黑) / / P(红) z(红) \ / z(红) P(红)操作将z指向父节点P对z进行左旋为什么要旋转当前z是右孩子属于内侧插入直接右旋祖父会让z跑到左边但结构不对称。通过左旋父节点将情况转化为情况3z变成左孩子即外侧情况。注意旋转后颜色不变因为还没完成修复代码实现if (z z-parent-right) { z z-parent; leftRotate(root, z); }情况3叔叔是黑色且z是父节点的左孩子外侧情况G(黑) P(黑) / / \ P(红) z(红) G(红) / z(红)操作将父节点P设为黑色将祖父G设为红色对祖父G进行右旋为什么这样做有效旋转后P成为新的子树根G变成P的右孩子。P原来是红色现在变黑保证不会与上层形成连续红。G原来是黑色现在变红但它的左右子树黑色高度保持不变。黑色高度验证原路径z→P→G黑色节点数 1只有G新路径z→P→G黑色节点数 1只有P代码实现z-parent-color BLACK; z-parent-parent-color RED; rightRotate(root, z-parent-parent); // 旋转后循环可以结束因为z的父节点已变黑对称情况父节点是祖父的右孩子完全对称只需将左和右互换else { // 父节点是祖父的右孩子 RBNodeKey, Value* y z-parent-parent-left; // 叔叔在左 if (isRed(y)) { // 情况1对称 z-parent-color BLACK; y-color BLACK; z-parent-parent-color RED; z z-parent-parent; } else { if (z z-parent-left) { // 情况2对称z是左孩子 z z-parent; rightRotate(root, z); } // 情况3对称 z-parent-color BLACK; z-parent-parent-color RED; leftRotate(root, z-parent-parent); } }完整插入修复流程图开始插入新节点为红色 ↓ 父节点是红色 ↓ 是 祖父存在且叔叔是红色 ↓ 是 ↓ 否 情况1颜色翻转 叔叔是黑色 ↓ ↓ z上移到祖父 z是父节点的内侧孩子 继续循环 ↓ 是 ↓ 否 情况2旋转父节点 情况3旋转祖父变色 ↓ ↓ 转换为情况3 修复完成退出循环 ↓ 情况3旋转祖父变色 ↓ 修复完成退出循环 ↓ 确保根为黑色 ↓ 结束复杂度和性能分析指标值说明时间O(log n)BST查找O(log n) 修复最多O(log n)旋转次数≤2次情况3后退出情况2转情况3也算1次颜色翻转次数≤O(log n)可能一直上移到根空间O(1)只使用了几个指针变量为什么旋转最多2次情况1颜色翻转不会旋转但可能向上传播情况2旋转父节点后必然进入情况3情况3旋转祖父节点后必然退出循环所以最多2次旋转情况2情况3各一次完整的insertFixup代码templatetypename Key, typename Value void insertFixup(RBNodeKey, Value* root, RBNodeKey, Value* z) { // 只要父节点是红色就需要修复 while (z ! root isRed(z-parent)) { // 分支A父节点是祖父的左孩子 if (z-parent z-parent-parent-left) { RBNodeKey, Value* uncle z-parent-parent-right; // ★情况1叔叔是红色 → 颜色翻转 if (isRed(uncle)) { z-parent-color BLACK; uncle-color BLACK; z-parent-parent-color RED; z z-parent-parent; // 上移两层继续检查 } else { // ★情况2z是右孩子内侧→ 左旋父节点 if (z z-parent-right) { z z-parent; leftRotate(root, z); } // ★情况3z是左孩子外侧→ 右旋祖父 变色 z-parent-color BLACK; z-parent-parent-color RED; rightRotate(root, z-parent-parent); // 此时父节点已变黑循环必然结束 } } else { // 分支B父节点是祖父的右孩子完全对称 RBNodeKey, Value* uncle z-parent-parent-left; if (isRed(uncle)) { z-parent-color BLACK; uncle-color BLACK; z-parent-parent-color RED; z z-parent-parent; } else { if (z z-parent-left) { // 内侧右孩子的左孩子 z z-parent; rightRotate(root, z); } z-parent-color BLACK; z-parent-parent-color RED; leftRotate(root, z-parent-parent); } } } // 保证根永远是黑色处理情况1传播到根的情况 root-color BLACK; }总结插入操作的思维导图红黑树插入├── 阶段1BST插入│ ├── 查找位置y记录父节点│ ├── 挂载新节点红色│ └── 更新父指针│└── 阶段2修复while父为红├── 父是祖父左孩子│ ├── 叔红 → 翻转颜色上移│ └── 叔黑│ ├── z是右孩子 → 左旋父转情况3│ └── z是左孩子 → 右旋祖父变色结束│└── 父是祖父右孩子对称├── 叔红 → 翻转颜色上移└── 叔黑├── z是左孩子 → 右旋父转情况3└── z是右孩子 → 左旋祖父变色结束最后根变黑强制

相关新闻

【AI需求预测分析黄金法则】：20年实战总结的5大避坑指南与实时优化框架

【AI需求预测分析黄金法则】：20年实战总结的5大避坑指南与实时优化框架

更多请点击： https://intelliparadigm.com 第一章：AI需求预测分析黄金法则的底层逻辑 AI需求预测并非单纯依赖历史数据拟合，其本质是构建“业务动因—数据表征—模型响应”的闭环因果链。脱离业务语义的数据驱动建模，极易陷入过拟…

2026/10/14 6:41:06 阅读更多 →
Python分支结构实战：从if-else到编程决策思维

Python分支结构实战：从if-else到编程决策思维

1. 项目概述：从“头哥”平台看Python分支结构的实战价值最近在“头哥”这个编程实践平台上，看到不少朋友在攻克实验二——分支结构程序设计。这让我想起了自己刚学Python那会儿，面对if-elif-else时那种既熟悉又有点无从下手的感觉。熟悉是因为…

2026/10/10 10:35:02 阅读更多 →
AI制度文档编写进入“强监管倒计时”：2024Q3起未通过AI治理文档合规性审查=项目自动终止

AI制度文档编写进入“强监管倒计时”：2024Q3起未通过AI治理文档合规性审查=项目自动终止

更多请点击： https://kaifayun.com 第一章：AI制度文档编写的时代背景与强监管逻辑 人工智能技术正以前所未有的速度渗透至金融、医疗、政务、教育等关键领域，其自主决策能力与规模化部署能力在提升效率的同时，也显著放大了算法偏…

2026/9/28 5:43:57 阅读更多 →

最新新闻

C#调用WebService获取PDF转图片：选型与踩坑实战

C#调用WebService获取PDF转图片：选型与踩坑实战

做C#开发这几年，遇到“调用WebService获取PDF文件再转换为图片”这种需求不算少。可能是一个审批系统需要预览合同，也可能是一个报表平台需要把服务端生成的文件转成缩略图展示。总之核心工作就两件事：把远程文件拿下来，再在本地转…

2026/10/14 6:40:29 阅读更多 →
Unity Spark实战：在浏览器中用AI自然语言快速做游戏原型

Unity Spark实战：在浏览器中用AI自然语言快速做游戏原型

看到“Unity Spark 正式发布”这条消息的时候，我第一反应是：又来了。这年头但凡和 AI 沾边的工具都在喊“原生支持 AI”，口号早就被用烂了。但等我真正在浏览器里打开这个基于 AI 的游戏开发环境，亲手生成一个场景、跑通一次跳跃、…

2026/10/14 6:40:29 阅读更多 →
仓颉语言属性（prop）完全指南：getter/setter 定义、抽象属性与继承覆盖实战

仓颉语言属性（prop）完全指南：getter/setter 定义、抽象属性与继承覆盖实战

文档编程语言 【免费下载链接】cangjie_docs 仓颉编程语言开发者文档。 项目地址： https://gitcode.com/Cangjie/cangjie_docs 点击查看 免费下载 属性（Properties）是仓颉语言中用于间接获取和设置值的语言机制：它通过一个 gette…

2026/10/14 6:40:29 阅读更多 →
从Node到Bun：JavaScript运行时与工具链的工程效率革命

从Node到Bun：JavaScript运行时与工具链的工程效率革命

1. 为什么我把重心从 Node 切到了 Bun先说结论：Bun 不是又一个跑得更快的 Node，它是一整套重新设计过的 JavaScript 运行时和工具链。我最初对它的态度是观望，因为这类"下一代运行时"的宣发见过太多次了，但真正在几个中…

2026/10/14 6:40:29 阅读更多 →
C#对接WebService拉取PDF并转图片：从接口调到部署避坑

C#对接WebService拉取PDF并转图片：从接口调到部署避坑

前一阵接手一个对接任务，对方是个运行了十多年的老系统，只对外暴露SOAP风格的WebService接口。业务要求很直接：通过这个接口把PDF文件拉到我们这边，再转成图片，放到Web端做在线预览和打印存档。这类需求在C#开发里非常…

2026/10/14 6:40:29 阅读更多 →
纯Python实现猜数字游戏：从零到避坑的完整指南

纯Python实现猜数字游戏：从零到避坑的完整指南

猜数字游戏大概是很多人的第一个编程项目。它不像计算器那样枯燥，也不需要复杂的界面，但一套完整流程走下来，变量、输入输出、条件判断、循环、异常处理这些编程入门核心概念全部能练到。我最近又把这个小项目从头写了一遍，用最基…

2026/10/14 6:39:29 阅读更多 →

日新闻

AnyPS5通用适配层设计：兼容性与性能的工程取舍

AnyPS5通用适配层设计：兼容性与性能的工程取舍

1. 从"AnyPS5"这个名字说起：它到底想解决什么问题第一次看到"AnyPS5"这个标题，我脑子里冒出来的第一个念头是：这大概率是一个围绕"跨平台运行"或者"通用适配"做文章的项目。名字里的"Any"…

2026/10/14 0:00:41 阅读更多 →
Flutter跨平台开发实战：二手交易应用与HarmonyOS适配

Flutter跨平台开发实战：二手交易应用与HarmonyOS适配

1. 项目概述：Flutter跨平台二手交易应用开发作为一名长期从事移动应用开发的工程师，我最近完成了一个基于Flutter框架的二手物品交易平台项目。这个项目最吸引我的地方在于它完美结合了Flutter的跨平台优势与HarmonyOS的生态特性，实现了"…

2026/10/14 0:00:41 阅读更多 →
DFS算法解决飞机降落调度问题实战

DFS算法解决飞机降落调度问题实战

1. 项目背景与核心思路飞机降落问题是一个经典的调度优化场景，也是算法竞赛和面试中的高频题目。这个题目要求我们合理安排多架飞机的降落顺序和时间，确保所有飞机都能安全着陆而不发生冲突。在实际航空管制中，这类问题直接关系到飞行安全和机…

2026/10/14 0:00:41 阅读更多 →

周新闻

流感时间序列预测实战：ARIMA/LSTM全流程拆解与避坑指南

流感时间序列预测实战：ARIMA/LSTM全流程拆解与避坑指南

简介：基于 ARIMA、LSTM、Transformer 等模型的流感时间序列预测 Python 源码，面向计算机相关专业课程设计与期末大作业学生，以及项目实战学习者。内容覆盖预处理、平稳性检验、定阶、残差分析、多模型对比预测的完整时序建模流程，…

2026/10/14 3:30:28 阅读更多 →
影刀RPA新手教程：键盘模拟输入实战——输入文本与模拟按键的区别

影刀RPA新手教程：键盘模拟输入实战——输入文本与模拟按键的区别

影刀RPA新手教程：键盘模拟输入实战——输入文本与模拟按键的区别 做影刀RPA自动化，十个新手有八个栽在"往输入框里填东西"这件事上：要么填不进去，要么填了一半，要么直接把原来内容追加在后面。这背后的根因&…

2026/10/13 16:22:04 阅读更多 →
影刀RPA新手教程：阅文起点小说数据采集实战——书籍信息与章节内容

影刀RPA新手教程：阅文起点小说数据采集实战——书籍信息与章节内容

影刀RPA新手教程：阅文起点小说数据采集实战——书籍信息与章节内容 1. 认识影刀：什么场景该用RPA采小说数据 起点中文网的页面结构相对稳定——分类榜单、书籍详情、章节内容三块独立页面，跳转链路清晰。这种场景非常适合影刀自动化&#x…

2026/10/14 3:29:58 阅读更多 →

月新闻

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/10/13 22:01:27 阅读更多 →
Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/10/13 14:57:39 阅读更多 →
黑夜航拍船只数据集训练YOLOV5模型全流程解析

黑夜航拍船只数据集训练YOLOV5模型全流程解析

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/10/12 18:11:17 阅读更多 →