【C++】——红黑树的平衡之道：深入实现与优化

Ne0inhk

— 20 min read
【C++】——红黑树的平衡之道：深入实现与优化

坎坷之路，终抵星空。

—— 哈珀·李 《杀死一只反舌鸟》

目录

1. 解密红黑树：平衡与效率的双重奏

2. 搭建红黑树：从零到自平衡的实现之路

2.1 树基打底：设计与框架构建

2.2 插入有道：插入操作的技巧与挑战

2.3 旋转为王：平衡的秘密武器

2.4 查找制胜：高效查询之道

3. 性能透析：红黑树的效率与边界

1. 解密红黑树：平衡与效率的双重奏

  • 探讨红黑树如何通过一组简单的规则保持平衡，并提供高效的查询和更新操作。

红黑树是一种特殊的二叉树，它遵循一套独特的规则：

每个节点要么是红色，要么是黑色。根节点必须是黑色的。如果一个节点是红色的，则它的两个子节点必须是黑色的。对于任意一个节点，从该节点到其所有后代叶子节点的简单路径上，必须包含相同数目的黑色节点。每个叶子节点都是黑色的。这里的叶子节点指的是为空的节点。

TIP：红黑树的规则并不要求红黑节点严格交替出现。黑色节点可以连续，但红色节点不能连续。这是规则的设定。

通过这些规则，红黑树可以保持接近平衡的状态。虽然它不像AVL树那样可以维持严格的平衡状态，但是它可以保证搜索的效率。需要记住的是：红黑树每条路径（从根节点到空节点）上的黑色节点数量相同。

那么问题来了，红黑树如何确保最长路径不超过最短路径的2倍的？

由规则4可知，从根到NULL结点的每条路径都有相同数量的黑色结点，所以极端场景下，最短路径就是全是黑色结点的路径，假设最短路径长度为bh(black height)。由规则2和规则3可知，任意一条路径不会有连续的红色结点，所以极端场景下，最长的路径就是一黑一红间隔组成，那么最长路径的长度为 2*bh。综合红黑树的规则而言，理论上的全黑最短路径和一黑一红的最长路径并不是在每棵红黑树都存在的。假设任意一条从根到NULL结点路径的长度为x，那么bh <= x <= 2*bh。

这样红黑树保证了查找效率！！！

假设N是红黑树树中节点数量，h为最短路径长度，那么等比数列求和有 2^(h) -1<=N<=2^(2h) -1 因此可以知道 h近似为log N ，也就是意味着红黑树增删查改最坏也就是走最长路径2*logN ，那么时间复杂度还是 O(log N)

红黑树的表达相对AVL树要抽象⼀些，AVL树通过高度差直观的控制了平衡。红黑树通过规则的颜色控制，间接的实现了近似平衡，他们效率都是同⼀档次，但是相对而言，插⼊相同数量的结点，红黑树的旋转次数是更少的，因为他对平衡的控制没那么严格。

红黑树的应用场景十分广泛，其中之一是在很多高性能的C++ STL库中被广泛采用，比如map和set。这是因为红黑树具有平衡性能较好的特性，能够保持树的高度较低，从而保证了在插入、删除和查找操作上的较高效率。除此之外，它还常用于实现范围查询和有序遍历等功能。 之后我们将来实现map与set的封装！！！

红黑树的平衡性质使其在数据库系统中也得到了广泛的应用，特别是在实现索引结构时。在数据库系统中，红黑树可以用于实现基于范围的查询，如在B+树的实现中，通常使用红黑树来维护叶子节点的有序性。

2. 搭建红黑树：从零到自平衡的实现之路

2.1 树基打底：设计与框架构建

  • 红黑树的基本设计思想，构建红黑树所需的基本元素和数据结构。

红黑树的节点设计基于二叉搜索树的节点 增加了一个表示颜色的变量，用来标识该节点的颜色，我们采用枚举表示颜色状态

namespace xc { // 枚举值表⽰颜⾊ enum Colour { RED, BLACK }; // 这⾥我们默认按key/value结构实现 template<class K, class V> struct RBTreeNode { // 这⾥更新控制平衡也要加⼊parent指针 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) {} }; template<class K, class V> class RBTree { public: typedef RBTreeNode<K, V> Node; private: Node* _root = nullptr; }; }

我们按照三叉结构来构建节点，方便进行后续操作（寻找父节点，寻找爷爷节点）。键值对来储存key和key 值对应的value值，_col来储存颜色，默认创建的节点是红色。

2.2 插入有道：插入操作的技巧与挑战

