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

红黑树——如何靠控制色彩实现平衡的？

news 2025/4/26 2:21:37

目录

引言

一、认识红黑树（RBTree）

二、为什么有了AVL树，还要红黑树？

1、AVL树 vs 红黑树，两棵树区别

2、如何选择？

三、红黑树的核心操作

3.1、红黑树结构定义

3.2、插入操作

四、红黑树的验证

五、完整代码

引言

什么是红黑树呢？

红黑树和AVL树一样也是一种平衡搜索树，只不过红黑树控制平衡的方式不一样，是一种近似平衡。 下面会详解他是如何维持平衡的。

一、认识红黑树（RBTree）

红黑树在节点的的定义上新加了个颜色属性，分别是Red和Black,这也是它为什么叫红黑树的原因了。通过节点之间颜色等的限制，来保证任意节点路径的节点个数不超过最短路径的两倍。所以它是近似平衡的。

保证平衡的核心性质：

  1. 每个节点的颜色不是红色就是黑色
  2. 根节点颜色一定是黑的
  3. 任何路径没有连续的红节点
  4. 每条路径上黑色节点的数量相等
  5. 所有叶子（NIL）节点都是黑色的

红黑树示例图：

为什么满足以上性质，就能保证红黑树的最长路径不超过最短路径的两倍呢？

注意性质3、4的条件下：

最短路径：一定是连续的黑色节点

最长路径：一定是红黑节点交替出现。类似下面这种样子：

所以在不破坏红黑树性质的情况下，红黑树的最长路径一定不超过最短路径的两倍。

二、为什么有了AVL树，还要红黑树？

1、AVL树 vs 红黑树，两棵树区别

AVL树特点：

  1. 是一颗严格平衡的二叉搜索树（左右子树高度差不超过1）
  2. 但是为了维护平衡因子，插入/删除可能需要多次旋转，效率O(logN)
  3. 查找效率嘎嘎快

红黑树特点：

  1. 是一颗近似平衡的二叉搜素树（最长路径 <= 2*最短路径）
  2. 当树不平衡时，可以通过变色O(1)+旋转解决，插入/删除的旋转次数少
  3. 查找效率比AVL树慢点

插入效率分析：
假设向AVL树和红黑树分别插入1000个值，两棵树的高度分别是多少呢？

AVL：h \approx log(1000) \approx 10

红黑树：因为最长路径小于最短路径的2倍，所以 h \leq 2*log(1000) \approx 20

假设向AVL树和红黑树分别插入10亿个值，两棵树的高度分别是多少呢？

AVL：h \approx log(1000000000) \approx 30

红黑树：h \leq 2*log(1000000000) \approx 60

综上所述：

对于CPU而言跑10次/20次、30次/60次差别不大，说明这两颗树的性能是同一量级的。但是AVL树为了严格控制平衡是付出代价的，插入和删除需要大量的旋转。所以，红黑树也是很优秀的，也比AVL树好控制点。C++里的map/set也是用红黑树设计的。

2、如何选择？

  • 若查询次数 > 插入/删除次数（如字典）———  AVL树
  • 若插入/删除频繁（如游戏中的实时排行榜）——— 红黑树
  • 不确定时：默认选红黑树，它在综合场景下表现更稳健。

三、红黑树的核心操作

3.1、红黑树结构定义

enum Color
{RED,BLACK
};template<class K,class V>
struct RBTreeNode
{pair<K, V> _kv; // 节点的值，存储键值对RBTreeNode<K, V>* _parent; // 指向父节点RBTreeNode<K, V>* _left; // 指向左孩子RBTreeNode<K, V>* _right; // 指向右孩子Color _col; // 节点的颜色RBTreeNode(const pair<K, V>& kv):_kv(kv),_parent(nullptr),_left(nullptr),_right(nullptr),_col(RED){}
};//红黑树实现
template<class K,class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:// ......private:Node* _root = nullptr;
};

3.2、插入操作

先分析一下,当我们要插入一个节点时，节点的颜色设置成红色还是黑色？

答案：红色。在考虑性质3和性质4时，插入的颜色是红色的话，不会影响其他路径，只会影响当前路径。但如果插入节点颜色是黑色的话，性质4被破坏了，并且会影响其它路径。

插入情况分析：
由上图可知：只有当我们插入节点颜色为红色且父节点也为红色时，整棵树才违反红黑树规则需要调整来维持平衡。这里直接分析具体情况，其他情况类似分析即可：

情况1：cur为红，parent为红，grandfather为黑，uncle存在且为红

情况2： cur为红，parent为红，grandfather为黑，uncle不存在

在向上面那样处理的话，违反每条路径上黑色节点的数量相等

情况3： cur为红，parent为红，grandfather为黑，uncle存在且为黑

总结：

红黑树插入关键看uncle节点

  1. uncle存在且为红，变色+向上更新
  2. uncle不存在/uncle存在且为黑，旋转+变色

具体是左单旋，右单旋还是双旋看情况分析

代码示例：
 

bool insert(const pair<K, V>& kv)
{//这里按二叉搜索树规则找合适位置插入就行，主要看平衡操作// ......//控制红黑树平衡while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){//变色grandfather->_col = RED;parent->_col = uncle->_col = BLACK;//继续向上处理cur = grandfather;parent = cur->_parent;}else //uncle不存在 或 uncle == BLACK{if (parent->_left == cur){//      g//   p//cRotateR(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;}else {//      g//   p//      cRotateL(parent);RotateR(grandfather);//变色cur->_col = BLACK;grandfather->_col = RED;}//break;}}else // grandfather->right == parent{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){//变色grandfather->_col = RED;parent->_col = uncle->_col = BLACK;//继续向上处理cur = grandfather;parent = cur->_parent;}else //uncle为空 或 uncle == BLACK{if (cur == parent->_right){// g//   p//     cRotateL(grandfather);//变色grandfather->_col = RED;parent->_col = BLACK;}else // cur == parent->left{// g//   p// cRotateR(parent);RotateL(grandfather);//变色grandfather->_col = RED;cur->_col = BLACK; }//break;}}}_root->_col = BLACK;return true;
}

