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

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

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

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

RBTree

• 一、红黑树的概念
  • 1.1 红黑树的规则（必须牢记）
  • 1.2 为什么最长路径不超过最短路径 2 倍？
  • 1.3 红黑树的效率优势
• 二、红黑树的实现
  • 2.1 红黑树的结构定义
  • 2.2 核心操作：旋转函数
  • 2.3 核心操作：插入函数
    • 2.2.2 情况1：变色
    • 2.2.3 情况2：单旋+变色
    • 2.2.4 情况3：双旋+变色
    • 2.2.5 插入核心问题总结
  • 2.3 红黑树的插入代码实现
  • 2.4 查找红黑树
  • 2.5 遍历打印红黑树
  • 2.6 红黑树高度及大小

一、红黑树的概念

红黑树是自平衡二叉搜索树，通过节点颜色（红 / 黑）和严格的规则约束，保证任意根到叶子的路径长度差不超过 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;}