深入解剖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

OCI 连接失败、PL/SQL 报错？金仓数据库直击 Oracle 迁移 4 大痛点，一次破解！

OCI 连接失败、PL/SQL 报错？金仓数据库直击 Oracle 迁移 4 大痛点，一次破解！

引言 现在企业都在忙着搞数字化转型，信创改造更是提上了所有企业的日程——说白了，就是把核心系统里的国外数据库换成国产的，实现自主可控。Oracle 作为老牌商业数据库，靠谱了几十年，不少政企的核心系统——像财务核算、业务审批、生产调度这些关键环节——都用了它，稳定得没话说。 可一到迁移环节，各种问题就扎堆冒出来：应用和数据库的“通信线”总断、写好的代码一迁就报错、常用的功能突然用不了、改造期限越来越近，迁移进度却越拖越慢……很多企业本来想借着迁移升级系统，结果反而被这些麻烦拖了后腿，甚至影响到正常业务运转。 作为国产数据库的头部玩家，电科金仓早就盯着这些迁移痛点了。靠着这么多年打磨的 Oracle 兼容能力和实打实的实战经验，金仓数据库能精准解决这些问题，让企业不用“推倒重来”，顺顺利利就把 Oracle 换成国产数据库。 一、Oracle 迁移四大核心痛点，企业直呼“扛不住” 1.1 痛点一：OCI 连接总掉线，数据传输“断联”

By Ne0inhk
828华为云征文｜使用sysbench对Flexus X实例对mysql进行性能测评

828华为云征文｜使用sysbench对Flexus X实例对mysql进行性能测评

目录 一、Flexus X实例概述 1.1 Flexus X实例 1.2 在mysql方面的优势 二、在服务器上安装MySQL 2.1 在宝塔上安装docker 2.2 使用宝塔安装mysql 2.3 准备测试数据库和数据库表 三、安装sysbench并进行性能测试 3.1 使用yum命令sysbench 3.2 运行 sysbench 并进行性能测试 3.3 运行结果分析性能 SQL Statistics General Statistics Latency (延迟) Threads Fairness 3.4 清理测试数据 3.5 总结 一、

By Ne0inhk

MySQL的水平分库分表和垂直分库分表

在MySQL中，分库分表是一种常见的数据库优化策略，用于解决单表数据量过大导致的性能问题。分库分表可以分为水平分库分表和垂直分库分表，它们分别有不同的含义和应用场景。下面详细解释这两种分库分表方式： 1. 水平分库分表（Horizontal Sharding） 水平分库分表是指将数据按照某种规则分散到多个数据库或表中，每个数据库或表中的数据结构相同，但数据行不同。这种分库分表方式主要解决的是数据量过大的问题，通过将数据分散到多个存储单元中，可以提高查询和更新的效率。 场景 * 单表数据量过大：当单个表的数据量达到数亿甚至数十亿条记录时，查询和更新性能会显著下降。 * 高并发读写：在高并发场景下，单表的读写性能可能成为瓶颈。 示例 假设有一个用户表users，存储了大量用户信息。当数据量过大时，可以将用户表按照用户ID的范围进行水平分表： * users_0：存储用户ID为0-999999的用户 * users_1：存储用户ID为1000000-1999999的用户 * users_2：存储用户ID为2000000-2999999的用户 * ... 或者按照用

By Ne0inhk
OpenClaw 树莓派部署终极避坑指南：解决OpenClaw Gateway仪表盘登录问题

OpenClaw 树莓派部署终极避坑指南：解决OpenClaw Gateway仪表盘登录问题

🚀 OpenClaw 树莓派部署终极避坑指南：解决OpenClaw Gateway仪表盘登录问题 在树莓派上部署 OpenClaw 时，很多开发者会遭遇一连串的“拦路虎”：从局域网无法访问，到跨域报错，再到 HTTPS 安全上下文限制，最后是设备配对验证。 本文完整复盘了我遇到的四个核心问题及其解决方案，按发生顺序排列，助您一次性打通所有关卡，顺利运行 AI 代理网关。 在其他类型系统上的解决方案基本一致 📋 目录 1. 第一关：局域网无法访问 (端口监听问题) 2. 第二关：跨域错误 CORS (白名单配置) 3. 第三关：安全上下文限制 (必须启用 HTTPS) 4. 第四关：Pairing Required (设备身份验证) 5. 总结：完整配置清单 🔌 第一关：局域网无法访问 (端口监听问题) ❌ 现象描述 树莓派上的

By Ne0inhk