定位适配高校期末考核、考研数据结构、互联网秋招底层手撕代码标准核心特点内容无删减、逻辑无跳步、严格遵循学术定义实现原理与底层代码一一对应。精准贴合考情完整实现秋招必考的旋转、插入、变色底层源码删除模块仅讲解核心思路不实现底层代码。本文为纯手写红黑树底层教程与STL map上层调用完全区分是吃透C map底层内核的核心资料。前置关键区分必看此前的Map教程为【STL容器上层API调用】本文档为【从零手写红黑树底层数据结构】完整实现节点定义、染色机制、旋转平衡、插入修复核心逻辑是Map/Set容器的底层核心原理。一、红黑树前置认知 为什么替代AVL树1.1 平衡树家族对比AVL树是严格平衡二叉树要求左右子树高度差严格不超过1平衡精度极高但插入、删除操作极易触发失衡需要频繁旋转调整数据修改效率较低。红黑树是弱平衡二叉搜索树不追求绝对高度平衡通过一套严格的颜色约束规则限制树的最长路径与最短路径比例大幅减少旋转次数插入、删除的整体效率显著优于AVL树。工业级应用结论面试常考频繁增删场景优先使用红黑树频繁查询场景优先使用AVL树。C map/set、Java TreeMap、Linux内核进程调度均采用红黑树作为底层数据结构。1.2 红黑树核心定位红黑树本质是基于颜色约束实现自平衡的二叉搜索树所有子树依然满足BST规则左子树值 根 右子树值其平衡机制不依赖节点高度差而是依靠五大核心性质强制约束树结构保证最长路径长度不超过最短路径的2倍稳定维持O(logn)时间复杂度。二、红黑树五大硬性性质以下五条为标准学术定义是期末考试、作业作答、面试口述的标准答案需精准记忆。性质1每个节点只能是黑色 或 红色。性质2根节点必须是黑色。性质3所有叶子节点空节点NIL均为黑色。性质4不存在连续两个红色节点红节点的孩子一定是黑节点。性质5从任意节点出发到达其所有叶子节点的路径上黑色节点数量相等黑高一致。2.1 五大性质核心推论最短路径全黑色节点最长路径红黑交替节点最长路径长度 ≤ 2 × 最短路径长度整树高度稳定在 O(logn)不会退化斜链三、红黑树核心基础概念3.1 节点颜色定义标准枚举定义RED红色、BLACK黑色3.2 NIL 虚拟叶子节点重点难点红黑树摒弃普通BST的空指针判定将所有空叶子统一替换为黑色NIL虚拟节点。核心作用统一所有边界判断逻辑严格保证黑高一致的性质成立3.3 失衡修复两大手段红黑树不依赖高度平衡仅靠两种操作修复所有违规变色修改节点红/黑颜色修复红节点连续、黑高不一致问题旋转左旋、右旋调整树结构不破坏BST规则四、基础工具模块完整手写逐行注释本节包含颜色枚举、节点结构体、全局NIL节点、构造函数、析构函数、高度获取、基础旋转全部为底层核心依赖无任何上层封装。#include iostream using namespace std; // 红黑树节点颜色枚举 严格标准定义 enum Color { RED, // 红色节点 BLACK // 黑色节点 }; /** * brief 红黑树节点结构体 * param val 节点存储数据 * param color 节点颜色 * param left/right 左右孩子指针 * param parent 父节点指针红黑树必备用于回溯祖父、叔叔节点 */ struct RBNode { int val; Color color; RBNode* left; RBNode* right; RBNode* parent; // 节点构造函数新节点默认红色 RBNode(int v) : val(v), color(RED), left(nullptr), right(nullptr), parent(nullptr) {} }; // 全局唯一NIL黑色虚拟叶子节点统一边界、保证黑高规则成立 RBNode* NIL new RBNode(0); /** * brief 红黑树类 * note 仅实现【面试必考】插入全套底层逻辑 * note 删除仅讲原理无底层代码 */ class RBTree { private: RBNode* root; // 整树根节点 /** * brief 获取节点颜色兼容NIL空节点 * param node 目标节点 * return 节点颜色空节点统一返回黑色 */ Color getColor(RBNode* node) { return node NIL ? BLACK : node-color; } /** * brief 修改节点颜色过滤NIL空节点 * param node 目标节点 * param c 目标颜色 */ void setColor(RBNode* node, Color c) { if (node ! NIL) node-color c; } /** * brief 红黑树左旋操作 * param x 旋转基准节点 * note 仅调整树结构不修改颜色、不破坏BST性质 */ void leftRotate(RBNode* x) { // y为x的右孩子 RBNode* y x-right; // y的左子树挂载到x的右子树 x-right y-left; // 非空子树更新父节点 if (y-left ! NIL) y-left-parent x; // y继承x的父节点关系 y-parent x-parent; // 若x是根节点y升级为新根 if (x-parent nullptr) root y; // 若x是父节点左孩子 else if (x x-parent-left) x-parent-left y; // 若x是父节点右孩子 else x-parent-right y; // x成为y的左孩子 y-left x; x-parent y; } /** * brief 红黑树右旋操作 * param y 旋转基准节点 * note 仅调整树结构不修改颜色、不破坏BST性质 */ void rightRotate(RBNode* y) { // x为y的左孩子 RBNode* x y-left; // x的右子树挂载到y的左子树 y-left x-right; // 非空子树更新父节点 if (x-right ! NIL) x-right-parent y; // x继承y的父节点关系 x-parent y-parent; // 若y是根节点x升级为新根 if (y-parent nullptr) root x; else if (y y-parent-left) y-parent-left x; else y-parent-right x; // y成为x的右孩子 x-right y; y-parent x; } /** * brief 插入后红黑树平衡与颜色修复函数 * param cur 新插入的节点 * note 唯一违规场景父节点为红色出现连续红节点 * note 修复手段变色、左旋、右旋、向上回溯 */ void insertFix(RBNode* cur) { // 父节点为红色才存在违规 while (getColor(cur-parent) RED) { // 情况一父节点是祖父节点的左孩子 if (cur-parent cur-parent-parent-left) { RBNode* p cur-parent; // 父节点 RBNode* g p-parent; // 祖父节点 RBNode* u g-right; // 叔叔节点 // 场景1叔叔为红色 —— 纯变色修复 if (getColor(u) RED) { setColor(p, BLACK); // 父变黑 setColor(u, BLACK); // 叔叔变黑 setColor(g, RED); // 祖父变红 cur g; // 向上回溯继续修复 } else { // 场景2叔叔黑、cur是右孩子LR交叉失衡 // 先左旋转为LL直线失衡 if (cur p-right) { cur p; leftRotate(cur); } // 场景3叔叔黑、cur是左孩子LL直线失衡 setColor(p, BLACK); setColor(g, RED); rightRotate(g); } } // 情况二父节点是祖父节点的右孩子镜像对称 else { RBNode* p cur-parent; RBNode* g p-parent; RBNode* u g-left; // 场景1镜像叔叔红色 if (getColor(u) RED) { setColor(p, BLACK); setColor(u, BLACK); setColor(g, RED); cur g; } else { // 场景2镜像RL交叉失衡先右旋转RR if (cur p-left) { cur p; rightRotate(cur); } // 场景3镜像RR直线失衡 setColor(p, BLACK); setColor(g, RED); leftRotate(g); } } } // 强制根节点为黑色满足性质2 setColor(root, BLACK); } /** * brief BST底层插入逻辑 * param val 待插入数值 * note 新节点默认红色插入最小化平衡代价 */ void insert(int val) { // 新建节点默认红色绑定NIL虚拟叶子 RBNode* newNode new RBNode(val); newNode-left NIL; newNode-right NIL; // 空树直接初始化根节点 if (root nullptr) { root newNode; root-color BLACK; return; } // 非空树遍历寻找插入位置 RBNode* cur root; RBNode* pre nullptr; while (cur ! NIL) { pre cur; if (val cur-val) cur cur-left; else cur cur-right; } // 挂载新节点建立父子关系 newNode-parent pre; if (val pre-val) pre-left newNode; else pre-right newNode; // 插入完成启动平衡修复 insertFix(newNode); } /** * brief 中序遍历 BST升序输出 * param node 遍历起始节点 */ void inOrder(RBNode* node) { if (node NIL) return; inOrder(node-left); cout node-val ; inOrder(node-right); } /** * brief 后序递归销毁整树防止内存泄漏 * param node 销毁起始节点 */ void destroy(RBNode* node) { if (node NIL) return; destroy(node-left); destroy(node-right); delete node; } public: // 构造函数初始化空树 RBTree() { root nullptr; } // 析构函数释放所有节点内存 ~RBTree() { destroy(root); } // 对外公开插入接口 void insertVal(int val) { insert(val); } // 对外公开遍历接口打印有序序列 void printTree() { inOrder(root); cout endl; } };五、红黑树插入机制全解析红黑树插入是秋招、期末唯一要求手撕的核心代码旋转、变色、回溯逻辑必须完整掌握。本节补齐全套完整插入源码包含BST插入底层逻辑、insertFix平衡修复逻辑逐行超详细注释零省略、零跳转。5.1 插入核心前置原理新节点默认红色插入。核心原因若插入黑色节点会直接破坏整树黑高统一性质性质5需要全局修复代价极大若插入红色节点仅可能破坏无连续红节点性质4仅需局部变色旋转修复是最优插入策略。插入失衡四大核心角色cur当前失衡节点、p父节点、g祖父节点、u叔叔节点。5.2 插入失衡三大标准场景统一前置条件插入后父节点p为红色触发连续红色违规根据红黑树合法规则祖父节点g一定为黑色。场景一叔叔节点为红色纯变色修复无旋转结构特征父红、叔叔红、祖父黑修复逻辑父节点、叔叔节点染黑祖父节点染红当前节点回溯至祖父节点向上迭代修复上层失衡。特点无需旋转仅变色即可修复局部失衡。场景二叔叔黑色、交叉失衡LR / RL 先旋转矫正结构LR交叉父为祖父左孩子、cur为父右孩子、叔叔黑 → 左旋父节点转为LL直线失衡RL交叉父为祖父右孩子、cur为父左孩子、叔叔黑 → 右旋父节点转为RR直线失衡场景三叔叔黑色、直线失衡LL / RR 旋转变色终结修复LL直线父左、cur左、叔叔黑 → 祖父染红、父染黑、右旋祖父修复完成无回溯RR直线父右、cur右、叔叔黑 → 祖父染红、父染黑、左旋祖父修复完成无回溯5.3 完整插入全套底层源码含BST插入 平衡修复以下为可直接编译的完整插入核心代码已整合进红黑树类注释全覆盖、逻辑无省略。/** * brief 底层BST插入逻辑 * param val 待插入节点数值 * note 1. 新节点默认红色左右孩子绑定全局NIL黑节点 * note 2. 单独处理空树场景根节点强制黑色 * note 3. 遍历寻找合法插入位置维护父子指针关系 * note 4. 插入完成后调用平衡修复函数恢复红黑树五大性质 */ void insert(int val) { // 实例化新节点默认红色初始绑定NIL虚拟叶子节点 RBNode* newNode new RBNode(val); newNode-left NIL; newNode-right NIL; // 特殊情况空树新节点直接作为根节点根必须为黑色 if (root nullptr) { root newNode; root-color BLACK; return; } // 非空树按照BST规则遍历寻找插入位置 RBNode* cur root; RBNode* pre nullptr; while (cur ! NIL) { pre cur; // 记录当前节点为父节点 if (val cur-val) // 小于当前节点往左子树走 cur cur-left; else // 大于等于当前节点往右子树走 cur cur-right; } // 挂载新节点建立父子双向指针关系 newNode-parent pre; if (val pre-val) pre-left newNode; else pre-right newNode; // 插入完成启动红黑树颜色与结构平衡修复 insertFix(newNode); } /** * brief 插入后红黑树自平衡修复函数 * param cur 新插入的失衡节点 * note 仅解决【连续红节点】违规问题 * note 修复手段变色、左旋、右旋、向上回溯迭代 */ void insertFix(RBNode* cur) { // 循环条件父节点为红色出现连续红节点触发违规 while (getColor(cur-parent) RED) { // 分支1父节点是祖父节点的左孩子左侧失衡体系 if (cur-parent cur-parent-parent-left) { RBNode* p cur-parent; // 定义父节点 RBNode* g p-parent; // 定义祖父节点 RBNode* u g-right; // 定义叔叔节点 // 场景1叔叔节点为红色 —— 纯变色修复 if (getColor(u) RED) { setColor(p, BLACK); // 父节点变黑消除连续红 setColor(u, BLACK); // 叔叔节点变黑 setColor(g, RED); // 祖父节点变红向上传递失衡 cur g; // 指针回溯至祖父继续向上校验 } else { // 场景2叔叔黑、当前节点为右孩子LR交叉失衡 // 先左旋父节点将交叉结构转为LL直线结构 if (cur p-right) { cur p; leftRotate(cur); } // 场景3叔叔黑、当前节点为左孩子LL直线失衡 // 变色右旋一次性终结修复 setColor(p, BLACK); setColor(g, RED); rightRotate(g); } } // 分支2父节点是祖父节点的右孩子右侧镜像失衡体系 else { RBNode* p cur-parent; RBNode* g p-parent; RBNode* u g-left; // 场景1镜像叔叔红色纯变色修复 if (getColor(u) RED) { setColor(p, BLACK); setColor(u, BLACK); setColor(g, RED); cur g; } else { // 场景2镜像RL交叉失衡先右旋转为RR直线 if (cur p-left) { cur p; rightRotate(cur); } // 场景3镜像RR直线失衡左旋变色终结修复 setColor(p, BLACK); setColor(g, RED); leftRotate(g); } } } // 强制根节点为黑色严格遵守红黑树性质2 setColor(root, BLACK); }5.4 插入代码核心逻辑总结1、先按照标准BST规则完成节点插入新节点默认红色2、判断是否出现连续红节点违规若父节点为黑色则无需修复3、根据叔叔节点颜色、当前节点位置区分三大场景4、纯变色场景向上回溯旋转场景直接终结修复5、最后强制根节点变黑保证五大性质全部成立。秋招/面试核心结论重点记忆红黑树删除底层源码极其复杂包含双重黑色消解、四套镜像场景、多层回溯修复常规秋招面试、期末考试均不要求手写删除底层代码仅需掌握核心思路即可。本文档不提供任何删除底层代码完全贴合面试考情。6.1 删除模块核心认知红黑树插入仅破坏「无连续红节点」规则修复简单而删除操作会直接破坏黑高一致性五大核心性质5产生「双重黑色节点」是红黑树最复杂的逻辑。删除整体执行流程仅理解思路无需写代码按照标准BST规则找到待删除节点区分叶子节点、单孩子节点、双孩子节点三种情况双孩子节点采用「后继节点替换法」用右子树最小节点覆盖待删除节点值再删除后继节点判断被删除节点颜色删除红色节点无任何影响无需修复删除黑色节点会产生双重黑色破坏整树黑高平衡通过兄弟节点、兄弟节点左右孩子的颜色组合匹配4种修复场景逐层向上消解双重黑色最终恢复红黑树五大性质。6.2 面试必背问答场景一叔叔节点为红色纯变色修复无需旋转结构特征父节点红、叔叔节点红、祖父节点黑修复逻辑父、叔叔节点染黑祖父节点染红随后将当前节点回溯至祖父节点向上继续校验平衡直到根节点。核心特点无需旋转仅变色即可修复局部失衡是最简单的插入失衡场景。场景二叔叔节点黑色、交叉失衡LR / RL先旋转再修复以左侧LR为例父节点是祖父左孩子、当前节点是父节点右孩子、叔叔节点黑色修复逻辑先对父节点左旋将交叉结构转换为直线结构LL场景再进入场景三修复。右侧RL镜像先对父节点右旋转换为RR直线结构。场景三叔叔节点黑色、直线失衡LL / RR旋转变色修复以左侧LL为例父节点是祖父左孩子、当前节点是父节点左孩子、叔叔节点黑色修复逻辑祖父节点染红父节点染黑对祖父节点右旋一次性修复所有失衡无需继续回溯。右侧RR镜像祖父染红、父节点染黑对祖父节点左旋修复。七、完整测试主函数int main() { // 实例化红黑树对象 RBTree tree; // 乱序测试数据验证自动排序、自动变色、自动旋转平衡 int arr[] {10, 20, 30, 15, 25, 5}; int n sizeof(arr) / sizeof(arr[0]); // 批量插入节点 for (int i 0; i n; i) { tree.insertVal(arr[i]); } // 中序遍历一定升序验证BST特性与平衡正确性 cout 红黑树插入完成 · 中序升序遍历结果 endl; tree.printTree(); return 0; }六、工具函数、测试代码与重难点总结8.1 插入核心考点必背根黑、叶黑、节点红黑二色、无连续红、任意路径黑高相等新节点默认红色插入代价最小8.2 插入修复三大场景答题模板叔叔红仅变色向上回溯叔叔黑、LR先左旋转LL再右旋变色叔叔黑、LL直接右旋变色8.3 删除考点总结删除核心难点删除黑色节点产生双重黑色破坏全局黑高一致性修复逻辑依靠兄弟节点、兄弟子节点颜色组合4种场景逐层消解双重黑色应试结论秋招面试、基础期末考核无需掌握删除底层代码仅需理解原理8.4 红黑树 vs AVL树AVL树严格平衡查询效率高增删旋转多、效率低红黑树弱平衡允许局部不平衡旋转少、增删效率高工业级首选
【彻底吃透C++红黑树 | 五大性质、变色旋转原理、完整手写实现、逐行注释、考点精讲
发布时间：2026/5/30 14:35:49
定位适配高校期末考核、考研数据结构、互联网秋招底层手撕代码标准核心特点内容无删减、逻辑无跳步、严格遵循学术定义实现原理与底层代码一一对应。精准贴合考情完整实现秋招必考的旋转、插入、变色底层源码删除模块仅讲解核心思路不实现底层代码。本文为纯手写红黑树底层教程与STL map上层调用完全区分是吃透C map底层内核的核心资料。前置关键区分必看此前的Map教程为【STL容器上层API调用】本文档为【从零手写红黑树底层数据结构】完整实现节点定义、染色机制、旋转平衡、插入修复核心逻辑是Map/Set容器的底层核心原理。一、红黑树前置认知 为什么替代AVL树1.1 平衡树家族对比AVL树是严格平衡二叉树要求左右子树高度差严格不超过1平衡精度极高但插入、删除操作极易触发失衡需要频繁旋转调整数据修改效率较低。红黑树是弱平衡二叉搜索树不追求绝对高度平衡通过一套严格的颜色约束规则限制树的最长路径与最短路径比例大幅减少旋转次数插入、删除的整体效率显著优于AVL树。工业级应用结论面试常考频繁增删场景优先使用红黑树频繁查询场景优先使用AVL树。C map/set、Java TreeMap、Linux内核进程调度均采用红黑树作为底层数据结构。1.2 红黑树核心定位红黑树本质是基于颜色约束实现自平衡的二叉搜索树所有子树依然满足BST规则左子树值 根 右子树值其平衡机制不依赖节点高度差而是依靠五大核心性质强制约束树结构保证最长路径长度不超过最短路径的2倍稳定维持O(logn)时间复杂度。二、红黑树五大硬性性质以下五条为标准学术定义是期末考试、作业作答、面试口述的标准答案需精准记忆。性质1每个节点只能是黑色 或 红色。性质2根节点必须是黑色。性质3所有叶子节点空节点NIL均为黑色。性质4不存在连续两个红色节点红节点的孩子一定是黑节点。性质5从任意节点出发到达其所有叶子节点的路径上黑色节点数量相等黑高一致。2.1 五大性质核心推论最短路径全黑色节点最长路径红黑交替节点最长路径长度 ≤ 2 × 最短路径长度整树高度稳定在 O(logn)不会退化斜链三、红黑树核心基础概念3.1 节点颜色定义标准枚举定义RED红色、BLACK黑色3.2 NIL 虚拟叶子节点重点难点红黑树摒弃普通BST的空指针判定将所有空叶子统一替换为黑色NIL虚拟节点。核心作用统一所有边界判断逻辑严格保证黑高一致的性质成立3.3 失衡修复两大手段红黑树不依赖高度平衡仅靠两种操作修复所有违规变色修改节点红/黑颜色修复红节点连续、黑高不一致问题旋转左旋、右旋调整树结构不破坏BST规则四、基础工具模块完整手写逐行注释本节包含颜色枚举、节点结构体、全局NIL节点、构造函数、析构函数、高度获取、基础旋转全部为底层核心依赖无任何上层封装。#include iostream using namespace std; // 红黑树节点颜色枚举 严格标准定义 enum Color { RED, // 红色节点 BLACK // 黑色节点 }; /** * brief 红黑树节点结构体 * param val 节点存储数据 * param color 节点颜色 * param left/right 左右孩子指针 * param parent 父节点指针红黑树必备用于回溯祖父、叔叔节点 */ struct RBNode { int val; Color color; RBNode* left; RBNode* right; RBNode* parent; // 节点构造函数新节点默认红色 RBNode(int v) : val(v), color(RED), left(nullptr), right(nullptr), parent(nullptr) {} }; // 全局唯一NIL黑色虚拟叶子节点统一边界、保证黑高规则成立 RBNode* NIL new RBNode(0); /** * brief 红黑树类 * note 仅实现【面试必考】插入全套底层逻辑 * note 删除仅讲原理无底层代码 */ class RBTree { private: RBNode* root; // 整树根节点 /** * brief 获取节点颜色兼容NIL空节点 * param node 目标节点 * return 节点颜色空节点统一返回黑色 */ Color getColor(RBNode* node) { return node NIL ? BLACK : node-color; } /** * brief 修改节点颜色过滤NIL空节点 * param node 目标节点 * param c 目标颜色 */ void setColor(RBNode* node, Color c) { if (node ! NIL) node-color c; } /** * brief 红黑树左旋操作 * param x 旋转基准节点 * note 仅调整树结构不修改颜色、不破坏BST性质 */ void leftRotate(RBNode* x) { // y为x的右孩子 RBNode* y x-right; // y的左子树挂载到x的右子树 x-right y-left; // 非空子树更新父节点 if (y-left ! NIL) y-left-parent x; // y继承x的父节点关系 y-parent x-parent; // 若x是根节点y升级为新根 if (x-parent nullptr) root y; // 若x是父节点左孩子 else if (x x-parent-left) x-parent-left y; // 若x是父节点右孩子 else x-parent-right y; // x成为y的左孩子 y-left x; x-parent y; } /** * brief 红黑树右旋操作 * param y 旋转基准节点 * note 仅调整树结构不修改颜色、不破坏BST性质 */ void rightRotate(RBNode* y) { // x为y的左孩子 RBNode* x y-left; // x的右子树挂载到y的左子树 y-left x-right; // 非空子树更新父节点 if (x-right ! NIL) x-right-parent y; // x继承y的父节点关系 x-parent y-parent; // 若y是根节点x升级为新根 if (y-parent nullptr) root x; else if (y y-parent-left) y-parent-left x; else y-parent-right x; // y成为x的右孩子 x-right y; y-parent x; } /** * brief 插入后红黑树平衡与颜色修复函数 * param cur 新插入的节点 * note 唯一违规场景父节点为红色出现连续红节点 * note 修复手段变色、左旋、右旋、向上回溯 */ void insertFix(RBNode* cur) { // 父节点为红色才存在违规 while (getColor(cur-parent) RED) { // 情况一父节点是祖父节点的左孩子 if (cur-parent cur-parent-parent-left) { RBNode* p cur-parent; // 父节点 RBNode* g p-parent; // 祖父节点 RBNode* u g-right; // 叔叔节点 // 场景1叔叔为红色 —— 纯变色修复 if (getColor(u) RED) { setColor(p, BLACK); // 父变黑 setColor(u, BLACK); // 叔叔变黑 setColor(g, RED); // 祖父变红 cur g; // 向上回溯继续修复 } else { // 场景2叔叔黑、cur是右孩子LR交叉失衡 // 先左旋转为LL直线失衡 if (cur p-right) { cur p; leftRotate(cur); } // 场景3叔叔黑、cur是左孩子LL直线失衡 setColor(p, BLACK); setColor(g, RED); rightRotate(g); } } // 情况二父节点是祖父节点的右孩子镜像对称 else { RBNode* p cur-parent; RBNode* g p-parent; RBNode* u g-left; // 场景1镜像叔叔红色 if (getColor(u) RED) { setColor(p, BLACK); setColor(u, BLACK); setColor(g, RED); cur g; } else { // 场景2镜像RL交叉失衡先右旋转RR if (cur p-left) { cur p; rightRotate(cur); } // 场景3镜像RR直线失衡 setColor(p, BLACK); setColor(g, RED); leftRotate(g); } } } // 强制根节点为黑色满足性质2 setColor(root, BLACK); } /** * brief BST底层插入逻辑 * param val 待插入数值 * note 新节点默认红色插入最小化平衡代价 */ void insert(int val) { // 新建节点默认红色绑定NIL虚拟叶子 RBNode* newNode new RBNode(val); newNode-left NIL; newNode-right NIL; // 空树直接初始化根节点 if (root nullptr) { root newNode; root-color BLACK; return; } // 非空树遍历寻找插入位置 RBNode* cur root; RBNode* pre nullptr; while (cur ! NIL) { pre cur; if (val cur-val) cur cur-left; else cur cur-right; } // 挂载新节点建立父子关系 newNode-parent pre; if (val pre-val) pre-left newNode; else pre-right newNode; // 插入完成启动平衡修复 insertFix(newNode); } /** * brief 中序遍历 BST升序输出 * param node 遍历起始节点 */ void inOrder(RBNode* node) { if (node NIL) return; inOrder(node-left); cout node-val ; inOrder(node-right); } /** * brief 后序递归销毁整树防止内存泄漏 * param node 销毁起始节点 */ void destroy(RBNode* node) { if (node NIL) return; destroy(node-left); destroy(node-right); delete node; } public: // 构造函数初始化空树 RBTree() { root nullptr; } // 析构函数释放所有节点内存 ~RBTree() { destroy(root); } // 对外公开插入接口 void insertVal(int val) { insert(val); } // 对外公开遍历接口打印有序序列 void printTree() { inOrder(root); cout endl; } };五、红黑树插入机制全解析红黑树插入是秋招、期末唯一要求手撕的核心代码旋转、变色、回溯逻辑必须完整掌握。本节补齐全套完整插入源码包含BST插入底层逻辑、insertFix平衡修复逻辑逐行超详细注释零省略、零跳转。5.1 插入核心前置原理新节点默认红色插入。核心原因若插入黑色节点会直接破坏整树黑高统一性质性质5需要全局修复代价极大若插入红色节点仅可能破坏无连续红节点性质4仅需局部变色旋转修复是最优插入策略。插入失衡四大核心角色cur当前失衡节点、p父节点、g祖父节点、u叔叔节点。5.2 插入失衡三大标准场景统一前置条件插入后父节点p为红色触发连续红色违规根据红黑树合法规则祖父节点g一定为黑色。场景一叔叔节点为红色纯变色修复无旋转结构特征父红、叔叔红、祖父黑修复逻辑父节点、叔叔节点染黑祖父节点染红当前节点回溯至祖父节点向上迭代修复上层失衡。特点无需旋转仅变色即可修复局部失衡。场景二叔叔黑色、交叉失衡LR / RL 先旋转矫正结构LR交叉父为祖父左孩子、cur为父右孩子、叔叔黑 → 左旋父节点转为LL直线失衡RL交叉父为祖父右孩子、cur为父左孩子、叔叔黑 → 右旋父节点转为RR直线失衡场景三叔叔黑色、直线失衡LL / RR 旋转变色终结修复LL直线父左、cur左、叔叔黑 → 祖父染红、父染黑、右旋祖父修复完成无回溯RR直线父右、cur右、叔叔黑 → 祖父染红、父染黑、左旋祖父修复完成无回溯5.3 完整插入全套底层源码含BST插入 平衡修复以下为可直接编译的完整插入核心代码已整合进红黑树类注释全覆盖、逻辑无省略。/** * brief 底层BST插入逻辑 * param val 待插入节点数值 * note 1. 新节点默认红色左右孩子绑定全局NIL黑节点 * note 2. 单独处理空树场景根节点强制黑色 * note 3. 遍历寻找合法插入位置维护父子指针关系 * note 4. 插入完成后调用平衡修复函数恢复红黑树五大性质 */ void insert(int val) { // 实例化新节点默认红色初始绑定NIL虚拟叶子节点 RBNode* newNode new RBNode(val); newNode-left NIL; newNode-right NIL; // 特殊情况空树新节点直接作为根节点根必须为黑色 if (root nullptr) { root newNode; root-color BLACK; return; } // 非空树按照BST规则遍历寻找插入位置 RBNode* cur root; RBNode* pre nullptr; while (cur ! NIL) { pre cur; // 记录当前节点为父节点 if (val cur-val) // 小于当前节点往左子树走 cur cur-left; else // 大于等于当前节点往右子树走 cur cur-right; } // 挂载新节点建立父子双向指针关系 newNode-parent pre; if (val pre-val) pre-left newNode; else pre-right newNode; // 插入完成启动红黑树颜色与结构平衡修复 insertFix(newNode); } /** * brief 插入后红黑树自平衡修复函数 * param cur 新插入的失衡节点 * note 仅解决【连续红节点】违规问题 * note 修复手段变色、左旋、右旋、向上回溯迭代 */ void insertFix(RBNode* cur) { // 循环条件父节点为红色出现连续红节点触发违规 while (getColor(cur-parent) RED) { // 分支1父节点是祖父节点的左孩子左侧失衡体系 if (cur-parent cur-parent-parent-left) { RBNode* p cur-parent; // 定义父节点 RBNode* g p-parent; // 定义祖父节点 RBNode* u g-right; // 定义叔叔节点 // 场景1叔叔节点为红色 —— 纯变色修复 if (getColor(u) RED) { setColor(p, BLACK); // 父节点变黑消除连续红 setColor(u, BLACK); // 叔叔节点变黑 setColor(g, RED); // 祖父节点变红向上传递失衡 cur g; // 指针回溯至祖父继续向上校验 } else { // 场景2叔叔黑、当前节点为右孩子LR交叉失衡 // 先左旋父节点将交叉结构转为LL直线结构 if (cur p-right) { cur p; leftRotate(cur); } // 场景3叔叔黑、当前节点为左孩子LL直线失衡 // 变色右旋一次性终结修复 setColor(p, BLACK); setColor(g, RED); rightRotate(g); } } // 分支2父节点是祖父节点的右孩子右侧镜像失衡体系 else { RBNode* p cur-parent; RBNode* g p-parent; RBNode* u g-left; // 场景1镜像叔叔红色纯变色修复 if (getColor(u) RED) { setColor(p, BLACK); setColor(u, BLACK); setColor(g, RED); cur g; } else { // 场景2镜像RL交叉失衡先右旋转为RR直线 if (cur p-left) { cur p; rightRotate(cur); } // 场景3镜像RR直线失衡左旋变色终结修复 setColor(p, BLACK); setColor(g, RED); leftRotate(g); } } } // 强制根节点为黑色严格遵守红黑树性质2 setColor(root, BLACK); }5.4 插入代码核心逻辑总结1、先按照标准BST规则完成节点插入新节点默认红色2、判断是否出现连续红节点违规若父节点为黑色则无需修复3、根据叔叔节点颜色、当前节点位置区分三大场景4、纯变色场景向上回溯旋转场景直接终结修复5、最后强制根节点变黑保证五大性质全部成立。秋招/面试核心结论重点记忆红黑树删除底层源码极其复杂包含双重黑色消解、四套镜像场景、多层回溯修复常规秋招面试、期末考试均不要求手写删除底层代码仅需掌握核心思路即可。本文档不提供任何删除底层代码完全贴合面试考情。6.1 删除模块核心认知红黑树插入仅破坏「无连续红节点」规则修复简单而删除操作会直接破坏黑高一致性五大核心性质5产生「双重黑色节点」是红黑树最复杂的逻辑。删除整体执行流程仅理解思路无需写代码按照标准BST规则找到待删除节点区分叶子节点、单孩子节点、双孩子节点三种情况双孩子节点采用「后继节点替换法」用右子树最小节点覆盖待删除节点值再删除后继节点判断被删除节点颜色删除红色节点无任何影响无需修复删除黑色节点会产生双重黑色破坏整树黑高平衡通过兄弟节点、兄弟节点左右孩子的颜色组合匹配4种修复场景逐层向上消解双重黑色最终恢复红黑树五大性质。6.2 面试必背问答场景一叔叔节点为红色纯变色修复无需旋转结构特征父节点红、叔叔节点红、祖父节点黑修复逻辑父、叔叔节点染黑祖父节点染红随后将当前节点回溯至祖父节点向上继续校验平衡直到根节点。核心特点无需旋转仅变色即可修复局部失衡是最简单的插入失衡场景。场景二叔叔节点黑色、交叉失衡LR / RL先旋转再修复以左侧LR为例父节点是祖父左孩子、当前节点是父节点右孩子、叔叔节点黑色修复逻辑先对父节点左旋将交叉结构转换为直线结构LL场景再进入场景三修复。右侧RL镜像先对父节点右旋转换为RR直线结构。场景三叔叔节点黑色、直线失衡LL / RR旋转变色修复以左侧LL为例父节点是祖父左孩子、当前节点是父节点左孩子、叔叔节点黑色修复逻辑祖父节点染红父节点染黑对祖父节点右旋一次性修复所有失衡无需继续回溯。右侧RR镜像祖父染红、父节点染黑对祖父节点左旋修复。七、完整测试主函数int main() { // 实例化红黑树对象 RBTree tree; // 乱序测试数据验证自动排序、自动变色、自动旋转平衡 int arr[] {10, 20, 30, 15, 25, 5}; int n sizeof(arr) / sizeof(arr[0]); // 批量插入节点 for (int i 0; i n; i) { tree.insertVal(arr[i]); } // 中序遍历一定升序验证BST特性与平衡正确性 cout 红黑树插入完成 · 中序升序遍历结果 endl; tree.printTree(); return 0; }六、工具函数、测试代码与重难点总结8.1 插入核心考点必背根黑、叶黑、节点红黑二色、无连续红、任意路径黑高相等新节点默认红色插入代价最小8.2 插入修复三大场景答题模板叔叔红仅变色向上回溯叔叔黑、LR先左旋转LL再右旋变色叔叔黑、LL直接右旋变色8.3 删除考点总结删除核心难点删除黑色节点产生双重黑色破坏全局黑高一致性修复逻辑依靠兄弟节点、兄弟子节点颜色组合4种场景逐层消解双重黑色应试结论秋招面试、基础期末考核无需掌握删除底层代码仅需理解原理8.4 红黑树 vs AVL树AVL树严格平衡查询效率高增删旋转多、效率低红黑树弱平衡允许局部不平衡旋转少、增删效率高工业级首选
