C++手撕红黑树：从0到200行，拿下STL map底层核心

Ne0inhk

— 9 min read
C++手撕红黑树：从0到200行，拿下STL map底层核心

文章目录

C++手撕红黑树：从0到200行，拿下STL map底层核心

1. 红黑树的概念

红黑树是一棵二叉搜索树，它的每个结点增加一个存储位来表示结点的颜色，可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。

1.1 红黑树的规则

  1. 每个结点不是红色就是黑色。
  2. 根结点是黑色的。
  3. 如果一个结点是红色的，则它的两个孩子结点必须是黑色的（即任意一条路径不会有连续的红色结点）。
  4. 对于任意一个结点，从该结点到其所有 NULL 结点的简单路径上，均包含相同数量的黑色结点。
说明：《算法导论》等书籍中补充了“每个叶子结点（NIL）都是黑色的”规则。这里所指的叶子结点不是传统意义上的叶子结点，而是我们说的空结点（NIL），也叫外部结点。引入 NIL 是为了准确标识所有路径，但在实现细节中通常忽略 NIL 结点，了解概念即可。
在这里插入图片描述


在这里插入图片描述

1.2 红黑树如何确保最长路径不超过最短路径的2倍？

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

1.3 红黑树的效率

假设 N 是红黑树中结点数量，h 是最短路径的长度，那么：

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

由此推出 h ≈ logN，即红黑树增删查改的最坏情况是走最长路径 2*logN，时间复杂度仍为 O(logN)。

红黑树的表达相对 AVL 树要抽象一些。AVL 树通过高度差直观地控制平衡，而红黑树通过4条规则的颜色约束间接实现了近似平衡。两者效率属于同一档次，但红黑树在插入相同数量的结点时旋转次数更少，因为它对平衡的控制没那么严格。

在这里插入图片描述

2. 红黑树的实现

2.1 红黑树的结构

// 枚举值表示颜色enumColour{ RED, BLACK };// 这里默认按 key/value 结构实现template<classK,classV>structRBTreeNode{// 更新控制平衡需要加入 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<classK,classV>classRBTree{typedef RBTreeNode<K, V> Node;public:// ...private: Node* _root =nullptr;};

2.2 红黑树的插入

2.2.1 插入的大概过程

  1. 按二叉搜索树规则插入新结点。
  2. 如果是空树插入，新增结点为黑色；如果是非空树插入，新增结点必须为红色（否则会破坏规则4）。
  3. 非空树插入后，如果父亲结点是黑色，则插入结束；如果父亲结点是红色，则违反规则3，需要进一步处理。
约定：c 为当前结点（cur），p 为父亲（parent），g 为祖父（grandfather），u 为叔叔（uncle，即 p 的兄弟）。

2.2.2 情况1：变色

条件：c 为红，p 为红，g 为黑，u 存在且为红。
处理：将 p 和 u 变黑，g 变红，然后把 g 当作新的 c，继续往上更新。

  • 无论 c 是 p 的左还是右，p 是 g 的左还是右，处理方法相同。

如果 g 是根，最后再将 g 变回黑色。

在这里插入图片描述

2.2.3 情况2：单旋 + 变色

条件：c 为红，p 为红，g 为黑，u 不存在或为黑。

  • 如果 u 不存在，c 一定是新增结点。
  • 如果 u 存在且为黑，c 一定不是新增，而是由情况1变色更新上来的。

处理：

  • p 是 g 的左，c 是 p 的左：以 g 为旋转点进行右单旋，再将 p 变黑，g 变红。

p 是 g 的右，c 是 p 的右：以 g 为旋转点进行左单旋，再将 p 变黑，g 变红。

在这里插入图片描述

2.2.4 情况3：双旋 + 变色

条件：c 为红，p 为红，g 为黑，u 不存在或为黑，且 c 与 p 的方向不一致。

处理：

  • p 是 g 的左，c 是 p 的右：先以 p 为旋转点进行左单旋，再以 g 为旋转点进行右单旋，最后将 c 变黑，g 变红。

p 是 g 的右，c 是 p 的左：先以 p 为旋转点进行右单旋，再以 g 为旋转点进行左单旋，最后将 c 变黑，g 变红。

在这里插入图片描述

2.3 红黑树的插入代码实现

boolInsert(const pair<K, V>& kv){if(_root ==nullptr){ _root =newNode(kv); _root->_col = BLACK;returntrue;} 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;}} cur =newNode(kv); cur->_col = RED;// 新增结点为红色if(parent->_kv.first < kv.first){ parent->_right = cur;}else{ parent->_left = cur;} cur->_parent = parent;while(parent && parent->_col == RED){ Node* grandfather = parent->_parent;if(parent == grandfather->_left){ Node* uncle = grandfather->_right;if(uncle && uncle->_col == RED){// 情况1：叔叔存在且为红 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent;}else{// 情况2/3：叔叔不存在或为黑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{ Node* uncle = grandfather->_left;if(uncle && uncle->_col == RED){// 情况1：叔叔存在且为红 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent;}else{// 情况2/3：叔叔不存在或为黑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;}
旋转代码与 AVL 树相同，只需调整指针，无需更新平衡因子。

