深入解剖STL RB-tree(红黑树)：用图解带入相关复杂操作实现

Ne0inhk

— 14 min read
深入解剖STL RB-tree(红黑树)：用图解带入相关复杂操作实现
在这里插入图片描述

👇点击进入作者专栏：

《算法画解》 ✅

《linux系统编程》✅

《C++》 ✅

文章目录

一、红黑树介绍

1. 什么是红黑树？

红黑树是一种自平衡的二叉搜索树。它在每个节点上增加一个存储位表示节点的颜色，可以是红色或黑色。通过对任何一条从根到叶子（空节点）路径上节点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出两倍，因此是近似平衡的。

红黑树的平衡不像AVL树那样严格，但它的旋转次数更少，插入删除的效率也更高。

2. 红黑树的规则

红黑树的平衡靠以下4条规则来维持：

  1. 每个节点不是红色就是黑色
  2. 根节点是黑色的
  3. 如果一个节点是红色的，那么它的两个孩子节点必须是黑色的（即不能有连续的红色节点）
  4. 对于任意节点，从该节点到其所有叶子节点的简单路径上，黑色节点数量相同注意：叶子节点不一定为红色，可以为黑（那是调整过后的结果）。
规则4中提到的叶子节点指的是空节点（NIL），它们被认为是黑色的。虽然在实际实现中我们通常不显式处理NIL节点，但理解它们有助于理解路径的定义。
在这里插入图片描述


在这里插入图片描述


在这里插入图片描述

3. 为什么最长路径不超过最短路径的两倍？

  • 根据规则4，每条路径上黑色节点数相同，假设为 bh（black height）。
  • 最短路径：全黑，长度为 bh。
  • 最长路径：黑-红交替，长度为 2 * bh。
  • 因此，任意路径长度 h 满足：bh ≤ h ≤ 2 * bh。

4. 红黑树的效率

假设树中节点数为 N，最短路径长度为 h，则：

2^h - 1 <= N <= 2^(2h) - 1

可得 h ≈ logN，最坏情况下路径长度为 2logN，因此红黑树的查找、插入、删除操作时间复杂度仍为 O(logN)。

相比AVL树，红黑树的平衡控制更宽松，旋转次数更少，适合频繁插入删除的场景。

在这里插入图片描述

二、红黑树的实现

2.1 红黑树的节点结构

源码：

typedef bool __rb_tree_color_type; const __rb_tree_color_type __rb_tree_red = false; // 红色为 0 const __rb_tree_color_type __rb_tree_black = true; // 黑色为 1 struct __rb_tree_node_base { typedef __rb_tree_color_type color_type; typedef __rb_tree_node_base* base_ptr; color_type color; // 节点颜色，非红即黑 base_ptr parent; // RB 树的许多操作，必须知道父节点 base_ptr left; // 指向左节点 base_ptr right; // 指向右节点 static base_ptr minimum(base_ptr x) { while (x->left != 0) x = x->left; return x; } static base_ptr maximum(base_ptr x) { while (x->right != 0) x = x->right; // 一直向右走，就会找到最大值， return x; // 这是二叉搜索树的特性 } }; template <class Value> struct _rb_tree_node : public _rb_tree_node_base { typedef _rb_tree_node<Value>* link_type; Value value_field; // 节点值 };

实现：

每个节点除了存储键值对、左右子节点指针、父节点指针外，还需要存储颜色。

// 枚举颜色enumColour{ RED, BLACK };// 红黑树节点结构template<classK,classV>structRBTreeNode{ 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)// 默认新节点为红色{}};
新节点为什么默认是红色？
如果插入黑色节点，会直接违反规则4（黑色节点数变化），修复成本太高。插入红色节点不会改变黑色节点数，只可能违反规则3（连续红色），更容易修复。

2.2 红黑树整体结构

