当前位置： 首页 > news >正文

深入解析：C++红黑树：理论与实践相结合的平衡艺术

news 2026/3/26 23:38:10

目录

1 红黑树的概念

1.1 红黑树的4条规则

1.2 红黑树是如何做到最长路径不超过最短路径的两倍的？

1.3 红黑树的效率

2 红黑树的实现

2.1 红黑树的结构

2.2 红黑树的插入

2.2.1 红黑树插入一个值的过程

2.2.2 情况1：变色

2.2.3 情况2：单旋+变色

2.2.4 情况3：双旋+变色

2.3 红黑树的插入代码实现

2.4 红黑树的查找

2.5 红黑树的验证

1 红黑树的概念

红黑树是一颗二叉搜索树，它的每个节点可以是红色或者黑色。通过对任意一条从根节点到叶子节点的路径上各个节点的颜色进行约束。红黑树确保没有一条路径的长度会比其他路径的长度多出2倍。所以是接近平衡的。

1.1 红黑树的4条规则

  • 规则一：每个节点不是红色就是黑色
  • 规则二：根节点是黑色的
  • 规则三：如果一个节点是红色的，那么它两个孩子节点必须是黑色的，也就是说任意一条路径都不会有连续的红色节点
  • 规则四：对于任意一个节点，从该节点到其所有NULL节点的路径上，均包含相同数量的黑色节点

一些红黑树的样例：

1.2 红黑树是如何做到最长路径不超过最短路径的两倍的？

  • 由规则4可知，从根到NULL节点的每条路径都有相同的黑色节点，所以在一些场景下，最短路径是全是黑色节点的路径，假设最短路径长度是h
  • 由规则2和规则3可以知道，任何一条路径不会有连续的红色节点，所以极端场景下，最长路径就是一黑一红间隔组成，那么最长路径的长度就是2*h
  • 综合红黑树的4点规则，全黑最短路径和一黑一红的最长路径并不是在每棵红黑树都存在。假设任意一条从根节点到NULL节点的路径长度是x，那么h<=x<=2*h

由此得出红黑树最长路径不超过最短路径的2倍

1.3 红黑树的效率

假设N是红黑树中节点的数量，h是最短路径的长度，那么2^h-1<=N<2^(2h)-1，由此得出h≈logN，也就意味着红黑树的增删查改的最长路径是2*logN，时间复杂度就是O(logN).

2 红黑树的实现

2.1 红黑树的结构

创建一个头文件RBTree.h，先搭建好框架，在public中实现操作：

enum Colour
{RED,//红BLACK//黑
};
//这里默认按照key/value结构实现
template
struct RBTreeNode
{Colour _col;pair _kv;RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;RBTreeNode(const pair& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){ }
};
template
class RBTree
{typedef RBTreeNode Node;
public:
private:Node* _root = nullptr;
};

2.2 红黑树的插入

2.2.1 红黑树插入一个值的过程

1 插入一个值按照二叉搜索树的规则进行插入，插入后只需要观察是否符合红黑树的4条规则

2 如果是空树插入，新增节点是黑色节点，如果是非空树插入，新增节点必须是红色节点，因为非空树插入黑色节点会破坏规则4.

3 非空树插入后，新增节点必须为红色节点，如果父亲节点是黑色的，则满足所有规则，插入结束

4 非空树插入后，新增节点必须是红色节点，如果父亲节点是红色的，违反规则3。进一步分析，插入节点是红色，它的父亲节点为红，父亲节点的父亲节点必为黑，这三个颜色都是固定的，主要是看父亲节点的兄弟节点的变化情况，下面就根据情况分别处理

这里说明一下，下文中将新增节点标识为c(cur)，c的父亲节点标识为p(parent)，p的父亲节点标识为g(grandfather)，p的兄弟节点标识(uncle)。

2.2.2 情况1：变色

这种情况是c为红，p为红，g为黑，u存在且为红。插入后将p和u变黑，g变红。再把g当作新的c，继续向上更新

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

这种情况只变色，不旋转，c是p的左还是右不影响。结合文字说明和图像便于理解：

2.2.3 情况2：单旋+变色

c为红，p为红，g为黑，u不存在或者u存在且为黑，u不存在，则c一定是新增节点，u存在且为黑，c不是新增，是c的子树新增后c变成了红色，更新上来的。

说明，p变黑才能解决，需要旋转加变色

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

这里方框内都是子树，是抽象出来成方框，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变成了红色，更新上来的。

说明，p变黑才能解决，需要旋转加变色

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

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

2.3 红黑树的插入代码实现

了解完原理之后，我们就可以编写代码来实现插入操作了。

bool Insert(const pair& kv)
{if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;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 false;}}cur = new Node(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){//g//p		//uNode* uncle = grandfather->_right;if (uncle && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//然后向上处理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_left){//g//p		//u//cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//g//p		//u//cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{//g//u		//pNode* uncle = grandfather->_left;//叔叔节点存在且为红，变色即可if (uncle&&uncle->_col==RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上处理cur = grandfather;parent = cur->_parent;}else//叔叔节点不存在，或者存在且为黑{if (cur == parent->_right){//g//u		//p//cRotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//g//u		//p//cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;
}
//右单旋
void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* pParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (pParent == nullptr){_root = subL;subL->_parent = nullptr;}else{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 (pParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (pParent->_left == parent){pParent->_left = subR;}else{pParent->_right = subR;}subR->_parent = pParent;}
}

2.4 红黑树的查找

查找红黑树的节点比较简单，直接按照二叉搜索树的逻辑实现即可，搜索效率为O(logN)

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;
}

2.5 红黑树的验证

