深入理解C++红黑树的底层实现及应用

文章目录

  • 1、红黑树简介
    • 1.1 、概述:介绍红黑树的定义、特点和用途。
  • 2、红黑树节点的定义
  • 3、红黑树结构
    • 3.1、红黑树的插入操作
  • 4、红黑树的验证
    • 4.1、红黑树的删除
    • 4.2、红黑树与AVL树的比较
    • 4.3、红黑树的应用
  • 5、总结

1、红黑树简介

1.1 、概述:介绍红黑树的定义、特点和用途。

如果发明AVL树的人是大牛的话,那么发明红黑树的人简直是天才。
红黑树和AVL树都是自平衡的二叉搜索树,它们在解决相同问题上有一些不同的权衡。
AVL树是最早提出的自平衡二叉搜索树之一。它通过维护每个节点的平衡因子(即右子树高度减去左子树高度)来保持树的平衡。当插入或删除操作导致某个节点的平衡因子超过1或小于-1时,需要进行旋转操作来重新平衡整棵树。这使得AVL树能够提供更加严格的平衡性,对于查找操作具有较快的时间复杂度。
然而,AVL树的平衡性是以牺牲部分插入和删除操作的效率为代价的。由于要保持严格的平衡,每次插入或删除一个节点后,可能需要进行多次旋转操作来恢复平衡,这会导致较高的调整成本。因此,在频繁执行插入和删除操作的场景下,AVL树的性能可能不如其他数据结构。

红黑树则是为了解决AVL树在插入和删除操作上的效率问题而引入的(不同场景用不同的树)。相比于AVL树的严格平衡性,红黑树放宽了平衡的要求,以牺牲部分平衡性为代价来提高插入和删除操作的效率

红黑树通过引入颜色标记和旋转操作来维护树的平衡。它的平衡性是基于一组规则,而不像AVL树那样严格依赖平衡因子。这使得红黑树在进行插入和删除操作时需要较少的旋转操作,从而降低了调整成本。
总结起来,红黑树相对于AVL树具有更好的插入和删除操作的性能,但查找操作的性能略逊于AVL树。因此,选择使用红黑树还是AVL树取决于具体应用场景中对插入、删除和查找操作的需求和权衡。

定义:

红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路
径会比其他路径长出俩倍,因而是接近平衡的。
在这里插入图片描述

性质:

  1. 每个结点不是红色就是黑色
  2. 根节点是黑色的
  3. 如果一个节点是红色的,则它的两个孩子结点是黑色的
  4. 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
    思考:为什么满足上面的性质,红黑树就能保证:其最长路径中节点个数不会超过最短路径节点个数的两倍?

第4条性质要求每个结点到其所有后代叶子结点的简单路径上包含相同数量的黑色结点。因此,在红黑树中,任意从根节点到叶子结点的路径都具有相同数量的黑色结点。这意味着没有一条路径会比其他路径更长。
同时,根据第3条性质,如果一个节点是红色的,则它的两个孩子结点必须是黑色的。这样,通过限制红色节点的位置,红黑树避免了出现连续的红色节点路径。这样做的目的是防止某些路径过于深,导致树的高度增加。由于以上性质的限制,红黑树的每条路径上的黑色节点数量是相等的,并且没有连续的红色节点路径。这就保证了最长路径(从根节点到任意叶子结点的路径)中的节点个数不会超过最短路径的两倍。这种平衡性质确保了红黑树在动态操作中具有较好的性能。
总结起来,通过限制红色节点的位置和要求每条路径上包含相同数量的黑色节点,红黑树可以保持相对平衡,并且最长路径中的节点个数不会超过最短路径的两倍。这使得红黑树在插入、删除和查找等操作时都能够获得较好的时间复杂度。

2、红黑树节点的定义

// 节点的颜色
enum Color{RED, BLACK};
// 红黑树节点的定义
template<class ValueType>
struct RBTreeNode
{RBTreeNode(const ValueType& data = ValueType(),Color color = RED): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _color(color){}RBTreeNode<ValueType>* _pLeft;  // 节点的左孩子RBTreeNode<ValueType>* _pRight;  // 节点的右孩子RBTreeNode<ValueType>* _pParent; // 节点的双亲(红黑树需要旋转,为了实现简单给//出该字段)ValueType _data;       // 节点的值域Color _color;        // 节点的颜色
};