  • 红黑树的插入算法，如何通过调整节点的颜色和旋转保持树的平衡。

现在我们来进行红黑树核心函数的实现，在这个插入函数中，会深刻体会到红黑树的抽象程度

首先依旧是最常规的操作：寻找插入位置：

public: bool insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); _root->_col = BLACK; return 1; } Node* cur = _root; Node* parent = nullptr; //查找逻辑 cur 到对应的位置去 while (cur) { if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else { return 0; } } }

寻找到合适的位置可以进行插入了，这里要进行一个思考：新插入的节点是什么颜色？？？

这就需要维护规则了

红色还是黑色？？？我们来分类讨论一下：

  1. 新插入黑色节点：如果我们新插入一个黑色节点，那么毋庸置疑会违反规则4 ：对于任意一个节点，从该节点到其所有后代叶子节点的简单路径上，必须包含相同数目的黑色节点。 这个是红黑树最为关键的规则，插入一个黑色节点，红黑树立刻就不是红黑树了！！！
  2. 新插入红色节点：如果我们新插入一个红色节点，那么规则4肯定是不会违反的了，但是规则3:如果一个节点是红色的，则它的两个子节点必须是黑色的。 是有可能违反的：
如果父节点是黑色，插入一个红色节点刚刚好，没有破坏红黑树的规则！！！如果父节点是红色，插入一个红色节点就违反了规则3。

所以插入黑色节点一定破坏原本的红黑树结构，插入红色节点不一定会破坏红黑树结构

因此新节点的颜色我们设置为红色。

那我们还是需要分类讨论：

  • 如果父节点是黑色，插入一个红色节点刚刚好，没有破坏红黑树的规则
  • 如果父节点是红色，插入一个红色节点就违反了规则3

我们只需要对父节点是红色进行处理了，为了保证满足规则4:对于任意一个节点，从该节点到其所有后代叶子节点的简单路径上，必须包含相同数目的黑色节点。我们仍需要对叔叔节点进行分类讨论：

  1. 如果叔叔节点是红色，那么说明爷爷节点的两个子树中黑色节点个数一致，此时只需要进行变色处理。
    父节点和叔叔节点都变成黑色，爷爷节点变成红色，然后继续向上进行（爷爷节点变成红色，类似“插入了一个红色节点”）。直到根节点结束（最后根节点还要变回黑色，此时相当于全体增加了一个黑色节点）
  2. 如果叔叔节点是黑色，那么说明爷爷节点的两个子树中黑色节点个数不一致，单纯依靠变色是不能达到要求的，这时候就要进行旋转。
    此时旋转的本质是将树的高度变低，再通过变色使其两边的黑色节点个数一致。但是无论如何，黑色节点的增加只可以再根节点进行！

所以我们先把处理的逻辑写好，稍后再来写旋转逻辑：

 bool insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); _root->_col = BLACK; return 1; } Node* cur = _root; Node* parent = nullptr; //查找逻辑 cur 到对应的位置去 while (cur) { if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else { return 0; } } cur = new Node(kv); cur->_col = RED; //新插入非空节点 为红色 // 连接 prev 与 cur if (parent->_kv.first > kv.first) parent->_left = cur; else parent->_right = cur; cur->_parent = parent; // 父亲是红色 出现了连续红节点 需要处理 可能多次处理 while向上更新 while (parent && parent->_col == RED) //可能为空 { Node* grandfather = parent->_parent; if (grandfather->_left == parent) { // g // p u Node* uncle = grandfather->_right; // 叔叔不为空 且红色 if (uncle && uncle->_col == RED) { //父亲和叔叔变黑 爷爷变红 变色 解决连续红色节点并且保证 路径黑节点数量不变 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; //往上更新 cur = grandfather; parent = cur->_parent; } else //叔叔不存在或者叔叔存在为黑色 { if (parent->_left == cur) //右单旋+变色 { // g // p u // c RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; // p // c g // u } else //双旋处理 { // g // p u // c RotateLR(grandfather); cur->_col = BLACK; grandfather->_col = RED; // c // p g // u } break; } } else { // g // u p Node* uncle = grandfather->_left; // 叔叔不为空 且红色 if (uncle && uncle->_col == RED) { //父亲和叔叔变黑 爷爷变红 变色 解决连续红色节点并且保证 路径黑节点数量不变 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; //往上更新 cur = grandfather; parent = cur->_parent; } else { if (parent->_right == cur) //左单旋+变色 { // g // u p // c RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; // p // g c // u } else //双旋处理 { // g // u p // c RotateRL(grandfather); cur->_col = BLACK; grandfather->_col = RED; // c // g p // u } break; } } } _root->_col = BLACK; return 1; }

