深入探索：C++红黑树原理与实现

devtools/2024/11/27 1:20:58/

在这里插入图片描述

文章目录

  • 一、红黑树的概念
  • 二、红黑树的规则
  • 三、红黑树与AVL树性能对比
  • 四、红黑树框架的搭建
  • 五、红黑树的插入逻辑
    • 1. 大体框架
    • 2. 初始颜色的设置
    • 3. 颜色的调整
      • 1）通过具体的情况对颜色调整进行框架认识
      • 2）通过抽象图对颜色调整加深理解
        • 情况一：uncle存在且uncle为红色
        • 情况二：uncle不存在或uncle存在且uncle为黑色
  • 六、红黑树是否构建正确的检查
  • 七、红黑树总体代码总结
  • 结语

一、红黑树的概念

红黑树是一棵二叉搜索树，他的每个结点增加一个存储位来表示结点的颜色，可以是红色或者黑色，通过对任何一条从根到叶子的路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。

二、红黑树的规则

在这里插入图片描述

  1. 每个结点不是红色就是黑色
  2. 根节点是黑色的
  3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
  4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点):

规则解释：

  • 什么是路径？对于上图来说，一共有11条路径，根到空节点算一条路径。

  • 红色结点的孩子必须是黑色结点，也就是说任何路径没有连续的红色节点。

  • 每条路径上黑色节点的数量相等

  • 对于任意一个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的黑色结点说明:《算法导论》等书籍上补充了一条每个叶子结点(NIL)都是黑色的规则。他这里所指的叶子结点不是传统的意义上的叶子结点，而是我们说的空结点，有些书籍上也把NIL叫做外部结点。NIL是为了方便准确的标识出所有路径，《算法导论》在后续讲解实现的细节中也忽略了NIL结点，所以我们知道一下这个概念即可。

  • 为什么说只要满足了上述所有规则，就能保证红黑树其最长路径中节点个数不会超过最短路径节点个数的两倍？

只要满足了上述规则，最短的路径将会是全是黑色，最长的路径将是一红一黑红黑相间：
由规则4可知，从根到NULL结点的每条路径都有相同数量的黑色结点，所以极端场景下，最短路径就就是全是黑色结点的路径，假设最短路径长度为bh(black height)。
由规则2和规则3可知，任意一条路径不会有连续的红色结点，所以极端场景下，最长的路径就是黑一红间隔组成，那么最长路径的长度为2*bh。

综合红黑树的4点规则而言，理论上的全黑最短路径和一黑一红的最长路径并不是在每棵红黑树都存在的。假设任意一条从根到NULL结点路径的长度为x，那么bh<=h<=2*bh。

在这里插入图片描述

三、红黑树与AVL树性能对比

性能差异总结：

  1. AVL树:

    • 严格平衡（高度差不超过1）。
    • 高度较低，查找效率更高。
    • 插入和删除操作由于需要频繁调整平衡，开销较大。

  2. 红黑树:

    • 平衡条件较宽松（最长路径不超过最短路径的2倍）。
    • 高度比AVL树稍高，查找效率略低。
    • 插入和删除操作调整较少，性能更优。

表格总结：

树种类平衡条件高度（1000个值）高度（10亿个值）查找效率插入/删除效率
AVL树高度差不超过1(log N = 10)(log N = 30)更高较低
红黑树最长路径 ≤ 最短路径的2倍(2log N = 20)(2log N = 60)略低更高

四、红黑树框架的搭建

#pragma once
#include<iostream>using namespace std;enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour _col;RBTreeNode(const pair<K, V>& kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}
};template<class K, class V> 
class RBTree
{typedef RBTreeNode<K, V> Node;
public:private:Node* _root = nullptr;
};

五、红黑树的插入逻辑

1. 大体框架

首先，插入逻辑的答题思路是和前面我们所学的AVL树的插入主体框架是大体相同的，代码如下：

bool Insert(const pair<K, V>& kv)
{// 树为空，直接插入然后返回if (_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){// 小于往左走if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first)   // 大于往右走{parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);// 链接if (cur->_kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;return true;
}

2. 初始颜色的设置

首先迎来我们第一个问题，新插入结点初始的颜色要设置成什么呢?

如果是根节点，答案很明确，根节点的颜色是黑色！

// 树为空，直接插入然后返回
if (_root == nullptr)
{_root = new Node(kv);// 根节点必须是黑色_root->_col = BLACK;return true;
}

