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

【C++】实现红黑树

news 2025/9/13 20:55:24

目录

  • 一、认识红黑树
    • 1.1 概念
    • 1.2 定义
  • 二、实现红黑树
    • 2.1 插入
    • 2.2 与AVL树对比

一、认识红黑树

1.1 概念

红黑树是一个二叉搜索树，与AVL树相比，红黑树不再使用平衡因子来控制树的左右子树高度差，而是用颜色来控制平衡，颜色为红色或者黑色。控制任意一条从根到叶子节点的路径的节点颜色，就可以确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

在这里插入图片描述

红黑树的规则：

  • 根节点是黑色的
  • 不能有连续的红色节点
  • 从某个节点出发，每条路径上的黑色节点的数量相同

1.2 定义

红黑树也是三叉链结构（左指针、右指针和父亲指针），有一个新的存储位来记录节点的颜色，这里实现的红黑树是kv模型。

enum Colour
{RED,//红色BLACK//黑色
};template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Colour _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr),_kv(kv),_col(RED)//默认的新节点都是红色的{}
};

二、实现红黑树

2.1 插入

红黑树的插入的与普通二叉搜索树的插入逻辑是一样的，不同的是插入新节点后要进行变色处理，符合前面的规则才行。
红黑树的插入一共分为两大类：

  1. 新插入的节点的父节点是黑色的，插入结束
  2. 新插入的节点的父节点是红色的，要变色处理

也就是说要看新插入的节点的父节点的颜色来确定是否本次插入结束。但是有个问题，新插入的节点说什么颜色的？其实看图就可以知道，插入的新节点必须是红色的，因为如果插入的是黑色节点，那么必然会导致每条路径上的黑色节点数量不相同，违反规则。

接下来看红黑树插入节点时是怎样变色的：
首先按照前面插入的两大类，如果插入节点的父节点是黑色的，就不需要进入变色调整；反之，如果插入节点的父节点存在且是红色的，说明此时有连续的红色节点，要变色处理。

这里需要定义几个节点的名字，方便叙述和画图：

  • c（cur）——当前新插入的节点
  • p（parent）——插入节点的父节点
  • g（grandfather）——父节点的父节点
  • u（uncle）——叔叔节点，父节点的另一边的节点

在这里插入图片描述
这4个节点主要看叔叔节点，根据叔叔节点分为两种情况。

情况一：叔叔存在且为红
p和u要变成黑色，g变成红色。如果g不是根节点，要向上更新，把g当成c；如果g是根节点，要把g变成黑色的，因为根节点必须是黑的。

1️⃣g是根节点

在这里插入图片描述

注意：不管p或者u是g的左边还是右边都是一样的，c在p的左边/右边都是一样的操作，不影响。

2️⃣g不是根节点
在这里插入图片描述

情况二：叔叔不存在或者叔叔存在且为黑

情况二里面又有4种变色方式（其实与其说是变色方式，不如直接说是旋转方式不同然后根据旋转情况来变色）

1️⃣p是g的左孩子，c是p的左孩子
进行右单旋，p变黑，g变红
在这里插入图片描述
在这里插入图片描述
上图的c不是新增，表示的是当它的叔叔节点u存在且为黑时的c不是新增。

注意：
这里u存在或者不存在也有两种情况，第一张图的c是新增的节点，u必然是不存在的，如果存在，会导致每条路径的黑色节点数量不相同；同理，第二张图的c刚开始是黑色的节点，它有自己的子树，是通过后面的向上变色处理才变红的，所以第二张图的u是必须存在的。总之一句话，u存不存在要符合规则

后面就以u不存在的情况处理
2️⃣p是g的右孩子，c是p的右孩子
进行左单旋，p变黑，g变红
在这里插入图片描述

3️⃣p是g的左孩子，c是p的右孩子
先左单旋§，再右单旋(g)，g变红，c变黑
在这里插入图片描述

4️⃣p是g的右孩子，c是p的左孩子
先右单旋§，再左单旋(g)，g变红，c变黑
在这里插入图片描述
代码：

//插入
bool Insert(const pair<K, V>& kv)
{//为空if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;//根节点都是黑色的，特殊处理return true;}//非空Node* cur = _root;Node* parent = nullptr;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);//红色的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){Node* uncle = grandfather->_right;//情况一：叔叔存在且为红if (uncle && uncle->_col == RED){grandfather->_col = RED;uncle->_col = parent->_col = BLACK;cur = grandfather;//爷爷不是根，向上更新parent = cur->_parent;}//情况二：叔叔不存在/存在且为黑else{//单旋if (cur == parent->_left){RotateR(grandfather);//右单旋parent->_col = BLACK;//变色grandfather->_col = RED;}//左右双旋 // cur == parent->_rightelse{RotateL(parent);//先左单旋RotateR(grandfather);//再右单旋grandfather->_col = RED;//变色cur->_col = BLACK;}}}else//父节点在右边，叔叔在左边{Node* uncle = grandfather->_left;//情况一：叔叔存在且为红if (uncle && uncle->_col == RED){grandfather->_col = RED;uncle->_col = parent->_col = BLACK;cur = grandfather;//爷爷不是根，向上更新parent = cur->_parent;}//情况二：叔叔不存在/存在且为黑else{//单旋if (cur == parent->_right){RotateL(grandfather);//左单旋parent->_col = BLACK;//变色grandfather->_col = RED;}//右左双旋 // cur == parent->_leftelse{RotateR(parent);//先右单旋RotateL(grandfather);//再左单旋grandfather->_col = RED;//变色cur->_col = BLACK;}break;//经过情况二后跳出}}}_root->_col = BLACK;//统一处理，根必须是黑的return true;
}//左单旋
void RotateL(Node* parent)
{RotateSize++;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;//不为空if (subRL){subRL->_parent = parent;}subR->_left = parent;Node* ppnode = parent->_parent;parent->_parent = subR;//处理parent如果为根if (parent == _root){_root = subR;subR->_parent = nullptr;}//不为根，处理与ppnode的连接else{if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}
}//右单旋
void RotateR(Node* parent)
{RotateSize++;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;//不为空if (subLR){subLR->_parent = parent;}subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}
}