思考:在节点的定义中,为什么要将节点的默认颜色给成红色的?

在红黑树中,将节点的默认颜色设置为红色是出于实现方便和性能优化的考虑。
红黑树通过一些特定的规则来保持平衡,其中之一是确保没有两个连续的红色节点。这个规则的目的是防止红黑树变得过度不平衡,并且可以在插入和删除操作时提供更好的性能。
如果将新插入的节点的默认颜色设置为黑色,那么在执行插入操作后,可能会违反红黑树的某些性质。此时,我们需要进行调整操作来修复违反的性质,这可能涉及到旋转和重新着色等复杂的操作。
相比之下,将新插入的节点的默认颜色设置为红色可以简化插入操作的实现。因为新插入的节点是红色的,它不会破坏红黑树的任何性质。插入操作只需按照二叉搜索树的规则将节点放置在正确的位置上,然后再利用一系列的旋转和重新着色操作来恢复红黑树的平衡性。
通过将节点的默认颜色设置为红色,我们可以减少在插入操作中所需的调整次数,从而提高了性能。这种选择也是为了简化红黑树的实现和维护,使其更易于理解和调试。
需要注意的是,默认颜色为红色只是一种约定,并不是强制规定。在某些特殊情况下,可以将默认颜色设置为黑色或其他颜色,但要确保插入操作和平衡调整仍然能够正确工作并满足红黑树的性质。

3、红黑树结构

为了后续实现关联式容器简单,红黑树的实现中增加一个头结点,因为根节点必须为黑色,为了
与根节点进行区分,将头结点给成黑色,并且让头结点的 pParent 域指向红黑树的根节点,pLeft
域指向红黑树中最小的节点,_pRight域指向红黑树中最大的节点,如下:
在这里插入图片描述

3.1、红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件,因此红黑树的插入可分为两步:

  1. 按照二叉搜索的树规则插入新节点
template<class ValueType>
class RBTree
{//……bool Insert(const ValueType& data){PNode& pRoot = GetRoot();if (nullptr == pRoot){pRoot = new Node(data, BLACK);// 根的双亲为头节点pRoot->_pParent = _pHead;_pHead->_pParent = pRoot;}else{// 1. 按照二叉搜索的树方式插入新节点// 2. 检测新节点插入后,红黑树的性质是否造到破坏,//  若满足直接退出,否则对红黑树进行旋转着色处理}// 根节点的颜色可能被修改,将其改回黑色pRoot->_color = BLACK;_pHead->_pLeft = LeftMost();_pHead->_pRight = RightMost();return true;
}
private:PNode& GetRoot(){ return _pHead->_pParent;}// 获取红黑树中最小节点,即最左侧节点PNode LeftMost();// 获取红黑树中最大节点,即最右侧节点PNode RightMost();
private:PNode _pHead;
}
  1. 检测新节点插入后,红黑树的性质是否造到破坏
    因为新节点的默认颜色是红色,因此:如果其双亲节点的颜色是黑色,没有违反红黑树任何
    性质,则不需要调整;但当新插入节点的双亲节点颜色为红色时,就违反了性质三不能有连
    在一起的红色节点,此时需要对红黑树分情况来讨论
    约定:cur为当前节点,p为父节点,g为祖父节点,u为叔叔节点
情况一: cur为红,p为红,g为黑,u存在且为红

在这里插入图片描述
cur和p均为红,违反了性质三,此处能否将p直接改为黑?
解决方式:将p,u改为黑,g改为红,然后把g当成cur,继续向上调整。

情况二: cur为红,p为红,g为黑,u不存在/u存在且为黑

在这里插入图片描述
p为g的左孩子,cur为p的左孩子,则进行右单旋转;相反,
p为g的右孩子,cur为p的右孩子,则进行左单旋转
p、g变色–p变黑,g变红

情况三: cur为红,p为红,g为黑,u不存在/u存在且为黑

