【C++】模拟实现 红黑树(RBTree)

Ne0inhk

— 15 min read
前言：
在掌握 AVL 树的严格平衡机制后，我们发现其虽能将树高严格控制在 O(logN)，但「高度差≤1」的强约束也带来了明显代价：插入 / 删除操作中频繁的旋转（最多两次双旋）大幅增加了写操作的开销，且每个节点需额外存储平衡因子和父指针，空间利用率较低。

为解决这一问题，红黑树（Red-Black Tree）作为一种近似平衡的二叉搜索树应运而生 —— 它放弃了 AVL 树 “严格平衡” 的要求，转而通过「节点颜色标记 + 5 条核心规则」实现 “黑高一致” 的弱平衡，将任意根到叶子的路径长度差控制在 2 倍以内。这种设计让红黑树在保持 O(logN) 时间复杂度的同时，大幅降低了旋转频率（插入最多 2 次旋转，删除最多 3 次），成为工程实践中更优的选择（C++ STL 的map/set、Linux 内核 CFS 调度器、Java 的TreeMap等均基于红黑树实现）。

本文将从 AVL 树的痛点切入，对比讲解红黑树的核心规则与实现逻辑，重点拆解 “插入修复” 的三种场景（叔叔红、叔叔黑且当前节点为左 / 右孩子），并给出完整可运行的代码实现。通过 “规则理解→代码实现→合法性验证” 的步骤，帮助你掌握红黑树的设计思想与工程落地方式。

RBTree

一、红黑树的概念

红黑树是自平衡二叉搜索树，通过节点颜色（红 / 黑）和严格的规则约束，保证任意根到叶子的路径长度差不超过 2 倍，实现近似平衡，避免普通二叉搜索树退化为链表。

1.1 红黑树的规则（必须牢记）

  • 每个节点非红即黑；
  • 根节点必须是黑色；
  • 红色节点的子节点必须全为黑色（禁止连续红节点）；
  • 任意节点到其所有 NULL 叶子节点的路径，黑色节点数量相同（简称 “黑高一致”）。



1.2 为什么最长路径不超过最短路径 2 倍？

  • 最短路径：全黑节点路径，黑高为 bh；
  • 最长路径：黑红交替路径，长度为 2*bh；
  • 结论：任意路径长度 bh ≤ h ≤ 2*bh，保证了红黑树的近似平衡。

1.3 红黑树的效率优势

  • 时间复杂度：增删查改均为 O(logN)（与 AVL 树同级）；

性能优势：插入 / 删除时旋转次数更少（AVL 树要求严格平衡，红黑树仅 “近似平衡”），实际工程中(如 STL map/set)更常用。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

二、红黑树的实现

2.1 红黑树的结构定义

#include<iostream>#include<utility>usingnamespace std;// 枚举值表示颜色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)// 默认红（插入时默认红，减少黑高破坏）{}};// 红黑树类template<classK,classV>classRBTree{using Node = RBTreeNode<K, V>;public:// 插入接口boolInsert(const pair<K, V>& kv);// 中序遍历（验证二叉搜索树特性）voidInOrder(){_InOrder(_root); cout << endl;}// 查找接口 Node*Find(const K& key);// 获取树的大小intSize(){return_Size(_root);}// 获取树的高度intHeight(){return_Height(_root);}private:// 私有递归函数void_InOrder(Node* root);int_Size(Node* root);int_Height(Node* root);// 旋转函数（核心操作）voidRotateL(Node* parent);// 左旋转voidRotateR(Node* parent);// 右旋转// 验证辅助函数bool_IsValidRBTree(Node* root,int blackCount,int& refBlackCount);private: Node* _root =nullptr;};

2.2 核心操作：旋转函数

旋转是红黑树维护平衡的核心，分为左旋转和右旋转，需保证旋转后仍符合二叉搜索树规则。