2.2 与AVL树对比

红黑树与AVL树都是平衡二叉树，那为什么现实中绝大部分是使用红黑树，很少使用AVL树？下面我们来作数据对比，从两者的旋转次数、插入时间、平衡状态和高度来作分析。

测试代码：

RBTree<int, int> t1;
AVLTree<int, int> t2;const int N = 10000000;
vector<int> v;
v.reserve(N);
srand(time(0));for (size_t i = 0; i < N; i++)
{v.push_back(rand() + i);
}size_t begin1 = clock();
for (auto e : v)
{t1.Insert(make_pair(e, e));
}
size_t end1 = clock();size_t begin2 = clock();
for (auto e : v)
{t2.Insert(make_pair(e, e));
}
size_t end2 = clock();
//旋转次数
cout << "RBTree RoateSize:" << t1.getRotateSize() << endl;
cout << "AVLTree RoateSize:" << t2.getRotateSize() << endl;
//插入时间
cout << "RBTree Insert:" << end1 - begin1 << endl;
cout << "AVLTree Insert:" << end2 - begin2 << endl;
//平衡状态
cout << "RBTree IsBalance:" << t1.IsBalance() << endl;
cout << "AVLTree IsBalance:" << t2.IsBalance() << endl;
//树的高度
cout << "RBTree Height:" << t1.Height() << endl;
cout << "AVLTree Height:" << t2.Height() << endl;
//树的节点个数
cout << "RBTree Size:" << t1.Size() << endl;
cout << "AVLTree Size:" << t2.Size() << endl;

插入一千万个数据，运行结果：
在这里插入图片描述
可以发现，红黑树的旋转次数比AVL树少，插入时间相差不大，两种树都是平衡的，红黑树的高度略高一些。

总结：
由于高度上红黑树不会高出多少，所以搜索效率影响不大。从树的高度可知，AVL树是极致追求平衡的，所以要频繁的进行旋转，这也导致旋转次数明显比红黑树多，因此在旋转上开销较大，不及红黑树的性能更优越些，同时红黑树实现比较简单，所以实际运用中红黑树更多。

http://www.lryc.cn/news/318791.html

相关文章：

  • 爬虫(六)
  • 最长连续序列 - LeetCode 热题 3
  • 运营模型—RFM 模型
  • YOLOv9|加入2023Gold YOLO中的GD机制！遥遥领先！
  • WRF模型运行教程（ububtu系统）--III.运行WRF模型（官网案例）
  • html和winform webBrowser控件交互并播放视频（包含转码）
  • Neo4j 批量导入数据 从官方文档学习LOAD CSV 命令 小白可食用版
  • Day43-2-企业级实时复制intofy介绍及实践
  • 2024年AI辅助研发趋势深度解析：科技革新与效率提升的双重奏
  • bash: mysqldump: command not found
  • hcie数通和云计算选哪个好？
  • 浅易理解：非极大抑制NMS
  • C语言如何进⾏字符数组的复制？
  • Linux 中搭建 主从dns域名解析服务器
  • CSS3病毒病原体图形特效
  • Tomcat Web 开发项目构建教程
  • Elasticsearch(9) gauss的使用
  • php前端和java后端数据调用流程
  • C语言从入门到熟悉------第四阶段
  • 【目标检测-数据集准备】DIOR转为yolo训练所需格式
  • Nacos为什么对于临时实例采用心跳检测,非临时实例采用主动询问?Nacos同时作为配置中心和注册中心有什么坏处?为什么Nacos可以抗住那么高的注册?
  • 【NLP】如何实现快速加载gensim word2vec的预训练的词向量模型
  • 前端实例：页面布局1（后端数据实现）
  • 【调参】如何为神经网络选择最合适的学习率lr-LRFinder-for-Keras
  • 【设计模式】Java 设计模式之享元模式（Flyweight）
  • 异次元发卡源码系统/荔枝发卡V3.0二次元风格发卡网全开源源码
  • 腾讯春招后端一面（八股篇）
  • “风口”上的量化大厂“绣球”抛向中低频人才
  • obdiag如何实现一键采集20+故障场景的诊断信息——《OceanBase诊断系列》之九
  • Cookie和Session的获取方法