那么对于其他结点呢？
是插入红色，还是插入黑色？

这里面就涉及到两个相冲的规则：
在这里插入图片描述

如果我们选择插入黑色，那么就会违背规则4，那么画出的图是这样的：
在这里插入图片描述
就会造成所有路径黑色结点出现问题，就要更改所有路径的风险，因此我们不选择这种方案。

如果选择插入红色结点，就会违背规则3，画出的图是这样的：
在这里插入图片描述

在这里插入图片描述

如果插入到红色节点后，则只牵扯到当前路径，很容易进行调整。因此我们新插入的结点默认为红色！！！

所以对于其他颜色，我们调节的代码为：

cur = new Node(kv);
// 其他结点初始颜色为红色
cur->_col = RED;

3. 颜色的调整

1）通过具体的情况对颜色调整进行框架认识

对于颜色的调整，我们可以总结为三种情况：

情况一：uncle存在，且为红色：
解决方式：parent与uncle变黑，grandfather变红，继续向上调整。

在这里插入图片描述

情况二：uncle不存在
解决方式：旋转 + 变色

在这里插入图片描述

情况三：uncle存在且为黑色
解决方式：旋转 + 变色

我们上一种情况继续插入，就会变成这种情况：

在这里插入图片描述

在这里插入图片描述

2）通过抽象图对颜色调整加深理解

情况一：uncle存在且uncle为红色

在这里插入图片描述

代码解析：

// 如果我们parent是黑色，不用处理，就结束了// 情况一：cur为红，parent为红，grandfather为黑，uncle不确定
// 用while循环是因为我们要不断的向上调整
while (parent && parent->_col == RED)
{// 首先我们要找到grandfatherNode* grandfather = parent->_parent;// 接下来通过grandfather找到uncle//如果parent是grandfather->_leftif (parent == grandfather->_left){// 说明uncle在右边Node* uncle = grandfather->_right;// uncle存在且为红if (uncle && uncle->_col == RED){// 满足上述情况，开始调整颜色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续向上调整cur = grandfather;parent = cur->_parent;// 但是走到这里有一个问题，如果当前parent就是根，// 并且parent是红色，我们要把它变为黑色，// 处理方式是：出循环后，暴力将_root->_col变为黑色}else    // uncle不存在 或 uncle存在且为黑色{ // ...}}// 这里保证根为黑色
_root->_col = BLACK;
情况二：uncle不存在或uncle存在且uncle为黑色

在这里插入图片描述
因为这里牵扯到旋转，所以我们需要知道旋转的逻辑，这个J桑之前做过专题讲解过，不会的小伙伴可以戳这里~🥰🥰🥰

C++：探索AVL树旋转的奥秘

下面我们在这里再放以下旋转的代码~
唯一的区别就是，这里不需要平衡因子。

// 左单旋
void RotateL(Node* parent)
{Node* cur = parent->_right;Node* curleft = cur->_left;// 重新链接parent->_right = curleft;if (curleft) // 如果curleft存在{curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}
}// 右单旋
void RotateR(Node* parent)
{Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright){curright->_parent = parent;}cur->_right = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (ppnode == nullptr){cur->_parent = nullptr;_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}
}

代码解析：

else    // uncle不存在 或 uncle存在且为黑色{// 判断要怎样旋转// 右单旋if (cur == parent->_left){//     g//   p// cRotateR(grandfather);// 调整颜色parent->_col = BLACK;grandfather->_col = RED;}else // 左右双旋{//     g//   p//		cRotateL(parent);RotateR(grandfather);// 调整颜色cur->_col = BLACK;grandfather->_col = RED;}// 旋转变色完就结束了，这里不加这个也可以，条件判断就会退出break;}

六、红黑树是否构建正确的检查

以下的这段代码的核心目标是检查红黑树是否构建正确，主要基于红黑树的规则进行验证。代码的设计分为两个关键部分：计算基准值和递归验证规则。

代码解析