// 左旋转：以parent为旋转点，右孩子上位voidRotateL(Node* parent){ Node* subR = parent->_right;// 失衡节点的右孩子（新根） Node* subRL = subR->_left;// 新根的左子树（需要转移） Node* pParent = parent->_parent;// 失衡节点的父节点// 1. 转移subRL：挂到parent的右子树 parent->_right = subRL;if(subRL) subRL->_parent = parent;// 2. 父节点降级：parent作为subR的左孩子 subR->_left = parent; parent->_parent = subR;// 3. 链接新根到原父节点if(pParent ==nullptr){ _root = subR; subR->_parent =nullptr;}else{if(pParent->_left == parent) pParent->_left = subR;else pParent->_right = subR; subR->_parent = pParent;}// 4. 重置平衡因子 parent->_bf = subR->_bf =0;}// 右旋转：以parent为旋转点，左孩子上位voidRotateR(Node* parent){ Node* subL = parent->_left;// 失衡节点的左孩子（新根） Node* subLR = subL->_right;// 新根的右子树（需要转移） Node* pParent = parent->_parent;// 失衡节点的父节点// 1. 转移subLR：挂到parent的左子树 parent->_left = subLR;if(subLR) subLR->_parent = parent;// 2. 父节点降级：parent作为subL的右孩子 subL->_right = parent; parent->_parent = subL;// 3. 链接新根到原父节点if(pParent ==nullptr){// 原parent是根节点，更新根 _root = subL; subL->_parent =nullptr;}else{if(pParent->_left == parent) pParent->_left = subL;else pParent->_right = subL; subL->_parent = pParent;}// 4. 重置平衡因子（旋转后子树高度恢复，BF归0） parent->_bf = subL->_bf =0;}

2.3 核心操作：插入函数

  1. 插入一个值按二叉搜索树规则进行插入，插入后我们只需要观察是否符合红黑树的4条规则
  2. 如果是空树插入，新增结点是黑色结点。如果是非空树插入，新增结点必须红色结点，因为非空树插入，新增黑色结点就破坏了规则4，规则4是很难维护的
  3. 非空树插入后，新增结点必须红色结点，如果父亲结点是黑色的，则没有违反任何规则，插入结束
  4. 非空树插入后，新增结点必须红色结点，如果父亲结点是红色的，则违反规则3。进一步分析，c是红色，p为红，g必为黑，这三个颜色都固定了，关键的变化看u的情况，需要根据u分为以下几种情况分别处理。
    说明：说明：下图中假设我们把新增结点标识为c(cur)，c的父亲标识为p(parent)，p的父亲标识为g(grandfather),p的兄弟标识为u(uncle)。

2.2.2 情况1：变色

插入的c为红，p为红，g为黑，u存在且为红，则将p和u变黑，g变红。然后把g当作新的c，继续往上更新。

分析：因为p和u都是红色，g是黑色，把p和u变黑，左边子树路径各增加一个黑色结点，g再变红，相当于保持g所在子树的黑色结点的数量不变，同时解决了c和p连续红色结点的问题，需要继续往上更新是因为，g是红色，如果g的父亲还是红色，那么就还需要继续处理；如果g的父亲是黑色，则处理结束了；如果g就是整棵树的根，再把g变回黑色。

