前言:
在掌握 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.2.2 情况1:变色
- 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 红黑树的结构定义
1#include <iostream> 2#include <utility> 3using namespace std; 4 5// 枚举值表示颜色 6enum Colour 7{ 8 RED, 9 BLACK 10}; 11 12// 红黑树节点结构 13template<class K, class V> 14struct RBTreeNode 15{ 16 pair<K, V> _kv; // 键值对 17 RBTreeNode<K, V>* _left; // 左孩子 18 RBTreeNode<K, V>* _right; // 右孩子 19 RBTreeNode<K, V>* _parent; // 父节点(红黑树必须维护父节点) 20 Colour _col; // 节点颜色 21 22 // 构造函数 23 RBTreeNode(const pair<K, V>& kv) 24 :_kv(kv) 25 , _left(nullptr) 26 , _right(nullptr) 27 , _parent(nullptr) 28 , _col(RED) // 默认红(插入时默认红,减少黑高破坏) 29 { } 30}; 31 32// 红黑树类 33template<class K, class V> 34class RBTree 35{ 36 using Node = RBTreeNode<K, V>; 37public: 38 // 插入接口 39 bool Insert(const pair<K, V>& kv); 40 // 中序遍历(验证二叉搜索树特性) 41 void InOrder() { _InOrder(_root); cout << endl; } 42 // 查找接口 43 Node* Find(const K& key); 44 // 获取树的大小 45 int Size() { return _Size(_root); } 46 // 获取树的高度 47 int Height() { return _Height(_root); } 48 49private: 50 // 私有递归函数 51 void _InOrder(Node* root); 52 int _Size(Node* root); 53 int _Height(Node* root); 54 // 旋转函数(核心操作) 55 void RotateL(Node* parent); // 左旋转 56 void RotateR(Node* parent); // 右旋转 57 // 验证辅助函数 58 bool _IsValidRBTree(Node* root, int blackCount, int& refBlackCount); 59 60private: 61 Node* _root = nullptr; 62}; 63
2.2 核心操作:旋转函数
旋转是红黑树维护平衡的核心,分为左旋转和右旋转,需保证旋转后仍符合二叉搜索树规则。
1// 左旋转:以parent为旋转点,右孩子上位 2void RotateL(Node* parent) 3{ 4 Node* subR = parent->_right; // 失衡节点的右孩子(新根) 5 Node* subRL = subR->_left; // 新根的左子树(需要转移) 6 Node* pParent = parent->_parent; // 失衡节点的父节点 7 8 // 1. 转移subRL:挂到parent的右子树 9 parent->_right = subRL; 10 if (subRL) 11 subRL->_parent = parent; 12 13 // 2. 父节点降级:parent作为subR的左孩子 14 subR->_left = parent; 15 parent->_parent = subR; 16 17 // 3. 链接新根到原父节点 18 if (pParent == nullptr) 19 { 20 _root = subR; 21 subR->_parent = nullptr; 22 } 23 else 24 { 25 if (pParent->_left == parent) 26 pParent->_left = subR; 27 else 28 pParent->_right = subR; 29 subR->_parent = pParent; 30 } 31 32 // 4. 重置平衡因子 33 parent->_bf = subR->_bf = 0; 34} 35 36// 右旋转:以parent为旋转点,左孩子上位 37void RotateR(Node* parent) 38{ 39 Node* subL = parent->_left; // 失衡节点的左孩子(新根) 40 Node* subLR = subL->_right; // 新根的右子树(需要转移) 41 Node* pParent = parent->_parent; // 失衡节点的父节点 42 43 // 1. 转移subLR:挂到parent的左子树 44 parent->_left = subLR; 45 if (subLR) 46 subLR->_parent = parent; 47 48 // 2. 父节点降级:parent作为subL的右孩子 49 subL->_right = parent; 50 parent->_parent = subL; 51 52 // 3. 链接新根到原父节点 53 if (pParent == nullptr) 54 { 55 // 原parent是根节点,更新根 56 _root = subL; 57 subL->_parent = nullptr; 58 } 59 else 60 { 61 if (pParent->_left == parent) 62 pParent->_left = subL; 63 else 64 pParent->_right = subL; 65 subL->_parent = pParent; 66 } 67 68 // 4. 重置平衡因子(旋转后子树高度恢复,BF归0) 69 parent->_bf = subL->_bf = 0; 70} 71
2.3 核心操作:插入函数
- 插入一个值按二叉搜索树规则进行插入,插入后我们只需要观察是否符合红黑树的4条规则
- 如果是空树插入,新增结点是黑色结点。如果是非空树插入,新增结点必须红色结点,因为非空树插入,新增黑色结点就破坏了规则4,规则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的左还是右,都是上面的变色处理方式。