template<classK,classV>classRBTree{// 类型重命名，方便使用typedef RBTreeNode<K, V> Node;public:// 构造函数（默认根节点为空）RBTree():_root(nullptr){}// 插入接口boolInsert(const pair<K, V>& kv);// 查找接口 Node*Find(const K& key);// 验证是否满足红黑树性质boolIsBalance();// 中序遍历（用于验证有序性）voidInOrder(){_InOrder(_root); cout << endl;}private:// 旋转操作（与AVL树类似，但不需要更新平衡因子）voidRotateL(Node* parent);// 左单旋voidRotateR(Node* parent);// 右单旋// 递归辅助函数void_InOrder(Node* root);boolCheck(Node* root,int blackNum,constint refNum);// 根节点 Node* _root =nullptr;};

三、红黑树的插入操作

3.1 插入的大致流程

  1. 按二叉搜索树的规则插入新节点。
  2. 新节点默认是红色。
  3. 如果插入后父节点是黑色，则插入结束（没有违反规则）。
  4. 如果父节点是红色，则违反规则3（连续红色），需要修复。
  5. 根据叔叔节点的颜色和位置，分情况处理。

3.2 插入后的三种情况

为了方便描述，我们约定：

  • cur：当前新插入的节点（红色）
  • p：父节点（红色，因为如果是黑色就不用处理了）
  • g：祖父节点（一定是黑色，因为不能连续红）
  • u：叔叔节点（p的兄弟，颜色不确定）

情况1：叔叔节点存在且为红色（变色处理）

【场景描述】

  • u 存在且为红色
  • p 为红色，g 为黑色

【处理方式】

  • 将 p 和 u 变为黑色
  • 将 g 变为红色
  • 把 g 当作新的 cur，继续向上检查

【原理分析】
把 p 和 u 变黑，解决了 cur 和 p 连续红的问题；g 变红，保证了从 g 到叶子路径上黑色节点数量不变（因为下面少了两个黑，上面加了一个红，黑数不变）。但 g 变红后可能和它的父节点形成连续红，所以需要继续向上检查。

在这里插入图片描述
// 情况1：叔叔存在且为红 if (uncle && uncle->_col == RED) { // 变色 parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; // 继续向上处理 cur = grandfather; parent = cur->_parent; }

情况2：叔叔节点不存在或为黑色 + cur和p在同一侧（单旋+变色）

【场景描述】

  • u 不存在 或 u 存在且为黑色
  • cur 和 p 在同一侧（都是左孩子 或 都是右孩子）

【处理方式】

  • 以 g 为旋转点进行单旋（左左→右旋，右右→左旋）
  • 旋转后：p 变黑，g 变红
  • 调整结束（不需要继续向上）

【原理分析】
为什么单旋后不用继续向上？因为旋转后 p 成了子树的新根，且 p 是黑色，无论它的父节点是什么颜色，都不会违反规则（红节点下面不能接红，但黑节点下面随便接）。

在这里插入图片描述
// 情况2：左左（右单旋） if (cur == parent->_left) { // 右单旋 RotateR(grandfather); // 变色 parent->_col = BLACK; grandfather->_col = RED; break; // 旋转结束，不用继续向上 }

情况3：叔叔节点不存在或为黑色 + cur和p在不同侧（双旋+变色）

【场景描述】

  • u 不存在 或 u 存在且为黑色
  • cur 和 p 在不同侧（p是左孩子，cur是右孩子 或 反之）

【处理方式】

  • 先以 p 为旋转点进行单旋（变成情况2的形状）
  • 再以 g 为旋转点进行单旋
  • 变色：cur 变黑，g 变红
  • 调整结束

【原理分析】
这种情况是"折线"形状，一次旋转解决不了问题。先旋转成"直线"形状，再按情况2处理。

// 情况3：左右（左右双旋） else // cur == parent->_right { // 先左旋p，再右旋g RotateL(parent); RotateR(grandfather); // 变色 cur->_col = BLACK; grandfather->_col = RED; break; // 旋转结束，不用继续向上 }

3.3 插入完整代码

boolInsert(const pair<K, V>& kv){// 1. 空树插入if(_root ==nullptr){ _root =newNode(kv); _root->_col = BLACK;// 根节点必须是黑色returntrue;}// 2. 查找插入位置 Node* parent =nullptr; Node* cur = _root;while(cur){if(cur->_kv.first < kv.first){ parent = cur; cur = cur->_right;}elseif(cur->_kv.first > kv.first){ parent = cur; cur = cur->_left;}else{returnfalse;// 键值已存在}}// 3. 插入新节点，颜色为红色 cur =newNode(kv); cur->_col = RED;// 新节点默认红色if(parent->_kv.first < kv.first) parent->_right = cur;else parent->_left = cur; cur->_parent = parent;// 4. 修复红黑树性质while(parent && parent->_col == RED){ Node* grandfather = parent->_parent;if(parent == grandfather->_left){ Node* uncle = grandfather->_right;// 情况1：叔叔存在且为红 → 变色if(uncle && uncle->_col == RED){ parent->_col = uncle->_col = BLACK; grandfather->_col = RED;// 继续向上处理 cur = grandfather; parent = cur->_parent;}else{// 情况2：叔叔不存在或为黑if(cur == parent->_left){// 左左 → 右单旋RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED;}else{// 左右 → 左右双旋RotateL(parent);RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED;}break;// 旋转后子树根变黑，不再影响上层}}else// parent == grandfather->_right{ Node* uncle = grandfather->_left;if(uncle && uncle->_col == RED){ parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent;}else{if(cur == parent->_right){// 右右 → 左单旋RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED;}else{// 右左 → 右左双旋RotateR(parent);RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED;}break;}}}// 确保根节点始终为黑色 _root->_col = BLACK;returntrue;}

3.4 旋转操作的实现

旋转操作和AVL树基本一样，只是不需要更新平衡因子。但要注意父指针的更新！

左单旋：

template<class K, class V> void RBTree<K, V>::RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; // 1. 将subRL链接到parent的右 parent->_right = subRL; if (subRL) subRL->_parent = parent; // 2. 记录parent的原父节点 Node* pParent = parent->_parent; // 3. subR的左指向parent subR->_left = parent; parent->_parent = subR; // 4. 处理subR与上层节点的链接 if (parent == _root) { // parent是根节点 _root = subR; subR->_parent = nullptr; } else { // parent是局部子树 if (pParent->_left == parent) pParent->_left = subR; else pParent->_right = subR; subR->_parent = pParent; } // 注意：不需要更新平衡因子！ }

右单旋：

template<class K, class V> void RBTree<K, V>::RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; // 1. 将subLR链接到parent的左 parent->_left = subLR; if (subLR) subLR->_parent = parent; // 2. 记录parent的原父节点 Node* pParent = parent->_parent; // 3. subL的右指向parent subL->_right = parent; parent->_parent = subL; // 4. 处理subL与上层节点的链接 if (parent == _root) { _root = subL; subL->_parent = nullptr; } else { if (pParent->_left == parent) pParent->_left = subL; else pParent->_right = subL; subL->_parent = pParent; } }

四、红黑树的查找

与普通二叉搜索树相同，时间复杂度 O(logN)。

template<classK,classV>typenameRBTree<K, V>::Node*RBTree<K, V>::Find(const K& key){ Node* cur = _root;while(cur){if(cur->_kv.first < key){ cur = cur->_right;// 去右子树找}elseif(cur->_kv.first > key){ cur = cur->_left;// 去左子树找}else{return cur;// 找到了}}returnnullptr;// 没找到}

五、红黑树的验证

验证一棵树是否是红黑树，不能简单地检查"最长路径≤最短路径的2倍"，因为即使满足这个条件，也可能不满足颜色规则。必须严格检查4条规则。

5.1 验证的思路

  1. 规则1：枚举类型天然保证，不需要检查
  2. 规则2：检查根节点是否为黑色
  3. 规则3：检查是否有连续的红色节点（可以检查红色节点的父节点是否为红色）
  4. 规则4：检查所有路径的黑色节点数是否相等
在这里插入图片描述

5.2 验证的代码实现

template<class K, class V> bool RBTree<K, V>::IsBalance() { if (_root == nullptr) return true; // 规则2：检查根节点是否为黑色 if (_root->_col == RED) { cout << "错误：根节点为红色" << endl; return false; } // 规则4：找一个参考值（最左路径的黑色节点数） int refNum = 0; Node* cur = _root; while (cur) { if (cur->_col == BLACK) refNum++; cur = cur->_left; } // 递归检查每条路径 return Check(_root, 0, refNum); } template<class K, class V> bool RBTree<K, V>::Check(Node* root, int blackNum, const int refNum) { if (root == nullptr) { // 走到空节点，说明一条路径走完了 // 规则4：检查黑色节点数是否等于参考值 if (blackNum != refNum) { cout << "错误：黑色节点数量不相等，当前路径有" << blackNum << "个，参考值为" << refNum << endl; return false; } return true; } // 规则3：检查是否有连续的红色节点 // 技巧：检查红色节点的父节点（孩子有两个不好检查，检查父亲更方便） if (root->_col == RED && root->_parent && root->_parent->_col == RED) { cout << "错误：存在连续的红色节点，节点值为" << root->_kv.first << endl; return false; } // 统计黑色节点 if (root->_col == BLACK) blackNum++; // 递归检查左右子树 return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum); }

5.3 中序遍历（验证有序性）

template<class K, class V> void RBTree<K, V>::_InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_kv.first << ":" << root->_kv.second << " "; _InOrder(root->_right); }
在这里插入图片描述

加油！志同道合的人会看到同一片风景。
看到这里请点个赞，关注，如果觉得有用就收藏一下吧。后续还会持续更新的。 创作不易，还请多多支持！

Read more

Flutter 三方库 lint_staged 的鸿蒙化适配指南 - 在鸿蒙系统上构建严谨、自动化的代码提交风控体系

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net Flutter 三方库 lint_staged 的鸿蒙化适配指南 - 在鸿蒙系统上构建严谨、自动化的代码提交风控体系 在鸿蒙（OpenHarmony）的大型研发团队中，代码质量的“守门员”任务至关重要。如果我们能在 Git 提交的瞬间自动执行静态扫描与格式化，就能极大减少后期 Code Review 的修边角成本。lint_staged 为鸿蒙开发者提供了一套完美集成的 Git Hook 工具。本文将实战演示如何在其背后构建鸿蒙代码提交的质量闭环。 前言 什么是 Lint Staged？它只对 Git 暂存区（Staged）的文件运行检查。在鸿蒙项目涉及成千上万个文件时，如果全量运行脚本将极其缓慢。lint_staged 通过精准的文件过滤，让鸿蒙开发者能在提交代码的几秒钟内完成格式校准和语法扫描，确保每一行入库的代码都符合鸿蒙架构的设计规范。 一、

By Ne0inhk
Flutter 组件 assertable_json 的适配 鸿蒙Harmony 实战 - 驾驭结构化 JSON 断言、实现鸿蒙端 API 回包自动化审计与零容错数据校验方案

Flutter 组件 assertable_json 的适配 鸿蒙Harmony 实战 - 驾驭结构化 JSON 断言、实现鸿蒙端 API 回包自动化审计与零容错数据校验方案

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net Flutter 组件 assertable_json 的适配 鸿蒙Harmony 实战 - 驾驭结构化 JSON 断言、实现鸿蒙端 API 回包自动化审计与零容错数据校验方案 前言 在鸿蒙（OpenHarmony）生态的金融级应用、大型电商后台以及涉及到敏感信息交换的政务系统中，“数据一致性”是高可用架构的最后一道防线。面对后端返回的动辄数千行、深度嵌套十余层的 JSON 数据流。如果仅仅依靠 data['user']['info']['id'] != null 这种脆弱的手动判空。那么不仅会导致代码中充斥着大量的噪声片段。更会因为某个微小的字段缺失（如：金额字段 amount 变为了 null）

By Ne0inhk
【Linux系统编程】（三十四）初识进程信号：Linux 软中断的核心奥秘

【Linux系统编程】（三十四）初识进程信号：Linux 软中断的核心奥秘

目录 前言 一、从生活场景理解信号：原来信号这么简单 1.1 快递的故事：完美映射信号处理流程 1.2 生活场景到 Linux 信号的核心结论 二、技术视角：Linux 进程信号的初体验 2.1 第一个实验：Ctrl+C的本质 —— 向前台进程发送 2 号信号SIGINT 代码实现：sig_hello.c 编译运行 2.2 第二个实验：修改信号处理方式 —— 让Ctrl+C不再终止进程 2.2.1 signal函数介绍 2.2.2 代码实现：sig_catch.c 2.2.

By Ne0inhk
OpenClaw 劝退率高？ClawX 完整安装指南（Windows/macOS/Linux），零基础也能会

OpenClaw 劝退率高？ClawX 完整安装指南（Windows/macOS/Linux），零基础也能会

前言：从 “极客劝退” 到 “全民上手”，ClawX 到底解决了什么？ 最近 OpenClaw 彻底火出圈，作为能让 AI 帮你整理文件、监控网页、定时干活的智能体框架，它的潜力让无数打工人和自媒体人眼馋。但实际情况是，十个人里九个半栽在安装部署这一步 —— 配 Node.js 环境、改 YAML 配置、敲命令行、查端口占用，光是搞定这些，就足以让非技术用户直接放弃。 我做了 15 年电脑维护，见过太多用户被命令行和配置文件劝退的场景。直到 ClawX 出现，这款 OpenClaw 的可视化桌面客户端，把原本需要极客功底的操作，简化成了 “下一步安装、聊天式操作” 的程度。今天就给大家带来一份全网最细的 ClawX 保姆级安装教程，涵盖 Windows、macOS、

By Ne0inhk