【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

Flutter for OpenHarmony: Flutter 三方库 fake_async 掌控时间的魔法，让鸿蒙异步单测快如闪电（单元测试加速神器）

Flutter for OpenHarmony: Flutter 三方库 fake_async 掌控时间的魔法，让鸿蒙异步单测快如闪电（单元测试加速神器）

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net 前言 在 OpenHarmony 应用的单元测试中，异步逻辑是一个避不开的难点。如果你的代码中有 Future.delayed(Duration(minutes: 5))，难道你在跑测试时真的要等上 5 分钟吗？或者如果你在测试一个复杂的动画状态流转，如何精确地模拟时间流逝了 125 毫秒？ fake_async 是 Dart 测试工具链中的“时间胶囊”。它能在一个受控的环境中虚拟化时钟。你可以瞬间“拨快”时间，让那些原本需要漫长等待的异步操作立即执行，从而让你的鸿蒙单测运行速度提升千倍。 一、核心虚拟时间原理 它通过接管全局的 Zone，拦截了所有基于时间的调度任务。 elapse(5 mins) 测试用例 fakeAsync 闭包环境 挂起的延迟任务 (Future/Stream) 瞬间拨快虚拟时钟

By Ne0inhk
ARM Linux 驱动开发篇--- Linux 并发与竞争实验（信号量实现 LED 设备互斥访问）--- Ubuntu20.04信号量实验

ARM Linux 驱动开发篇--- Linux 并发与竞争实验（信号量实现 LED 设备互斥访问）--- Ubuntu20.04信号量实验

🎬 渡水无言：个人主页渡水无言 ❄专栏传送门： 《linux专栏》《嵌入式linux驱动开发》《linux系统移植专栏》 ❄专栏传送门： 《freertos专栏》《STM32 HAL库专栏》 ⭐️流水不争先，争的是滔滔不绝  📚博主简介：第二十届中国研究生电子设计竞赛全国二等奖 |国家奖学金 | 省级三好学生 | 省级优秀毕业生获得者 | ZEEKLOG新星杯TOP18 | 半导纵横专栏博主 | 211在读研究生 在这里主要分享自己学习的linux嵌入式领域知识；有分享错误或者不足的地方欢迎大佬指导，也欢迎各位大佬互相三连 目录 前言 一、实验基础说明 1.1、信号量简介 1.2 本次实验设计思路 二、硬件原理分析（看过之前博客的可以忽略） 三、实验程序编写 3.1 信号量 LED 驱动代码（spinlock.c） 3.2、驱动代码分段解析 3.2.

By Ne0inhk
Flutter for OpenHarmony: Flutter 三方库 intersperse 优雅在鸿蒙列表项间插入间隔或装饰（UI 细节处理助手）

Flutter for OpenHarmony: Flutter 三方库 intersperse 优雅在鸿蒙列表项间插入间隔或装饰（UI 细节处理助手）

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net 前言 在 OpenHarmony 应用的 UI 设计中，我们经常需要在列表（List）或一排组件（Column/Row）之间插入特定的元素，例如： 1. 在一排按钮中间插入分隔线。 2. 在列表数据项之间插入间隙（Spacing）。 3. 为每个组件之间添加逗号或其他符号。 常见的做法是手写 for 循环并通过索引判断。但这种方式不仅代码丑陋，且在处理动态列表时极其容易出错（例如忘记最后一个元素不加分隔符）。 intersperse 是一个极简的扩展库。它通过为 Iterable 增加一个极其直观的方法，彻底解决了“元素间插入”这一烦人的小问题。 一、核心操作图解 intersperse 提供了一种“无感插入”的流式处理方式。 [A, B, C] (原始数据) intersperse(

By Ne0inhk
从虚拟地址到物理页框：Linux 页表与内存管理全解析

从虚拟地址到物理页框：Linux 页表与内存管理全解析

前言：虚拟内存、物理内存与页表，是现代操作系统内存管理的三大核心。本文将从原理、结构、映射机制等角度，系统讲解虚拟地址空间、页表工作方式、物理内存管理，带你彻底理解程序背后的内存世界。 文章目录 * 一、什么是虚拟内存 * 二、虚拟内存的描述与组织 * 三、页表的优势 * 四、虚拟内存区域划分 * 五、物理空间理解 * 六、页表映射原理 问题引入 为引入今天的话题，我们先来看下面一段程序： #include<stdio.h>#include<sys/types.h>#include<unistd.h>intmain(){int k=10; pid_t id=

By Ne0inhk