上述即插入函数的实现但是旋转细节并没有解释且娓娓道来

2.3 旋转为王：平衡的秘密武器

  • 详细介绍红黑树中如何通过左旋和右旋操作保持平衡，并避免树的退化。

旋转函数实现细节可以参考AVL的实现

这里我们简单图解一下旋转变色机制

右单旋的情况是：父节点是红色，叔叔节点是黑色 , 插入的位置是父节点的左边。这是就要对爷爷节点进行右单旋。（hb为黑色节点个数）

void RotateR(Node* parent) { ////这里涉及三叉链的 链接交换 注意空指针引用问题 和链接顺序 //Node* subL = parent->_left; //Node* subLR = subL->_right; //parent->_left = subLR; ////subLR->_parent = parent; //这里有个问题 subLR为空呢？ //if (subLR) // subLR->_parent = parent; //subL->_right = parent; ////为根 //if (parent == _root) //{ // _root = subL; // subL->_parent = nullptr; //} // //这里个问题如何确定 subL为 parnet->parent的左右呢？ //else //不为根 还需要连接 parent->parent 和subL //{ // if (parent->_parent->_left == parent) // parent->_parent->_left = subL; // else // parent->_parent->_right = subL; // subL->_parent = parent->_parent; //} //parent->_parent = subL; Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; //subLR->_parent = parent; //这里有个问题 subLR为空呢？ if (subLR) subLR->_parent = parent; Node* pparent = parent->_parent; //先记录再更改指向 subL->_right = parent; parent->_parent = subL; //为根 if (parent == _root) { _root = subL; subL->_parent = nullptr; } //这里个问题如何确定 subL为 parnet->parent的左右呢？ else //不为根 还需要连接 parent->parent 和subL { if (pparent->_left == parent) pparent->_left = subL; else pparent->_right = subL; subL->_parent = pparent; } }

左单旋逻辑是一样的只是对称一下

void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL->_parent = parent; Node* pparent = parent->_parent; subR->_left = parent; parent->_parent = subR; if (parent == _root) { _root = subR; subR->_parent = nullptr; } else { if (pparent->_left == parent) pparent->_left = subR; else pparent->_right = subR; subR->_parent = pparent; } }

接下来我们来看双旋的情况，左右双旋如图：

直接对单旋复用即可，值得注意的是变色问题

 void RotateLR(Node* parent) { RotateL(parent->_left); RotateR(parent); } // 右左双旋 parent最后在 subRL左 void RotateRL(Node* parent) { RotateR(parent->_right); RotateL(parent); }