在这里插入图片描述
p为g的左孩子,cur为p的右孩子,则针对p做左单旋转;相反,
p为g的右孩子,cur为p的左孩子,则针对p做右单旋转
则转换成了情况2
在这里插入图片描述
针对每种情况进行相应的处理即可。

bool Insert(const ValueType& data)
{// ...// 新节点插入后,如果其双亲节点的颜色为空色,则违反性质3:不能有连在一起的红色结while(pParent && RED == pParent->_color)
{// 注意:grandFather一定存在// 因为pParent存在,且不是黑色节点,则pParent一定不是根,则其一定有双亲PNode grandFather = pParent->_pParent;// 先讨论左侧情况
if(pParent == grandFather->_pLeft)
{PNode unclue = grandFather->_pRight;
// 情况三:叔叔节点存在,且为红
if(unclue && RED == unclue->_color)
{pParent->_color = BLACK;unclue->_color = BLACK;grandFather->_color = RED;pCur = grandFather;pParent = pCur->_pParent;
}else{// 情况五:叔叔节点不存在,或者叔叔节点存在且为黑if(pCur == pParent->_pRight){_RotateLeft(pParent);swap(pParent, pCur);}// 情况五最后转化成情况四grandFather->_color = RED;pParent->_color = BLACK;_RotateRight(grandFather);}
}
else{// 右侧请学生们自己动手完成}
}// ...
} 

4、红黑树的验证

红黑树的检测分为两步:

  1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
  2. 检测其是否满足红黑树的性质
bool IsValidRBTree()
{PNode pRoot = GetRoot();// 空树也是红黑树if (nullptr == pRoot)return true;// 检测根节点是否满足情况if (BLACK != pRoot->_color){cout << "违反红黑树性质二:根节点必须为黑色" << endl;return false;}// 获取任意一条路径中黑色节点的个数size_t blackCount = 0;PNode pCur = pRoot;while (pCur){if (BLACK == pCur->_color)blackCount++;pCur = pCur->_pLeft;}// 检测是否满足红黑树的性质,k用来记录路径中黑色节点的个数size_t k = 0;return _IsValidRBTree(pRoot, k, blackCount);
}
bool _IsValidRBTree(PNode pRoot, size_t k, const size_t blackCount)
{//走到null之后,判断k和black是否相等if (nullptr == pRoot){if (k != blackCount){cout << "违反性质四:每条路径中黑色节点的个数必须相同" << endl;return false;}return true;}
// 统计黑色节点的个数if (BLACK == pRoot->_color)k++;// 检测当前节点与其双亲是否都为红色PNode pParent = pRoot->_pParent;if (pParent && RED == pParent->_color && RED == pRoot->_color){cout << "违反性质三:没有连在一起的红色节点" << endl;return false;}return _IsValidRBTree(pRoot->_pLeft, k, blackCount) &&_IsValidRBTree(pRoot->_pRight, k, blackCount);
}

4.1、红黑树的删除

红黑树的删除本节不做讲解,有兴趣的同学可参考:《算法导论》或者《STL源码剖析》
http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html

4.2、红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树,增删改查的时间复杂度都是O( l o g 2 N log_2 N log2N),红黑树不追
求绝对平衡,其只需保证最长路径不超过最短路径的2倍,相对而言,降低了插入和旋转的次数,
所以在经常进行增删的结构中性能比AVL树更优,而且红黑树实现比较简单,所以实际运用中红
黑树更多。

4.3、红黑树的应用

  1. C++ STL库 – map/set、mutil_map/mutil_set
  2. Java 库
  3. linux内核
  4. 其他一些库
    http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html

5、总结

红黑树是一种自平衡的二叉搜索树,通过满足一系列性质来保证查找、插入和删除操作的效率。它是一种广泛应用于各种场景的重要数据结构,展示了平衡二叉搜索树的强大功能和灵活性。尽管红黑树已经具有很好的性能,但未来的研究还可以进一步改进其性能或扩展其应用范围。例如,可以研究红黑树的内存使用优化、动态调整参数等新特性来更好地适应不断变化的应用需求。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/167294.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Linux | 深入浅出冯诺依曼

前言 但凡是科班出生的小伙伴多多稍稍应该都听过冯诺依曼体系吧&#xff0c;这似乎已成为入门计算机的必备知识了&#xff0c;本章就带着大家一起去理解冯诺依曼体系&#xff1b; 一、体系构成 冯诺依曼体系主张计算机由五大部件组成&#xff0c;如下所示&#xff1b; 输入设备…

Java设计模式 | 基于订单批量支付场景,对策略模式和简单工厂模式进行简单实现

基于订单批量支付场景&#xff0c;对策略模式和简单工厂模式进行简单实现 文章目录 策略模式介绍实现抽象策略具体策略1.AliPayStrategy2.WeChatPayStrategy 环境 使用简单工厂来获取具体策略对象支付方式枚举策略工厂接口策略工厂实现 测试使用订单实体类对订单进行批量支付结…

Stable Diffusion WebUI报错RuntimeError: Torch is not able to use GPU解决办法

新手在安装玩Stable Diffusion WebUI之后会遇到各种问题&#xff0c; 接下来会慢慢和你讲解如何解决这些问题。 在我们打开Stable Diffusion WebUI时会报错如下&#xff1a; RuntimeError: Torch is not able to use GPU&#xff1b;add --skip-torch-cuda-test to COMMANDL…

操作系统——吸烟者问题(王道视频p34、课本ch6)

1.问题分析&#xff1a;这个问题可以看作是 可以生产多种产品的 单生产者-多消费者问题 2.代码——这里就是由于同步信号量的初值都是1&#xff0c;所以没有使用mutex互斥信号&#xff0c; 总共4个同步信号量&#xff0c;其中一个是 finish信号量

在Lichee RV Dock上的不成功的烧录尝试

最近在学基于risc-v的简单操作系统&#xff0c;刚好手里有块Lichee RV Dock 的板子&#xff0c;所以在学了基础的"hello, world"程序后&#xff0c;想着能不能把这个程序烧录到板子上&#xff0c;简单的做个实验。 要完成这个任务&#xff0c;需要将程序烧录到sd卡上…

专访 Web3Go 新产品 Reiki:培育 AI 原生数字资产与创意新土壤

从 DeFi 到 NFTFi、SocialFi&#xff0c;web3 从业者在尝试 crypto 与区块链技术能为我们的生活、创作、娱乐和文化带来何种新体验&#xff0c;而生成式人工智能的突破性发展则为我们与链上世界的交互、社区内容创作等带来了新的体验&#xff0c;改变互动、交易和价值创造方式。…

容器技术基础

1. Linux Namespace和Cgroups 对于 Docker 等大多数 Linux 容器来说&#xff0c;Cgroups 技术是用来制造约束的主要手段&#xff0c;而 Namespace 技术则是用来修改进程视图的主要方法。 1.1 PID Namespace //Linux 系统正常创建线程 int pid clone(main_function, stack_s…

Docker数据管理、端口映射、容器互联

目录 一、Docker 的数据管理&#xff1a; 1&#xff0e;数据卷&#xff1a; 1.1 宿主机目录/var/www/html 挂载到容器中的/data1&#xff1a; 1.2 测试&#xff1a; 2&#xff0e;数据卷容器&#xff1a; 2.1 创建一个容器作为数据卷容器&#xff1a; 2.2 挂载a1容器中的数据卷…

《数据结构与算法之美》读书笔记1

Java的学习 方法参数多态&#xff08;向上和向下转型&#xff09; 向上转型&#xff1a; class Text{public static void main(String[] args) {Animals people1 new NiuMa();people1.eat1();//调用继承后公共部分的方法&#xff0c;没重写调用没重写的&#xff0c;重写了调…

Mysql数据库 2.SQL语言 数据类型与字段约束

Mysql数据类型 数据类型&#xff1a;指的是数据表中的列文件支持存放的数据类型 1.数值类型 Mysql当中有多种数据类型可以存放数值&#xff0c;不同的类型存放的数值的范围或者形式是不同的 注&#xff1a;前三种数字类型我们在实际研发中用的很少&#xff0c;一般整数类型…

【C++】:类和对象(中)之拷贝构造函数+赋值运算符重载

拷贝构造函数 概念 在现实生活中&#xff0c;可能存在一个与你一样的自己&#xff0c;我们称其为双胞胎 那在创建对象时&#xff0c;可否创建一个与已存在对象一某一样的新对象呢&#xff1f; 拷贝构造函数&#xff1a;只有单个形参&#xff0c;该形参是对本类类型对象的引用…

OpenP2P实现内网穿透远程办公

OpenP2P是一个开源、免费、轻量级的P2P共享网络。你的设备将组成一个私有P2P网络&#xff0c;里面的设备可以直接访问其它成员&#xff0c;或者通过其它成员转发数据间接访问。如果私有网络无法完成通信&#xff0c;将会到公有P2P网络寻找共享节点协助通信。 相比BT网络用来共享…

【C++】哈希的应用 -- 布隆过滤器

文章目录 一、布隆过滤器提出二、布隆过滤器概念三、布隆过滤器哈希函数个数的选择四、布隆过滤器的实现1.布隆过滤器的插入2.布隆过滤器的查找3.布隆过滤器删除4.完整代码实现 五、布隆过滤器总结1.布隆过滤器优点2.布隆过滤器缺陷3.布隆过滤器的应用4.布隆过滤器相关面试题 一…

华为云HECS云服务器docker环境下安装nacos

华为云HECS云服务器&#xff0c;安装docker环境&#xff0c;查看如下文章。 华为云HECS安装docker-CSDN博客 一、拉取镜像 docker pull nacos/nacos-server二、宿主机创建挂载目录 执行如下命令&#xff1a; mkdir -p /usr/local/nacos/logs mkdir -p /usr/local/nacos/con…

【iOS】UITableView总结(Cell的复用原理、自定义Cell、UITableViewCell协议方法)

UITableView 列表的特点&#xff1a; 数据量大样式较为统一通常需要分组垂直滚动通常可视区只有一个 -> 视图的复用 UITableViewDataSource UITableView作为视图&#xff0c;只负责展示&#xff0c;协助管理&#xff0c;不管理数据 需要开发者为UITableView提供展示所需…

基于springboot实现java学习平台项目【项目源码+论文说明】计算机毕业设计

基于springboot实现java学习平台演示 摘要 在Internet高速发展的今天&#xff0c;我们生活的各个领域都涉及到计算机的应用&#xff0c;其中包括学习平台的网络应用&#xff0c;在外国学习平台已经是很普遍的方式&#xff0c;不过国内的管理平台可能还处于起步阶段。学习平台具…

网络编程-java基础

两台电脑之间的通信形成了网络 最小的网络&#xff1a;局域网 校园网(局域网) 城域网(一个市) 广域网(全球) 为什么我发QQ你能收到&#xff0c;这是因为我发的消息实际上是发给了QQ服务器&#xff0c;并不是直接发给你的&#xff0c; 我是与QQ服务器进行通信的&#xff0c…

正方形(Squares, ACM/ICPC World Finals 1990, UVa201)rust解法

有n行n列&#xff08;2≤n≤9&#xff09;的小黑点&#xff0c;还有m条线段连接其中的一些黑点。统计这些线段连成了多少个正方形&#xff08;每种边长分别统计&#xff09;。 行从上到下编号为1&#xff5e;n&#xff0c;列从左到右编号为1&#xff5e;n。边用H i j和V i j表示…

深度学习零基础教程

代码运行软件安装&#xff1a; anaconda:一个管理环境的软件–>https://blog.csdn.net/scorn_/article/details/106591160&#xff08;可选装&#xff09; pycharm&#xff1a;一个深度学习运行环境–>https://blog.csdn.net/scorn_/article/details/106591160&#xf…

2023/10/30-LED灯驱动开发

k1.c #include <linux/init.h> #include <linux/module.h> #include <linux/fs.h> #include <linux/uaccess.h> #include <linux/io.h> #include "head.h" char kbuf[128] {}; unsigned int major; //定义三个指针指向映射后的虚拟内…