// 检查是否构建正确
bool CheckColour(Node* root, int blacknum, int benchmark)
{if (root == nullptr){if (blacknum != benchmark)return false;return true;}if (root->_col == BLACK){++blacknum;}if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << root->_kv.first << "出现连续红色节点" << endl;return false;}return CheckColour(root->_left, blacknum, benchmark)&& CheckColour(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;}return CheckColour(root, 0, benchmark);
}

  1. 基准值的计算
    在红黑树中，所有从根节点到叶节点的路径上，必须经过相同数量的黑色节点。为此，代码首先沿着树的左侧路径计算路径上黑色节点的数量，作为基准值 benchmark。这是验证红黑树平衡性的关键步骤。

  2. 递归验证红黑树规则
    接下来通过递归函数 CheckColour，对红黑树的所有节点进行逐一验证，确保其符合以下规则：

  3. 每个节点是红色或黑色。

  4. 红色节点的子节点必须是黑色（即不能出现连续的红色节点）。

  5. 从任一节点到其所有后代的每条路径包含相同数量的黑色节点。

整体逻辑描述

  • 首先调用 IsBalance()，对整棵树进行平衡性检查。

    • 先判断根节点是否为黑色，这是红黑树的基本要求。
    • 沿着左侧路径，计算从根节点到最左叶节点的黑色节点总数，作为基准值。

  • 然后进入递归检查函数 CheckColour()：

    • 如果当前节点为空（即到达叶节点），检查该路径累计的黑色节点数量是否与基准值一致。
    • 对每个非空节点，检查其颜色是否满足规则：红色节点不能有红色父节点。
    • 累计当前路径上的黑色节点数，并递归检查左右子树。

  • 最终通过递归结果判断整棵树是否满足红黑树性质。

  • 如果发现不符合的地方（如连续红色节点或黑色节点数不一致），会提前返回 false 并结束验证。

我们运行的时候给10000000个随机值，看看会不会调用成功。

#include"RBTree_1.h"#include<vector>int main()
{const int N = 10000000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(i);}RBTree<int, int> rbt;for (auto e : v){rbt.Insert(make_pair(e, e));}cout << rbt.IsBalance() << endl;return 0;
}

运行结果如下：
在这里插入图片描述

说明我们的红黑树构建成功啦~

七、红黑树总体代码总结

#pragma once
#include<iostream>using namespace std;enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour _col;RBTreeNode(const pair<K, V>& kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}
};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* cur = _root;Node* parent = nullptr;while (cur){// 小于往左走if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first)   // 大于往右走{parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);// 其他结点初始颜色为红色cur->_col = RED;// 链接if (cur->_kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;// 如果我们parent是黑色，不用处理，就结束了// 情况一：cur为红，parent为红，grandfather为黑，uncle不确定// 用while循环是因为我们要不断的向上调整while (parent && parent->_col == RED){// 首先我们要找到grandfatherNode* grandfather = parent->_parent;// 接下来通过grandfather找到uncle//如果parent是grandfather->_leftif (parent == grandfather->_left){// 说明uncle在右边Node* uncle = grandfather->_right;// uncle存在且为红if (uncle && uncle->_col == RED){// 满足上述情况，开始调整颜色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续向上调整cur = grandfather;parent = cur->_parent;// 但是走到这里有一个问题，如果当前parent就是根，// 并且parent是红色，我们要把它变为黑色，// 处理方式是：出循环后，暴力将_root->_col变为黑色}else    // uncle不存在 或 uncle存在且为黑色{// 判断要怎样旋转// 右单旋if (cur == parent->_left){//     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 //(parent == grandfather->_right)  // 如果parent是grandfather->_right{// 说明uncle在左边Node* uncle = grandfather->_left;// uncle存在且为红if (uncle && uncle->_col == RED){// 满足上述情况，开始调整颜色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续向上调整cur = grandfather;parent = cur->_parent;}else    // uncle不存在 或 uncle存在且为黑色{// 判断要怎样旋转// 左单旋if (cur == parent->_right){// g//	  p//       cRotateL(grandfather);// 调整颜色parent->_col = BLACK;grandfather->_col = RED;}else // 右左双旋{// g//	  p// cRotateR(parent);RotateL(grandfather);// 调整颜色cur->_col = BLACK;grandfather->_col = RED;}break;}}}// 这里保证根为黑色_root->_col = BLACK;return true;}// 左单旋void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;// 重新链接parent->_right = curleft;if (curleft) // 如果curleft存在{curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}// 右单旋void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright){curright->_parent = parent;}cur->_right = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (ppnode == nullptr){cur->_parent = nullptr;_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}// 检查是否构建正确bool CheckColour(Node* root, int blacknum, int benchmark){if (root == nullptr){if (blacknum != benchmark)return false;return true;}if (root->_col == BLACK){++blacknum;}if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << root->_kv.first << "出现连续红色节点" << endl;return false;}return CheckColour(root->_left, blacknum, benchmark)&& CheckColour(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;}return CheckColour(root, 0, benchmark);}private:Node* _root = nullptr;
};