可以注意到旋转逻辑之后 变色现象 最终根是黑色，左右是红色

 if (uncle && uncle->_col == RED) { //父亲和叔叔变黑 爷爷变红 变色 解决连续红色节点并且保证 路径黑节点数量不变 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; //往上更新 cur = grandfather; parent = cur->_parent; } else //叔叔不存在或者叔叔存在为黑色 { if (parent->_left == cur) //右单旋+变色 { // g（黑） // p（红） u（黑） // c（红） RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; // p（黑） // c（红） g（红） // u（黑） } else //双旋处理 { // g（黑） // p（红） u（黑） // c（红） RotateLR(grandfather); cur->_col = BLACK; grandfather->_col = RED; // c（黑） // p（红） g（红） // u（黑） } break; } } else { // g // u p Node* uncle = grandfather->_left; // 叔叔不为空 且红色 if (uncle && uncle->_col == RED) { //父亲和叔叔变黑 爷爷变红 变色 解决连续红色节点并且保证 路径黑节点数量不变 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; //往上更新 cur = grandfather; parent = cur->_parent; } else { if (parent->_right == cur) //左单旋+变色 { // g（黑） // u（黑） p（红） // c（红） RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; // p（黑） // g（红） c（红） // u（黑） } else //双旋处理 { // g（黑） // u（黑） p（红） // c（红） RotateRL(grandfather); cur->_col = BLACK; grandfather->_col = RED; // c（黑） // g（红） p（红） // u（黑） } break; } } }

2.4 查找制胜：高效查询之道

  • 如何通过红黑树的特性实现高效的查找操作，保证最坏情况下的时间复杂度为O(log n)。

查找逻辑仍是按照二叉搜素树对key进行查找

 Node* find(const K& key) { Node* cur = _root; while (cur) { if (cur->_kv.first < key) { cur = cur->_right; } else if (cur->_kv.first > key) { cur = cur->_left; } else { return cur; } } return nullptr; }

3. 性能透析：红黑树的效率与边界

  • 分析红黑树在不同应用场景中的性能表现，探讨其与其他平衡树（如AVL树、B树等）的比较和优缺点。

还是老操作，测试一下RBTree是否满足条件！

这⾥获取最长路径和最短路径，检查最长路径不超过最短路径的2倍是不可行的，因为就算满足这个条件，红黑树也可能颜色不满足规则，当前暂时没出问题，后续继续插入还是会出问题的。所以我们还是去检查规则，满足这些规则，⼀定能保证最长路径不超过最短路径的2倍。

1. 规则1枚举颜色类型，天然实现保证了颜色不是黑色就是红色。
2. 规则2直接检查根即可
3. 规则3前序遍历检查，遇到红色结点查孩子不方便，因为孩子有两个，且不⼀定存在，反过来检查父亲的颜色就方便许多。
4. 规则4前序遍历，遍历过程中用形参记录跟到当前结点的blackNum(黑色结点数量)，前序遍历遇到黑色结点就 ++blackNum ，走到空就计算出了⼀条路径的黑色结点数量。再与任意⼀条路径黑色结点数量作为参考值，依次比较即可。
 

这里我们给出refNum 参考值进行比较

 bool isBalance() { if (_root == nullptr) return true; if (_root->_col == RED) return false; // 参考值 int refNum = 0; Node* cur = _root; while (cur) { if (cur->_col == BLACK) { ++refNum; } cur = cur->_left; } return Check(_root, 0, refNum); } bool Check(Node * root, int blackNum, const int refNum) { if (root == nullptr) { // 前序遍历⾛到空时，意味着⼀条路径⾛完了 //cout << blackNum << endl; if (refNum != blackNum) { cout << "存在黑色结点的数量不相等的路径" << endl; return false; } return true; } //检查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲就⽅便多了 if (root->_col == RED && 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); }

现在我们进行测试一下

void TestRBTree2() { const int N = 10000000; vector<int> v; v.reserve(N); srand(time(0)); for (size_t i = 0; i < N; i++) { v.push_back(rand() + i); } size_t begin2 = clock(); xc::RBTree<int, int> t; for (auto e : v) { t.insert(make_pair(e, e)); } size_t end2 = clock(); cout << "Insert:" << end2 - begin2 << endl; cout << t.isBalance() << endl; cout << "Height:" << t.height() << endl; cout << "Size:" << t.size() << endl; }

一千万的数据我们进行检查后依然是满足红黑树的规则

红黑树和 AVL 树都是自平衡的二叉搜索树，它们的主要区别如下：

一、时间复杂度

  1. 查找操作：
    • 红黑树和 AVL 树在查找操作上的时间复杂度都为O（logN） ，其中 N 是树中节点的数量。这是因为它们都是二叉搜索树，并且通过自平衡机制保持树的高度相对较低，从而保证了高效的查找性能。
  2. 插入和删除操作：
    • 红黑树和 AVL 树在插入和删除操作时都需要进行旋转等操作来维持树的平衡，但红黑树的旋转次数相对较少。
    • 红黑树的插入和删除操作的时间复杂度也为 O（logN）。
    • AVL 树在插入和删除节点后，为了保持平衡，可能需要进行多次旋转操作，其时间复杂度也为O（logN） ，但在一些情况下可能会比红黑树的操作更耗时。

二、高度

  1. AVL 树：
    • AVL 树是高度平衡的二叉搜索树，即任何节点的左右子树高度差最多为 1。
    • 由于高度严格平衡，AVL 树的高度为O（logN） ，其中 N 是树中节点的数量。
  2. 红黑树：
    • 红黑树是一种弱平衡的二叉搜索树，它通过对节点颜色的约束来保证一定程度的平衡。
    • 红黑树的高度最多为 2*logN+1)，相对 AVL 树来说可能会略高一些，但仍然是对数级别的。

三、性能区别

  1. 插入和删除操作频繁的场景：
    • 红黑树在插入和删除操作上相对更加高效。因为红黑树的平衡调整相对较少，旋转操作也相对简单，所以在频繁进行插入和删除操作的情况下，性能可能更好。
    • 例如，在数据库索引、内存管理等场景中，红黑树可能更适合，因为这些场景中数据的动态变化较为频繁。
  2. 查找操作频繁的场景：
    • AVL 树由于高度更严格平衡，可能在查找操作上稍微快一些。
    • 如果应用场景主要是进行大量的查找操作，而插入和删除操作相对较少，那么 AVL 树可能是更好的选择。

综上所述，红黑树和 AVL 树在时间复杂度上相似，但在高度和性能上存在一些区别。选择使用哪种树结构取决于具体的应用场景和需求。如果需要频繁进行插入和删除操作，红黑树可能更合适；如果主要是进行查找操作，AVL 树可能性能更好。

Thanks谢谢阅读！！！

Read more

保姆级教程：Windows下安装OpenClaw + 接入飞书机器人，看这一篇就够了！

文章目录 * 前言 * ⚠️ 重要提示：隐私安全优先 * 第一部分：Windows环境准备 * 1.1 系统要求 * 1.2 安装nvm for Windows（推荐） * 1.3 安装Node.js 22.x版本 * 第二部分：安装OpenClaw * 2.1 一键安装脚本（推荐） * 2.2 初始化配置 * 2.3 启动服务并验证 * 第三部分：配置大模型API（核心前提） * 第四部分：飞书机器人配置（核心步骤） * 4.1 安装飞书插件 * 4.2 创建飞书企业自建应用 * 4.3 添加机器人能力 * 4.4

By Ne0inhk
免费部署openClaw龙虾机器人（经典）

免费部署openClaw龙虾机器人（经典）

前几天出了个免费玩龙虾的详细教程，很多小伙伴觉得不错，但是还有一些新手留言反馈内容不够详细，这次我将重新梳理一遍，做一期更细致的攻略，同时扩展补充配置好之后的推荐（我认为是必要）操作，争取一篇文章让大家可以收藏起来，随时全套参照复用。 先看效果测试 部署完成基础运行效果测试，你可以直接问clawdbot当前的模型： 1.Token平台准备 首先，还是准备好我们可以免费撸的API平台 这里我找到了两个可以免费使用的API，测试之后执行效率还可以，下面将分别进行细致流程拆解。 1.1 硅基流动获取ApiKey （相对免费方案 推荐） 硅基流动地址：https://cloud.siliconflow.cn/i/6T57VxS2 如果有账号的直接登录，没有的注册一个账号，这个认证就送16元，可以直接玩收费模型，真香。认证完成后在API秘钥地方新建秘钥。 硅基流动里面很多模型原来是免费的，有了16元注册礼，很多收费的模型也相当于免费用了，我体验一下了原来配置免费模型还能用，也是值得推荐的。建议使用截图的第一个模型体验一下，我一直用它。 1.2 推理时代

By Ne0inhk
ABB 机器人虚拟示教器基础操作教程

ABB 机器人虚拟示教器基础操作教程

一、基础操作界面与模式 1. 操作模式切换 * 手动模式：用于编程、调试和手动操作 自动模式：用于程序自动运行（需满足安全条件） 2. 动作模式选择（手动模式下） * 单轴模式：单独控制每个关节轴（1-6轴） * 优点：最直观，与坐标系无关 * 用途：调整机器人姿态，避免奇异点 * 线性模式：TCP沿直线运动 * 重定位模式：TCP位置不变，只改变工具姿态 点击示教器左上角 进入菜单栏 3. 坐标系选择（线性/重定位模式下） 四个可选坐标系： * 大地坐标系：机器人安装的基础坐标系 * 基座坐标系：机器人底座中心为原点（多数基本选择） * 工件坐标系：用户自定义的工作平面 * 工具坐标系：以工具末端为原点 二、三大核心数据设置 1. 工具数据（tooldata） 定义：描述工具（

By Ne0inhk

2026年RAG技术路线图：基于DeepSeek与Neo4j知识图谱构建企业智能体系

RAG的演进：为何图检索增强生成（GraphRAG）将主导2026年 检索增强生成（RAG）自问世以来经历了深刻变革，2026年标志着其向图检索增强生成（GraphRAG）范式的关键性转变。这一演进源于传统平面向量型RAG在满足企业级复杂推理和可靠决策支持需求方面日益凸显的局限性。 这一转型的核心驱动力是从平面向量相似性向复杂关系推理的跨越。传统RAG依赖向量嵌入来衡量查询与文档片段的语义相似性，但这种方法无法捕捉企业决策至关重要的实体、概念与事件间的复杂关联。相比之下，GraphRAG将信息构建为包含节点（实体）和边（关系）的知识图谱，使模型能够遍历并推理这些关联——解锁了平面向量RAG无法实现的多跳推理和上下文关系理解能力。 GraphRAG还解决了传统RAG的两大长期痛点：上下文窗口限制和“中间信息丢失”问题。随着企业查询日益复杂，需要更大的上下文窗口来整合相关信息，但即便是最先进的大语言模型（LLM）也存在有限的上下文容量。GraphRAG通过将结构化知识存储在外部图数据库中解决了这一问题，允许模型按需检索最相关的节点和关系，而非将大量文本塞入上下文窗口。此外，“中间信息

By Ne0inhk