要验证一个数是否是红黑树，这里我们获取最长路径和最短路径，然后检查最长路径不超过最短路径的两倍是行不通的，原因是即使满足这个条件，红黑树也可能颜色不满足规则，所以还是去对四点规则进行一一检查，满足4点规则，一定能保证最长路径不超过最短路径的2倍。

  • 1 对于规则1保证红黑树节点不是黑色就是红色
  • 2 对于规则2直接检查根节点即可
  • 3 对于规则3前序遍历检查，遇到红色节点时，查它的孩子节点不太方便，因为孩子节点可能有两个，反过来检查父亲节点的颜色就方便许多
  • 4 规则4前序遍历，遍历过程中记录黑色节点数量，记录一条路径的黑色节点数量，然后其他路径黑色节点的数量作为参考值，依次比较即可。

代码实现：

bool Check(Node* root, int blackNum, const int refNum)
{if (root == nullptr){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);
}
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);
}

3 完整代码实现

enum Colour
{RED,BLACK
};
template
struct RBTreeNode
{Colour _col;pair _kv;RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;RBTreeNode(const pair& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){ }
};
template
class RBTree
{typedef RBTreeNode Node;
public:bool Insert(const pair& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;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 false;}}cur = new Node(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){//g//p		//uNode* uncle = grandfather->_right;if (uncle && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//然后向上处理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_left){//g//p		//u//cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//g//p		//u//cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{//g//u		//pNode* uncle = grandfather->_left;//叔叔节点存在且为红，变色即可if (uncle&&uncle->_col==RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上处理cur = grandfather;parent = cur->_parent;}else//叔叔节点不存在，或者存在且为黑{if (cur == parent->_right){//g//u		//p//cRotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//g//u		//p//cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}//右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* pParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (pParent == nullptr){_root = subL;subL->_parent = nullptr;}else{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 (pParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (pParent->_left == parent){pParent->_left = subR;}else{pParent->_right = subR;}subR->_parent = pParent;}}void Inorder(){_InOrder(_root);cout << endl;}int Height(){return _Height(_root);}int Size(){return _Size(_root);}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;}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);}
private:bool Check(Node* root, int blackNum, const int refNum){if (root == nullptr){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 _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}int _Height(Node* root){if (root == nullptr){return 0;}int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}int _Size(Node* root){if (root == nullptr){return 0;}return _Size(root->_left) + _Size(root->_right) + 1;}
private:Node* _root = nullptr;
};

以上就是红黑树的核心知识了，其中插入操作是重点。如果这篇文章对你有用，可以点点赞哦，你的支持就是我写下去的动力。后续会不断地更新知识。

http://www.jsqmd.com/news/304113/

相关文章：

  • 拒绝“一锤子买卖”：2026年铝合金线材靠谱供应商推荐与售后大比拼
  • 2026西南空调风口优质供应商推荐榜
  • 2026年广告转化增长指南：怎么提高广告转化？江南春与分众传媒的实战方法论
  • NMN怎么选？2026年十大品牌排名推荐，揭秘以专利NMNH定义行业上限之作
  • 基于认证、临床与市场反馈的2026年NMN品牌公信力
  • 爆肝整理，性能测试-内存问题定位分析+常见业务场景bug（汇总）
  • 全网热销第一！2026控油蓬松洗发水排行榜，实测效果好推荐
  • NMN品牌怎么选？2026年十大品牌数据化评分指南，全能型选手领跑
  • 2026年护栏网厂家推荐：道路护栏网/铁丝网护栏网/铁路护栏网/防护网围栏网/高速路围栏网/体育场围栏网/体育场护栏网/选择指南
  • NMN品牌哪个好？2026年十大品牌排名推荐，榜首凭借全球唯一GRAS认证领先
  • 专业高新技术企业认定中介机构｜四川汇海立方科技有限公司实力推荐
  • 从“小工”到“专家”，我的软件测试修炼之道
  • 如何高效接入日本股市实时数据？StockTV API 对接实战指南
  • 【开题答辩过程】以《基于uni-app的手账记录小程序的设计与实现》为例，不知道这个选题怎么做的，不知道这个选题怎么开题答辩的可以进来看看
  • 门店管理软件核心功能、选型对比与数字化决策参考
  • 书籍-陈仲金《越南通史》
  • 前端小白别慌：30分钟搞懂CSS浮动布局，代码一贴就跑！
  • Leetcode 107 旋转链表
  • 数据工程新范式：基于 NoETL 语义编织实现自助下钻分析
  • 2026年 吸塑品牌实力推荐榜：专业厂家深度解析，涵盖厚片吸塑、精密吸塑、大型吸塑制品的优质品牌全景测评
  • 2026四川护栏网优质产品推荐榜
  • PWR电源控制
  • 基于容器化的边缘计算网关应用部署实践：Python+MQTT
  • 计算机毕业设计springboot机票订购系统的设计与实现 基于Spring Boot框架的在线机票预订系统开发与实践 利用Spring Boot实现的机票预订平台设计与应用
  • 计算机毕业设计springboot智慧乡村服务平台 基于Spring Boot框架的智慧乡村综合服务平台设计与实现 Spring Boot驱动的智慧乡村服务系统开发与应用
  • 震惊！腾讯企业邮箱在梅州竟有这样的服务商内幕！
  • 全球主流进口电子秤制造商综合实力全景对比与评析
  • 2026年 塑料板材厂家推荐排行榜：ABS/PS/PP/PE/PET/PVC板材，精选高韧性耐腐蚀工程塑料板材优质品牌！
  • 成都附近打印机出租公司、成都附近打印机租赁、成都附近打印机租赁公司、成都周边打印机出租、成都周边打印机租赁、成都彩色打印机出租选择指南
  • 核心技术大起底：看这几家真空石墨炉/碳管炉厂家如何掌握加热体命脉