2.4 红黑树的查找

按二叉搜索树逻辑实现，时间复杂度 O(logN)。

Node*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.5 红黑树的验证

不能简单地通过检查最长路径不超过最短路径2倍来验证，因为即使满足该条件，颜色规则也可能被破坏。必须检查4点规则：

  1. 根结点为黑色。
  2. 无连续红色结点。
  3. 每条路径黑色结点数量相同。
boolCheck(Node* root,int blackNum,constint refNum){if(root ==nullptr){if(refNum != blackNum){ cout <<"存在黑色结点数量不相等的路径"<< endl;returnfalse;}returntrue;}if(root->_col == RED && root->_parent->_col == RED){ cout << root->_kv.first <<"存在连续的红色结点"<< endl;returnfalse;}if(root->_col == BLACK){ blackNum++;}returnCheck(root->_left, blackNum, refNum)&&Check(root->_right, blackNum, refNum);}boolIsBalance(){if(_root ==nullptr)returntrue;if(_root->_col == RED)returnfalse;// 参考值：最左路径的黑色结点数int refNum =0; Node* cur = _root;while(cur){if(cur->_col == BLACK)++refNum; cur = cur->_left;}returnCheck(_root,0, refNum);}

Read more

Nginx面试宝典【刷题系列】

Nginx面试宝典【刷题系列】

文章目录 * 1、nginx是如何实现高并发的？ * 2、Nginx如何处理HTTP请求？ * 3、使用“反向代理服务器”的优点是什么? * 4、列举Nginx服务器的最佳用途。 * 5、Nginx服务器上的Master和Worker进程分别是什么? * 6、什么是C10K问题? * 7、请陈述stub_status和sub_filter指令的作用是什么? * 8、为什么不使用多线程？ * 9、为什么要做动、静分离？ * 10、ngx_http_upstream_module的作用是什么? 1、nginx是如何实现高并发的？ 答：一个主进程，多个工作进程，每个工作进程可以处理多个请求，每进来一个request，会有一个 worker 进程去处理。但不是全程的处理，处理到可能发生阻塞的地方，比如向上游（后端）服务器转发 request ，并等待请求返回。那么，这个处理的 worker 继续处理其他请求，

By Ne0inhk
基于SpringBoot和Leaflet的区域冲突可视化-以伊以冲突为例

基于SpringBoot和Leaflet的区域冲突可视化-以伊以冲突为例

目录 前言 一、相关空间要素 1、区域冲突目标查询 2、域外第三国势力查询 二、前后端应用实现 1、后台查询实现 2、前端Leaflet可视化 三、成果分析 1、冲突双方 2、域外势力 四、总结 前言         在当今全球化时代，地区局势成为国际社会关注的焦点。其中，以色列与伊朗之间的冲突持续多年，局势复杂且影响深远。这种冲突不仅关乎两国人民的安危，还对地区稳定、国际能源、政治格局等诸多方面产生剧烈冲击。如何能直观、高效地呈现伊以冲突的态势，为冲突分析、预防及应对提供有力支持，是一个亟待解决的问题。传统上，冲突信息主要以文字报道、统计图表等形式传播。然而，这些方式在展现冲突的地理分布、动态变化等方面存在诸多局限。比如，文字描述难以让人清晰把握冲突发生的准确位置及其周边环境；统计图表虽能呈现数据，但缺乏地理空间上的直观关联。因此，构建一个可视化系统来呈现区域冲突，显得尤为关键。

By Ne0inhk
KingbaseES数据库：ksql 命令行从建表到删表实战（含避坑指南）

KingbaseES数据库：ksql 命令行从建表到删表实战（含避坑指南）

KingbaseES数据库：ksql 命令行从建表到删表实战（含避坑指南） 本文围绕 KingbaseES 中 ksql 命令行操作表展开，涵盖表 “创建→查看→数据增删改查→结构修改→删除” 全生命周期。前置准备需连接数据库并切换目标模式，可选确认表空间；创建表要明确数据类型与约束，含基础单表、进阶复合主键表示例；查看表结构可通过 \dt、\d、\d + 命令分别获取表列表、基本结构、详细信息；数据操作聚焦 INSERT（单条 / 批量）、SELECT（全量 / 条件 / 排序）、UPDATE（必加 WHERE）、DELETE（必加 WHERE）；结构修改含增列、改列、删列、加约束、改表名；还梳理了三类常见报错解决方案。全文搭配实操命令与验证方法，助力新手快速掌握表操作核心技巧。

By Ne0inhk