结语

那么到这里就结束啦，创作不易，如果对各位大佬有帮助的话，麻烦给一个一键三连吧~谢谢各位大佬🥰🥰🥰

在这里插入图片描述


http://www.ppmy.cn/devtools/137270.html

相关文章

Pytorch微调深度学习模型

Pytorch微调深度学习模型

在公开数据训练了模型&#xff0c;有时候需要拿到自己的数据上微调。今天正好做了一下微调&#xff0c;在此记录一下微调的方法。用Pytorch还是比较容易实现的。 网上找了很多方法&#xff0c;以及Chatgpt也给了很多方法&#xff0c;但是不够简洁和容易理解。 大体步骤是&…
阅读更多...
使用LoRA微调florence-2模型

使用LoRA微调florence-2模型

1 环境 Kaggle&#xff0c;单GPU 2 数据 图片、索引和标签放在JSON文件中 文件目录如下&#xff1a; logo是图片的文件夹&#xff0c;PNG-SVG是图片的文件夹&#xff0c;re.json是索引&#xff0c;florence2-weight是预训练的权重 JSON文件内容如下&#xff1a; image是…
阅读更多...
unsloth vlm模型Qwen2-VL、Llama 3.2 Vision微调案例

unsloth vlm模型Qwen2-VL、Llama 3.2 Vision微调案例

T4卡15G显卡训练 参考： https://github.com/unslothai/unsloth 按自己显卡cuda版本安装 免费colab微调代码： Qwen2-VL： https://colab.research.google.com/drive/1whHb54GNZMrNxIsi2wm2EY_-Pvo2QyKh?usp=sharing from unsloth import FastVisionModel # NEW instead …
阅读更多...
Python绘制太极八卦

Python绘制太极八卦

文章目录 系列目录写在前面技术需求1. 图形绘制库的支持2. 图形绘制功能3. 参数化设计4. 绘制控制5. 数据处理6. 用户界面 完整代码代码分析1. rset() 函数2. offset() 函数3. taiji() 函数4. bagua() 函数5. 绘制过程6. 技术亮点 写在后面 系列目录 序号直达链接爱心系列1Pyth…
阅读更多...
jQuery-Word-Export 使用记录及完整修正文件下载 jquery.wordexport.js

jQuery-Word-Export 使用记录及完整修正文件下载 jquery.wordexport.js

参考资料&#xff1a; jQuery-Word-Export导出word_jquery.wordexport.js下载-CSDN博客 近期又需要自己做个 Html2Doc 的解决方案&#xff0c;因为客户又不想要 Html2pdf 的下载了&#xff0c;当初还给我费尽心思解决Html转pdf时中文输出的问题&#xff08;html转pdf文件下载之…
阅读更多...
Maven学习笔记

Maven学习笔记

Maven功能介绍 提供了一套标准化的项目结构提供了一套标准化的构建流程&#xff08;编译、测试、打包、发布.....&#xff09;提供了一套依赖管理机制 依赖管理其实就是管理你项目所依赖的第三方资源&#xff08;jar包、插件...&#xff09; ①Maven使用标准的坐标配置来管理…
阅读更多...
Java文件上传解压

Java文件上传解压

目录结构 工具类 枚举 定义文件类型 public enum FileType {// 未知UNKNOWN,// 压缩文件ZIP, RAR, _7Z, TAR, GZ, TAR_GZ, BZ2, TAR_BZ2,// 位图文件BMP, PNG, JPG, JPEG,// 矢量图文件SVG,// 影音文件AVI, MP4, MP3, AAR, OGG, WAV, WAVE}为了避免文件被修改后缀&#xff0…
阅读更多...
手机无法连接服务器1302什么意思？

手机无法连接服务器1302什么意思？

你有没有遇到过手机无法连接服务器&#xff0c;屏幕上显示“1302”这样的错误代码&#xff1f;尤其是在急需使用手机进行工作或联系朋友时&#xff0c;突然出现的连接问题无疑会带来不少麻烦。那么&#xff0c;什么是1302错误&#xff0c;它又意味着什么呢&#xff1f; 1302错…
阅读更多...
最新文章

Copyright @ 2022~2023