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

红黑树的模拟实现

news 2025/12/3 0:13:19

目录

前言

概念

为什么红黑树满足  最长路径的节点个数 <= 2 * 最短路径的节点个数？

答案揭晓

举例

红黑树诞生原因

红黑树的模拟实现

“颜色”定义

基本数据结构定义

RBTreeNode的定义

RBTree的定义 

基本操作实现

Insert函数

基础知识

“叔叔”这个身份的认知

插入原则

插入的准备工作

插入节点的颜色定义

情况分类

情况1：根节点为空

情况2：叔叔为红色

情况2：叔叔不存在或者叔叔为黑色

分析

1、叔叔不存在

2、叔叔为黑色

IsBalance函数

测试代码

总代码

前言

我在前面的文章中，已经详细讲解了二叉搜索树（二叉搜索树的模拟实现-CSDN博客）、AVL树（AVL树模拟实现-CSDN博客）的模拟实现，终于，我要讲解红黑树啦~~~，让我们进入正题吧

ヾ(≧▽≦*)o

概念

红黑树也是一棵二叉搜索树，它有如下特点

1、每个节点不是红色就是黑色

（从红黑树名字就可得知）

2、根节点是黑色的

（这是检查红黑树是否正确的一个判断条件）

3、如果一个节点是红色的，那它的两个孩子就是黑色的

（因此在每个路径上，不可以出现连续的两个红色节点，这既可以作为检查红黑树是否正确的判断条件，也是判断插入一个节点后是否需要进行旋转操作的一个条件）

4、从该节点到所有后代叶节点的简单路径上，均包含相同数目的黑色节点

（这是检查红黑树是否正确的一个判断条件）

这些特点使得红黑树效率也很高，因为他们构成了一个大特点：

最长路径的节点个数 <= 2 * 最短路径的节点个数

为什么红黑树满足  最长路径的节点个数 <= 2 * 最短路径的节点个数？

通过第四个特点，我们思考一下：

(1) 最短路径满足什么条件？

(2) 从最短路径的情况能推断出最长路径应该长什么样？

答案揭晓

(1) 最短路径满足什么条件？

答：当该路径所有节点都是黑色节点时，该路径最短

(2) 从最短路径的情况能推断出最长路径应该长什么样？

答：当该路径黑红相间时，该路径最长

举例

当每条路径上的黑色节点数为3时

❁ 当所有节点为黑色 时，该路径长为3

❁ 当该路径黑红相间时，该路径长为6

所以红黑树满足： 最长路径的节点个数 <= 2 * 最短路径的节点个数

下图就清晰明了了

红黑树诞生原因

我们通过了解AVL树可知，AVL树的效率非常高，它通过维持左右子树高度差的绝对值 < 2来维持平衡，如果该绝对值 >= 2，则将进行旋转，在面对杂乱顺序的数据的情况下，仍然游刃有余。

但是，当数据是有序的，也就是基本升序或者降序时，AVL树将花大量时间在旋转上，这就使得AVL树的效率变低，而造成这一结果的原因是：AVL树追求的是极度平衡。

【注】这一特点使得AVL树高度较低，面对100w个数据，树的高度也是在27~28之间，这使得在最坏情况下，我们需要查找比较的次数控制在30以内，这也是AVL树效率高的原因

因此，红黑树在付出更少的旋转的代价下，诞生了

红黑树的模拟实现

“颜色”定义

虽然红黑树有颜色，但是红色和黑色并不是真的颜色，而是用了枚举enum的知识，将字符串转化为数字（内部），因此黑色红色的定义就是一个枚举

enum COLOR
{BLACK,RED
};
// 枚举常量通常用大写

基本数据结构定义

RBTreeNode的定义

该部分和AVL树极其相似（忘记的可以去复习哦：AVL树模拟实现-CSDN博客），只不过多了一个颜色的成员

template <typename T, typename V>
struct RBTreeNode//RadBlackTree的缩写
{RBTreeNode<T,V>* _left;RBTreeNode<T, V>* _right;RBTreeNode<T, V>* _parent;pair<T, V> _data;COLOR _col;/**/RBTreeNode(const pair<T, V>& kv)// 构造函数: _left(nullptr), _right(nullptr), _parent(nullptr), _data(kv), _col(RED)/*插入节点起初都为红色最好，这样只需要检查  当前所在子树  是否出现连续的红节点的情况，若为黑色将会改变该路径的长度，将会影响   所有路径  */{}
};