1bool insert(const pair<K, V>& kv) 2{ 3 if (_root) 4 { 5 _root = new Node(kv); 6 _root->_col = BLACK; 7 8 return true; 9 } 10 11 Node* parent = nullptr; 12 Node* cur = _root; 13 while (cur) 14 { 15 if (cur->_kv.first < kv.first) 16 { 17 parent = cur; 18 cur = cur->_right; 19 } 20 else if(cur->_kv.first > kv.first) 21 { 22 parent = cur; 23 cur = cur->_left; 24 } 25 else 26 { 27 return false; 28 } 29 } 30 31 cur = new Node(kv); 32 cur->_col = RED; // 新节点为红色 33 if (parent->_kv.first < kv.first) 34 parent->_right = cur; 35 else 36 parent->_left = cur; 37 // 链接父亲 38 cur->_parent = parent; 39 40 // 父亲是红色,出现连续的红色节点(需处理) 41 while (parent && parent->_col == RED) // 分两种情况:1.叔叔在左边 2.叔叔在右边 42 { // 条件parent:防止空指针(_root节点的父亲为NULL) 43 Node* grandfater = parent->_parent; 44 45 if (parent = grandfater->_left) // 叔叔在右边 46 { 47 // g 48 // p u 49 Node* uncle = grandfater->_right; 50 if (uncle && uncle->_col == RED) // 变色过程 51 { 52 parent->_col = uncle->_col = BLACK; 53 grandfater->_col = RED; 54 55 // 继续向上处理,最坏结果处理到根 56 cur = grandfater; 57 parent = cur->_parent; 58 } 59 } 60 else // 叔叔在左边 61 { 62 // g 63 // u p 64 Node* uncle = grandfater->_left; 65 } 66 } 67 _root->_col = BLACK; // _root节点必为BLACK 68 69 return true; 70} 71
更复杂情况(了解即可)
- 图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不存在或者是黑色的,这里单纯的变色无法解决问题,需要旋转+变色
1 g 2 p u 3c 4
如果p是g的左,c是p的左,那么以g为旋转点进行右单旋,再把p变黑,g变红即可。p变成课这颗树新的根,这样子树黑色结点的数量不变,没有连续的红色结点了,且不需要往上更新,因为p的父亲是黑色还是红色或者空都不违反规则。
1 g 2 p u 3 c 4
如果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不存在或者是黑色的,这里单纯的变色无法解决问题,需要旋转+变色。
1 g 2 p u 3 c 4
如果p是g的左,c是p的右,那么先以p为旋转点进行左单旋,再以g为旋转点进行右单旋,再把c变
黑,g变红即可。c变成课这颗树新的根,这样子树黑色结点的数量不变,没有连续的红色结点了,且不需要往上更新,因为c的父亲是黑色还是红色或者空都不违反规则。
1 g 2 p u 3 c 4
如果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 红黑树的插入代码实现
1bool Insert(const pair<K, V>& kv) 2{ 3 if (_root == nullptr) 4 { 5 _root = new Node(kv); 6 _root->_col = BLACK; 7 8 return true; 9 } 10 11 Node* parent = nullptr; 12 Node* cur = _root; 13 while (cur) 14 { 15 if (cur->_kv.first < kv.first) 16 { 17 parent = cur; 18 cur = cur->_right; 19 } 20 else if(cur->_kv.first > kv.first) 21 { 22 parent = cur; 23 cur = cur->_left; 24 } 25 else 26 { 27 return false; 28 } 29 } 30 31 cur = new Node(kv); 32 cur->_col = RED; // 新节点为红色 33 if (parent->_kv.first < kv.first) 34 parent->_right = cur; 35 else 36 parent->_left = cur; 37 // 链接父亲 38 cur->_parent = parent; 39 40 // 父亲是红色,出现连续的红色节点(需处理) 41 while (parent && parent->_col == RED) // 分两种情况:1.叔叔在左边 2.叔叔在右边 42 { // 条件parent:防止空指针(_root节点的父亲为NULL) 43 Node* grandfater = parent->_parent; 44 45 if (parent = grandfater->_left) // 叔叔在右边 46 { 47 // g 48 // p u 49 Node* uncle = grandfater->_right; 50 if (uncle && uncle->_col == RED) // 叔叔存在且为红色(变色) 51 { 52 parent->_col = uncle->_col = BLACK; 53 grandfater->_col = RED; 54 55 // 继续向上处理,最坏结果处理到根 56 cur = grandfater; 57 parent = cur->_parent; 58 } 59 else // 叔叔不存在,或存在且为黑(旋转+变色) 60 { 61 if (cur == parent->_left) // c在父亲左边,构成直线,只单旋一次 62 { 63 // g 64 // p u 65 // c 66 RotateR(grandfater); 67 parent->_col = BLACK; 68 grandfater->_col = RED; 69 } 70 else// c在父亲右边,构成折现,需要双旋 71 { 72 // g 73 // p u 74 // c 75 RotateL(parent); 76 RotateR(grandfater); 77 cur->_col = BLACK; 78 grandfater->_col = RED; 79 } 80 81 break; 82 } 83 } 84 else // 叔叔在左边(类似上列代码) 85 { 86 // g 87 // u p 88 Node* uncle = grandfater->_left; 89 90 // 叔叔存在且为红(变色即可) 91 if (uncle && uncle->_col == RED) 92 { 93 parent->_col = uncle->_col = BLACK; 94 grandfater->_col = RED; 95 96 // 继续向上处理 97 cur = grandfater; 98 parent = cur->_parent; 99 } 100 else// 叔叔不存在,或存在且为黑(旋转+变色) 101 { 102 // g 103 // u p 104 // c 105 if (cur == parent->_right) 106 { 107 RotateL(grandfater); 108 parent->_col = BLACK; 109 grandfater->_col = RED; 110 } 111 else 112 { 113 // g 114 // u p 115 // c 116 RotateR(parent); 117 RotateL(grandfater); 118 cur->_col = BLACK; 119 grandfater->_col = RED; 120 } 121 122 break; 123 } 124 } 125 } 126 _root->_col = BLACK; // _root节点必为BLACK 127 128 return true; 129} 130
2.4 查找红黑树
按二叉搜索树逻辑实现即可,搜索效率为O(logN)
1Node* Find(const K& key) 2{ 3 Node* cur = _root; 4 while (cur) 5 { 6 if (cur->_kv.first < key) 7 { 8 cur = cur->_right; 9 } 10 else if (cur->_kv.first > key) 11 { 12 cur = cur->_left; 13 } 14 else 15 { 16 return cur; 17 } 18 } 19 20 return nullptr; 21} 22
2.5 遍历打印红黑树
1/*public*/ 2void InOrder() 3{ 4 _InOrder(_root); 5 cout << endl; 6} 7 8/*private*/ 9void _InOrder(Node* root) 10{ 11 if (root == nullptr) 12 { 13 return; 14 } 15 16 _InOrder(root->_left); 17 cout << root->_kv.first << ":" << root->_kv.second << endl; 18 _InOrder(root->_right); 19} 20
2.6 红黑树高度及大小
1/*public*/ 2int Size() 3{ 4 return _Size(_root); 5} 6 7int Height() 8{ 9 return _Height(_root); 10} 11 12/*private*/ 13int _Height(Node* root) 14{ 15 if (root == nullptr) 16 return 0; 17 int leftHeight(root->_left); 18 int rightHeight(root->_right); 19 return rightHeight > leftHeight ? leftHeight + 1 : rightHeight + 1; 20} 21 22int _Size(Node* root) 23{ 24 if (root == nullptr) 25 return 0; 26 27 return _Size(root->_left) + _Size(root->_right) + 1; 28} 29
《【C++】模拟实现 红黑树(RBTree)》 是转载文章,点击查看原文。