情况1只变色，不旋转。所以无论c是p的左还是右，p是g的左还是右，都是上面的变色处理方式。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
boolinsert(const pair<K, V>& kv){if(_root){ _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)// 分两种情况：1.叔叔在左边 2.叔叔在右边{// 条件parent：防止空指针（_root节点的父亲为NULL） Node* grandfater = parent->_parent;if(parent = grandfater->_left)// 叔叔在右边{// g// p u Node* uncle = grandfater->_right;if(uncle && uncle->_col == RED)// 变色过程{ parent->_col = uncle->_col = BLACK; grandfater->_col = RED;// 继续向上处理，最坏结果处理到根 cur = grandfater; parent = cur->_parent;}}else// 叔叔在左边{// g// u p Node* uncle = grandfater->_left;}} _root->_col = BLACK;// _root节点必为BLACKreturntrue;}

更复杂情况（了解即可）

  • 图1将以上类似的处理进行了抽象表达，d/e/f代表每条路径拥有hb个黑色结点的子树，a/b代表每条路径拥有hb-1个黑色结点的根为红的子树，hb>=0。

图2/图3，分别展示了hb==0/hb==1的具体情况组合分析，当hb等于2时，这里组合情况上百亿种，这些样例是帮助我们理解，不论情况多少种，多么复杂，处理方式一样的，变色再继续往上处理即可，所以我们只需要看抽象图即可。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传


外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

2.2.3 情况2：单旋+变色

c为红，p为红，g为黑，u不存在或者u存在且为黑。

  • u不存在，则c一定是新增节点。
  • u存在且为黑，c一定不是新增节点，c之前是黑色的，是在c的子树中插入，符合情况1，变色将c从黑色变成红色，更新上来的。
p必须变黑，连续红色节点的问题，u不存在或者是黑色的，这里单纯的变色无法解决问题，需要旋转+变色
 g p u c

如果p是g的左，c是p的左，那么以g为旋转点进行右单旋，再把p变黑，g变红即可。p变成课这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为p的父亲是黑色还是红色或者空都不违反规则。

 g p u c

如果p是g的右，c是p的右，那么以g为旋转点进行左单旋，再把p变黑，g变红即可。p变成课这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为p的父亲是黑色还是红色或者空都不违反规则。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

2.2.4 情况3：双旋+变色

c为红，p为红，g为黑，u不存在或者u存在且为黑，u不存在，则c一定是新增结点，u存在且为黑，则c一定不是新增，c之前是黑色的，是在c的子树中插入，符合情况1，变色将c从黑色变成红色，更新上来的。

p必须变黑，才能解决，连续红色结点的问题，u不存在或者是黑色的，这里单纯的变色无法解决问题，需要旋转+变色。
 g p u c

如果p是g的左，c是p的右，那么先以p为旋转点进行左单旋，再以g为旋转点进行右单旋，再把c变
黑，g变红即可。c变成课这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为c的父亲是黑色还是红色或者空都不违反规则。

 g p u c

如果p是g的右，c是p的左，那么先以p为旋转点进行右单旋，再以g为旋转点进行左单旋，再把c变
黑，g变红即可。c变成课这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为c的父亲是黑色还是红色或者空都不违反规则。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

2.2.5 插入核心问题总结

关键看u(叔叔)，p(父亲)和g(爷爷)是固定的，方向不一定固定分两种情况，if(情况1)、else(情况2)，但颜色一定是固定的。

  • u(叔叔)存在且为红，就可以和p(父亲)一起分担颜色，把u(叔叔)和p(父亲)变黑，g(爷爷)变红
  • 单旋情况下：u(叔叔)不存在 / u(叔叔)存在且为黑，u(叔叔)没办法分担只能变色，让p(父亲)变黑为顶
  • 双旋情况下：u(叔叔)不存在 / u(叔叔)存在且为黑，u(叔叔)没办法分担只能变色，让c(新节点)变黑为顶

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)// 分两种情况：1.叔叔在左边 2.叔叔在右边{// 条件parent：防止空指针（_root节点的父亲为NULL） Node* grandfater = parent->_parent;if(parent = grandfater->_left)// 叔叔在右边{// g// p u Node* uncle = grandfater->_right;if(uncle && uncle->_col == RED)// 叔叔存在且为红色（变色）{ parent->_col = uncle->_col = BLACK; grandfater->_col = RED;// 继续向上处理，最坏结果处理到根 cur = grandfater; parent = cur->_parent;}else// 叔叔不存在，或存在且为黑（旋转+变色）{if(cur == parent->_left)// c在父亲左边，构成直线，只单旋一次{// g// p u// cRotateR(grandfater); parent->_col = BLACK; grandfater->_col = RED;}else// c在父亲右边，构成折现，需要双旋{// g// p u// cRotateL(parent);RotateR(grandfater); cur->_col = BLACK; grandfater->_col = RED;}break;}}else// 叔叔在左边（类似上列代码）{// g// u p Node* uncle = grandfater->_left;// 叔叔存在且为红（变色即可）if(uncle && uncle->_col == RED){ parent->_col = uncle->_col = BLACK; grandfater->_col = RED;// 继续向上处理 cur = grandfater; parent = cur->_parent;}else// 叔叔不存在，或存在且为黑（旋转+变色）{// g// u p// cif(cur == parent->_right){RotateL(grandfater); parent->_col = BLACK; grandfater->_col = RED;}else{// g// u p// cRotateR(parent);RotateL(grandfater); cur->_col = BLACK; grandfater->_col = RED;}break;}}} _root->_col = BLACK;// _root节点必为BLACKreturntrue;}

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 遍历打印红黑树

/*public*/voidInOrder(){_InOrder(_root); cout << endl;}/*private*/void_InOrder(Node* root){if(root ==nullptr){return;}_InOrder(root->_left); cout << root->_kv.first <<":"<< root->_kv.second << endl;_InOrder(root->_right);}