RBTree的定义 

仍然和普通的树一样

template <typename T, typename V>
class RBTree
{typedef RBTreeNode<T, V> Node;
public:private:Node* _root = nullptr;
};

基本操作实现

Insert函数

所有的二叉搜索树都一样，最关键的部分就是Insert部分，而红黑树的Insert部分无非就是 =  平衡的调整 + 颜色的变换

也就是说

Insert = 旋转 + 变色

基础知识

“叔叔”这个身份的认知

我们在红黑树的插入部分，需要注意的就是“叔叔”这个角色，叔叔就是自己的父亲的兄弟，也就是自己爷爷的另一个儿子，“叔叔”将会是插入操作的重要部分。

插入原则

❁ 保证目前子树的所有路径的黑色节点数不变，否则和插入黑色节点没区别（将影响所有路径）

❁ 根节点必须是黑色

插入的准备工作

在插入前，我们首先要做的就是找到

❁ 插入位置

❁ 插入位置的父亲

这一部分也和二叉搜索树相同啦

bool Insert(const pair<T, V>& kv)
{Node* cur = _root;Node* parent = nullptr;while (cur){parent = cur;if (kv.second > cur->_data.second){cur = cur->_right;}else if (kv.second < cur->_data.second){cur = cur->_left;}else{return false;}}Node* newnode = new Node(kv);newnode->_parent = parent;if (kv.second > parent->_data.second){parent->_right = newnode;}else if (kv.second < parent->_data.second){parent->_left = newnode;}cur = newnode;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;Node* uncle;if (parent == grandfather->_left){uncle = grandfather->_right;}else{uncle = grandfather->_left;}}_root->_col = BLACK; /*重点(插入原则：根节点为黑色)*/return true;
}
插入节点的颜色定义

我在“基础数据结构定义”部分已经注释了：

插入节点起初都为红色最好，这样只需要检查  当前所在子树  是否出现连续的红节点的情况，
若为黑色将会改变该路径的长度，将会影响   所有路径  

通过这里，我们就知道我们插入的节点应该起初定义为红色

但是我们红黑树的一个重要特点就是：一条路径下不能有连续的红色节点

这一点造成我们插入一个数据后，需要判断其父亲的颜色

❁ 如果父亲为黑色，那么不需要在意