四、红黑树的验证

红黑树的检测分为两步：

1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)

2. 检测其是否满足红黑树的性质

// 检查红黑树性质的核心递归函数
// root: 当前检查的节点
// blacknum: 当前路径已累积的黑色节点数（按值传递保持路径独立）
// benchmark: 基准黑高（从根到最左叶子的黑色节点数）
bool CheckColor(Node* root, int blacknum, int benchmark) 
{// 递归终止条件：到达叶子节点（NIL）if (root == nullptr) {// 检查当前路径黑高是否等于基准值if (benchmark != blacknum) {return false; // 黑高不一致，违反性质5}return true; // 当前路径合法}// 性质2：根节点为黑已在入口函数检查，此处无需处理// 统计黑色节点数量if (root->_col == BLACK) {++blacknum; // 遇到黑色节点，累计计数}// 性质4：检查连续红色节点if (root->_col == RED && root->_parent && root->_parent->_col == RED) {cout << root->_kv.first << "出现连续红色节点" << endl; // 输出违规位置return false; // 父子节点均为红，违反性质4}// 递归检查左右子树（注意blacknum是值传递，左右子树计数独立）return CheckColor(root->_left, blacknum, benchmark) && CheckColor(root->_right, blacknum, benchmark);
}// 外部调用的平衡性检查接口
bool IsBalance() 
{return IsBalance(_root); // 从根节点开始检查
}// 内部实现的平衡性检查入口
bool IsBalance(Node* root) 
{if (root == nullptr) {return true; // 空树视为平衡}// 根节点必须为黑if (root->_col != BLACK) {return false; // 根节点为红直接失败}// 计算基准黑高（从根到最左叶子路径的黑色节点数）int benchmark = 0;Node* cur = root;while (cur) {if (cur->_col == BLACK) {++benchmark; // 统计黑色节点}cur = cur->_left; // 沿左子树深入}// 从根节点开始递归检查所有路径，初始黑高计数为0return CheckColor(root, 0, benchmark);
}

五、完整代码

template<class K,class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:bool insert(const pair<K, V>& 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->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);cur->_col = RED;if (parent->_kv.first > kv.first){parent->_left = cur;}else{parent->_right = 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){//变色grandfather->_col = RED;parent->_col = uncle->_col = BLACK;//继续向上处理cur = grandfather;parent = cur->_parent;}else //uncle不存在 或 uncle == BLACK{if (parent->_left == cur){//      g//   p//cRotateR(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;}else {//      g//   p//      cRotateL(parent);RotateR(grandfather);//变色cur->_col = BLACK;grandfather->_col = RED;}//break;}}else // grandfather->right == parent{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){//变色grandfather->_col = RED;parent->_col = uncle->_col = BLACK;//继续向上处理cur = grandfather;parent = cur->_parent;}else //uncle为空 或 uncle == BLACK{if (cur == parent->_right){// g//   p//     cRotateL(grandfather);//变色grandfather->_col = RED;parent->_col = BLACK;}else // cur == parent->left{// g//   p// cRotateR(parent);RotateL(grandfather);//变色grandfather->_col = RED;cur->_col = BLACK; }//break;}}}_root->_col = BLACK;return true;}void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright){curright->_parent = parent;}Node* ppnode = parent->_parent;parent->_parent = cur;cur->_right = parent;if (_root == parent){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;cur->_parent = ppnode;}else{ppnode->_right = cur;cur->_parent = ppnode;}}}void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}Node* ppnode = parent->_parent;cur->_left = parent;parent->_parent = cur;if (_root == parent){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;cur->_parent = ppnode;}else{ppnode->_right = cur;cur->_parent = ppnode;}}}private:Node* _root = nullptr;
};


http://www.mrgr.cn/news/100064.html

相关文章：

  • DPIN河内AI+DePIN峰会：共绘蓝图，加速构建去中心化AI基础设施新生态
  • 【Harmony OS】组件
  • Java 安全：如何实现用户认证与授权？
  • Chrmo手动同步数据
  • 一款好用的桌面待办工具，轻松掌控时间沙漏！
  • 【Python数据库与后端开发】从ORM到RESTful API
  • 【专题刷题】二分查找（二）
  • 单机无穷大系统暂态稳定性仿真Matlab模型
  • 【Kafka 初学】为什么启动 Kafka 前必须先启动 Zookeeper
  • Canvas入门教程！！【Canvas篇二】
  • 第TR5周：Transformer实战:文本分类
  • 基于Axure的动态甘特图设计：实现任务增删改与时间拖拽交互
  • 初一试后担忧
  • 【c++11】c++11新特性（下）（可变参数模板、default和delete、容器新设定、包装器）
  • Redis是单线程的，如何提高多核CPU的利用率？
  • Python Transformers 库介绍
  • Langchain入门介绍
  • 【金仓数据库征文】金仓数据库：开启未来技术脑洞，探索数据库无限可能
  • 5.6 Microsoft Semantic Kernel：专注于将LLM集成到现有应用中的框架
  • 【黑马 微服务面试篇】