2.6 红黑树高度及大小

/*public*/intSize(){return_Size(_root);}intHeight(){return_Height(_root);}/*private*/int_Height(Node* root){if(root ==nullptr)return0;intleftHeight(root->_left);intrightHeight(root->_right);return rightHeight > leftHeight ? leftHeight +1: rightHeight +1;}int_Size(Node* root){if(root ==nullptr)return0;return_Size(root->_left)+_Size(root->_right)+1;}

Read more

【C++：C++11收尾】解构C++可调用对象：从入门到精通，掌握function包装器与bind适配器包装器详解

【C++：C++11收尾】解构C++可调用对象：从入门到精通，掌握function包装器与bind适配器包装器详解

🎬 个人主页：艾莉丝努力练剑 ❄专栏传送门：《C语言》《数据结构与算法》《C/C++干货分享&学习过程记录》 《Linux操作系统编程详解》《笔试/面试常见算法：从基础到进阶》《Python干货分享》 ⭐️为天地立心，为生民立命，为往圣继绝学，为万世开太平 🎬 艾莉丝的简介： 🎬 艾莉丝的C++专栏简介： 文章目录 * C++学习阶段的三个参考文档 * 8 ~> 包装器 * 8.1 function * 8.1.1 结构 * 8.1.2 概念 * 8.1.3 function实现 * 8.1.4 重写逆波兰表达式求值 * 8.2 bind

By Ne0inhk
【C++】菱形继承为何会引发二义性？虚继承如何破解？

【C++】菱形继承为何会引发二义性？虚继承如何破解？

🎬 个人主页：MSTcheng · ZEEKLOG 🌱 代码仓库 ：MSTcheng · Gitee 🔥 精选专栏: 《C语言》 《数据结构》 《C++由浅入深》 💬座右铭：路虽远行则将至，事虽难做则必成！ 前言：在之前的文章中，我们已经介绍了继承的相关内容，但有些重要概念尚未涉及，例如菱形继承、虚继承以及二义性等问题。本文将重点探讨这些内容。加粗样式 文章目录 * 一、多继承及菱形继承问题 * 1.1单继承 * 1.2多继承 * 1.3虚继承 * 1.3.1为什么通过虚继承可以将Person部分成员提取出来？ * 1.3.2虚继承的构造初始化顺序 * 二、总结 一、多继承及菱形继承问题 1.1单继承 单继承：⼀个派⽣类只有⼀个直接基类时称这个继承关系为单继承。 第一种情形： #include<

By Ne0inhk
【C++】unordered系列容器使用及封装

【C++】unordered系列容器使用及封装

目录 一、unordered_map和unordered_set的使用 1. unordered_set系列的使用 1.1 unordered_set和unordered_multiset参考文档 1.2 unordered_set类的介绍 1.3 unordered_set和set的使用差异 1.4 unordered_map和map的使用差异 1.5 unordered_multimap/unordered_multiset 1.6 unordered_xxx的哈希相关接口 二、用哈希表封装myunordered_map和myunordered_set 1. 源码及框架分析 2. 模拟实现unordered_map和unordered_set 2.1 实现出复用哈希表的框架，并支持insert 2.

By Ne0inhk
扒透 STL 底层！map/set 如何封装红黑树？迭代器逻辑 + 键值限制全手撕----《Hello C++ Wrold!》(23)--(C/C++)

扒透 STL 底层！map/set 如何封装红黑树？迭代器逻辑 + 键值限制全手撕----《Hello C++ Wrold!》(23)--(C/C++)

文章目录 * 前言 * map和set的封装 * 底层红黑树的模拟实现 * 迭代器的模拟实现 前言 你是不是也有过这种 “知其然不知其所以然” 的困惑： 用 map 存键值对、用 set 去重排序时很顺手，但一被问 “map 的 [] 怎么既插入又访问”“set 为啥不能改元素”“它们底层的红黑树到底存的啥”，就瞬间卡壳？甚至看 STL 源码时，被 “KeyOfT”“迭代器 ++ 逻辑” 绕得晕头转向？ 其实 map 和 set 的本质，就是对红黑树的 “定制化封装” —— 红黑树是 “通用骨架”，map 和 set 通过 “提取键的规则（KeyOfT）”“迭代器权限控制”“键值修改限制”，分别适配了 “键值对存储”

By Ne0inhk