❁ 如果父亲为红色，那我们需要按情况调整，情况已经在下面列举出来啦，让我们看看吧(´▽`ʃ♡ƪ)

情况分类

情况1：根节点为空

这个情况自然是第一个节点插入的时候，只需要给_root分配空间，并将其颜色设置为黑色，就可以返回啦

if (_root == nullptr)
{_root = new Node(kv);_root->_col = BLACK;return true;
}
情况2：叔叔为红色

如下图所示

 

我们需要满足“插入原则”

1、该子树所有路径黑色节点数不变

所以我们可以通过如下操作来改变：

(1) 父亲必须变为黑色（这是一定的）

根据第一点，我们会发现该子树最左边的路径的黑色节点数增加1，为了不改变路径的黑色节点数，我们进行第二步

(2) 爷爷变为红色

根据红黑树的特点：不可以有连续的两个红色节点。我们进行第三步

(3) 叔叔变为黑色

如下图所示

细心的读者可能会发现：爷爷的颜色变为红色了

在红黑树这个非红即黑的树下，我们就需要对“红色”极其敏感

这里爷爷不一定是祖先，所以，我们应该注意爷爷的父亲是什么颜色，因此将更新cur = grandfather，parent也随其改变，parent = cur->_parent

cur = grandfather，parent也随其改变，parent = cur->_parent

代码如下

if (uncle && uncle->_col == RED/*叔叔颜色是红色*/)
{/*只需要变色,然后grandfather变为cur*//*grandfather变为红色parent和uncle变为黑色*/grandfather->_col = RED;uncle->_col = parent->_col = BLACK;// 继续向上更新cur = grandfather;parent = cur->_parent;
}
情况2：叔叔不存在或者叔叔为黑色

这两种情况我们需要进行的操作如下：

旋转 + 变色
    
    旋转：
        左左、右右情况同AVL树的旋转
        左右、右左情况按照cur的情况分析：
            如果parent是左孩子cur是右孩子，左旋parent，然后就转化为左左情况
            如果parent是右孩子cur是左孩子，右旋parent，然后就转化为右右情况
    变色：
        parent变为黑色，因为他变为了该子树的祖先
        grandfather、cur变为红色，为了不影响每条路径的黑色节点个数

分析
1、叔叔不存在

左左情况

红黑树是一棵“近似平衡”的树，但如上图所示，该树不平衡，这个时候我们就需要“旋转”

根据AVL树的知识，我们就可以知道该树为“左左情况”，因此我们需要“右旋”，如下所示

 

而插入原则规定：不可改变该子树路径中的黑色节点个数

因此这里我们需要保证每条路径的黑色节点数目不变，因此

1、将parent的颜色改为黑色

2、新插入节点 和 grandfather的颜色改为红色

 

同样，我们观察一下最上面的节点，我们可以发现，它的颜色为黑色，因此我们不需要向上更新

2、叔叔为黑色

左左情况

 

根据叔叔不存在且为“左左”的情况，我们同样可以知道，叔叔存在时的“左左”情况可以写为：

1、右旋grandfather

2、更改颜色（parent变黑色，cur和grandfather变红色）

通过以上可见，uncle不存在 和 uncle为黑色  的情况的处理方法一样，所以如下部分我将以 uncle为黑色的情况讲述~(￣▽￣)~*

    if (parent == grandfather->_left){if (cur == parent->_left){// 左左情况// 右旋RotateR(grandfather);// 变色parent->_col = BLACK;cur->_col = grandfather->_col = RED;}}

 右右情况

很显然，右右情况和左左情况类似，只不过旋转方向变了，因此它的操作如下：

1、左旋grandfather

2、parent的颜色 = 黑色，cur的颜色 = grandfather的颜色 = 红色

    else{if (cur == parent->_right){// 右右情况// 左旋RotateL(grandfather);// 变色parent->_col = BLACK;cur->_col = grandfather->_col = RED;}}

左右情况

 

这种情况看似复杂，其实我们能发现：这棵树不平衡。

因此我们思路就是：先变平衡。

很显然，从parent那里就已经不平衡了，因此我们需要左旋parent

 

我们会发现：这个情况变为了“左左”情况！！！！！！！！

因此我们只需要右旋grandfather就好，并更改颜色 

颜色更改：

cur = 黑色

parent = grandfather = 红色

我们可以发现：最上面的节点为黑色。

因此我们不用继续向上更新

 // 左右情况// 先左旋parentRotateL(parent);// 再右旋grandfatherRotateR(grandfather);// 变色cur->_col = BLACK;parent->_col = grandfather->_col = RED;

右左情况

同样，和左右情况类似，步骤：

1、右旋parent

2、变为了“右右”情况，左旋grandfather

3、更改颜色：

      cur = 黑色

      parent = grandfather = 红色

 // 右左情况// 先右旋parentRotateR(parent);// 再左旋grandfatherRotateL(grandfather);// 变色cur->_col = BLACK;parent->_col = grandfather->_col = RED;

IsBalance函数

该部分用来检查该红黑树是否正确

public:bool IsBalance(){return _IsBalance(_root);// 这种在外部接口里面调用内部接口的原因我在AVL树和二叉搜索树部分讲过// 原因：这样子使用就不需要设置外部接口让类外访问_root，再调用该函数}
private:bool _IsBalance(Node* root, int numfirst = -1/*第一条路径的黑色节点个数*/, int num = 0/*该路径黑色节点的个数*/){if (root == nullptr)// 到了一条路径的末尾{if (numfirst == -1)// 说明是第一条路径{numfirst = num;return true;}else// 不是第一条路就{// 打印提示信息方便定位插入哪个部分代码不对if (numfirst != num)cout << "不是所有路径的黑色节点个数相同" << endl;return numfirst == num;// 判断每条路径的黑色节点个数是否相同}}// 根必须为黑色if (root == _root && _root && root->_col == RED){cout << "根为红色" << endl;return false;}// 不能有连续的红色if (root->_col == RED){if (root->_left && root->_left->_col == RED){cout << "两个连续节点为红色" << endl;return false;}if (root->_right && root->_right->_col == RED){cout << "两个连续节点为红色" << endl;return false;}}else // 每条路径的黑色节点数相同{return _IsBalance(root->_left, numfirst, num + 1)&/*注意不是&&*/ _IsBalance(root->_right, numfirst, num + 1);}return true;}

测试代码

我们可以采用随机数的方法来检测我们的代码是否有bug哦，以下部分就是该方法的代码啦

void test()
{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);// + i：使得数据更随机}size_t begin2 = clock();// 记录Insert部分的起始时间RBTree<int, int> t;for (auto e : v){//cout << "Insert:" << e << "->";t.Insert(make_pair(e, e));//cout << t.IsBalance() << endl;}size_t end2 = clock();// 记录Insert部分的结束时间cout << "Insert:" << end2 - begin2 << endl;// 计算Insert  10000000个数据时所需要的时间cout << t.IsBalance() << endl;
}

中序遍历部分就和普通树的部分一样啦，这里就不过多赘述啦

总代码

#pragma onceenum COLOR
{BLACK,RED
};template <typename T, typename V>
struct RBTreeNode
{RBTreeNode<T,V>* _left;RBTreeNode<T, V>* _right;RBTreeNode<T, V>* _parent;pair<T, V> _data;COLOR _col;RBTreeNode(const pair<T, V>& kv): _left(nullptr), _right(nullptr), _parent(nullptr), _data(kv), _col(RED)/*插入节点起初都为红色最好，这样只需要检查  当前所在子树  是否出现连续的红节点的情况，若为黑色将会改变该路径的长度，将会影响   所有路径  */{}
};template <typename T, typename V>
class RBTree
{typedef RBTreeNode<T, V> Node;
public:bool Insert(const pair<T, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;while (cur){parent = cur;if (kv.second > cur->_data.second){cur = cur->_right;}else if (kv.second < cur->_data.second){cur = cur->_left;}elsereturn false;}Node* newnode = new Node(kv);newnode->_parent = parent;if (kv.second > parent->_data.second){parent->_right = newnode;}else if (kv.second < parent->_data.second){parent->_left = newnode;}cur = newnode;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;Node* uncle;if (parent == grandfather->_left){uncle = grandfather->_right;}elseuncle = grandfather->_left;if (uncle == nullptr/*叔叔不存在*/ || uncle->_col == BLACK/*叔叔颜色是黑色*/){/*旋转 + 变色*//*旋转：左左、右右情况同AVL树的旋转左右、右左情况按照cur的情况分析：如果parent是左孩子cur是右孩子，左旋parent，然后就转化为左左情况如果parent是右孩子cur是左孩子，右旋parent，然后就转化为右右情况变色：p变为黑色，因为他变为了该子树的组先g、c变为红色，为了不影响每条路径的黑色节点个数*/// 旋转if (parent == grandfather->_left){if (cur == parent->_left){// 左左情况// 右旋RotateR(grandfather);// 变色parent->_col = BLACK;cur->_col = grandfather->_col = RED;}else{// 左右情况// 先左旋parentRotateL(parent);// 再右旋grandfatherRotateR(grandfather);// 变色cur->_col = BLACK;parent->_col = grandfather->_col = RED;}}else{if (cur == parent->_right){// 右右情况// 左旋RotateL(grandfather);// 变色parent->_col = BLACK;cur->_col = grandfather->_col = RED;}else{// 右左情况// 先右旋parentRotateR(parent);// 再左旋grandfatherRotateL(grandfather);// 变色cur->_col = BLACK;parent->_col = grandfather->_col = RED;}}break;}else// if (uncle->_col == RED/*叔叔颜色是红色*/){/*只需要变色,然后grandfather变为cur*//*grandfather变为红色parent和uncle变为黑色*/grandfather->_col = RED;uncle->_col = parent->_col = BLACK;// 继续向上更新cur = grandfather;parent = cur->_parent;}}_root->_col = BLACK;/*重点*/return true;}// 左单旋void RotateL(Node* root){Node* subR = root->_right;Node* subRL = subR->_left;/*可能为空*/root->_right = subRL;if (subRL){subRL->_parent = root;}subR->_left = root;subR->_parent = root->_parent;root->_parent = subR;if (root == _root)_root = subR;if (subR->_parent){if (root == subR->_parent->_left){subR->_parent->_left = subR;}elsesubR->_parent->_right = subR;}}// 右单旋void RotateR(Node* root){Node* subL = root->_left;Node* subLR = subL->_right;/*可能为空*/root->_left = subLR;if (subLR){subLR->_parent = root;}subL->_right = root;subL->_parent = root->_parent;root->_parent = subL;if (root == _root)_root = subL;if (subL->_parent){if (root == subL->_parent->_left){subL->_parent->_left = subL;}elsesubL->_parent->_right = subL;}}void InOrder(){_InOrder(_root);cout << endl;}// 检查是否平衡时用void PreOrder(){_PreOrder(_root);cout << endl;}void _PreOrder(Node* root){if (root == nullptr)return;cout << root->_data.first << "(" << root->_col << ") ";_PreOrder(root->_left);_PreOrder(root->_right);}bool IsBalance(){return _IsBalance(_root);}bool IsBalance2(){if (_root == nullptr)return true;if (_root->_col == RED)return false;//参考值int refVal = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refVal;}cur = cur->_left;}int blacknum = 0;return Check(_root, blacknum, refVal);}private:void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_data.first << " ";_InOrder(root->_right);}bool _IsBalance(Node* root, int numfirst = -1/*第一条路径的黑色节点个数*/, int num = 0){if (root == nullptr){if (numfirst == -1){numfirst = num;return true;}else{// 打印提示信息方便定位插入哪个部分代码不对if (numfirst != num)cout << "不是所有路径的黑色节点个数相同" << endl;return numfirst == num;}}// 根必须为黑色if (root == _root && _root && root->_col == RED){cout << "根为红色" << endl;return false;}// 不能有连续的红色if (root->_col == RED){if (root->_left && root->_left->_col == RED){cout << "两个连续节点为红色" << endl;return false;}if (root->_right && root->_right->_col == RED){cout << "两个连续节点为红色" << endl;return false;}}else // 每条路径的黑色节点数相同{return _IsBalance(root->_left, numfirst, num + 1)&/*注意不是&&*/ _IsBalance(root->_right, numfirst, num + 1);}return true;}// 根节点->当前节点这条路径的黑色节点的数量bool Check(Node* root, int blacknum, const int refVal){if (root == nullptr){//cout << balcknum << endl;if (blacknum != refVal){cout << "存在黑色节点数量不相等的路径" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << "有连续的红色节点" << endl;return false;}if (root->_col == BLACK){++blacknum;}return Check(root->_left, blacknum, refVal)&& Check(root->_right, blacknum, refVal);}private:Node* _root = nullptr;
};

完结撒花~❀❀❀❀❀❀❀❀❀

快开学啦，祝大家在新的一学期收获满满哦，脑子不好的小菜鸟和你一起加油哦(●ˇ∀ˇ●)


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

相关文章：

  • Java面试八股之什么是MQTT协议
  • Leetcode3228. 将 1 移动到末尾的最大操作次数
  • STM32使用串口DMA发送+空闲中断
  • 4.1 SQL的起源与发展
  • 3D 技术对我们的生活有哪些影响？
  • 流量分析0.o
  • 安卓App开发 篇五：签名和打包
  • Kafka系列之：Kafka Connect深入探讨 - 错误处理和死信队列
  • 微前端架构下的响应式设计实现策略
  • 腾讯云短信正文模板每个变量取值最多支持6个字符出现的问题及应对方法
  • MyBatis入门
  • Ubuntu如何实现每天定时关机
  • 力扣经典题目~快乐数~零基础也能看懂哦
  • C++的依赖注入
  • 小程序分账有哪些常见的应用场景
  • C++多态
  • Qt 子窗体直接调用父窗体成员、函数、控件的方法
  • 语音助手Verbi：科技创新的未来
  • VS2017 MFC 使用3D_Button控件注意事项
  • 苍穹外卖-day03(SpringBoot+SSM的企业级Java项目实战)