红黑树——插入底层实现【C++】面试重灾区!!

目录

前言

一,概念

定义 

二,insert

情况一:仅染色

情况二:单旋 + 染色

情况三:双旋 + 染色

insert代码

三, 红黑树验证(面试题)

产生随机数验证

四,删除

下期预告:用红黑树封装map与 set​​​​​​​

结语


每日一图区:

前言

AVL树是一棵绝对平衡的二叉搜索树,其要求每个节点的左右子树高度差的绝对值都不超过1,这样可以保证查询时高效的时间复杂度,即$log_2 (N)$。但是如果要对AVL树做一些结构修改的操作,性能非常低下,比如:插入时要维护其绝对平衡,旋转的次数比较多,更差的是在删除时,有可能一直要让旋转持续到根的位置。
因此:如果需要一种查询高效且有序的数据结构,而且数据的个数为静态的(即不会改变),可以考虑AVL树,但一个结构经常修改,就不太适合。

 红黑树相对于AVL树的优势包括:

  1. 插入和删除操作更快:红黑树相对于AVL树的平衡条件更加宽松,因此在插入和删除节点时需要进行的旋转操作更少。这使得红黑树的插入和删除操作更快。

  2. 更好的平衡性能:红黑树的平衡性能比AVL树稍差,但是在实际应用中,红黑树的平衡性能已经足够好了。红黑树的插入和删除操作相对较快,这在某些场景下更重要。

  3. 更少的旋转操作:红黑树的旋转操作比AVL树少。旋转操作是一种比较耗时的操作,因此红黑树的插入和删除操作相对更快。

  4. 更好的空间效率:红黑树相对于AVL树需要更少的额外空间来存储平衡因子或颜色信息。这使得红黑树的空间效率更高。

  5. 更广泛的应用:红黑树相对于AVL树应用更广泛。红黑树在很多语言的标准库中都有实现,而AVL树的应用相对较少。

需要注意的是,红黑树和AVL树都是平衡二叉搜索树,选择使用哪种树结构取决于具体的应用场景和需求。

一,概念

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

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

其中,NIL表示一个路径的出口。

定义 

enum color{RED, BLACK};template <class data_type>
struct RBT_Data
{data_type _kv;RBT_Data<data_type>* left = nullptr;RBT_Data<data_type>* right = nullptr;RBT_Data<data_type>* parent = nullptr;color _col;  // 颜色RBT_Data(const data_type& p):_kv(p),_col(RED) // 颜色默认红{}
};template <class data_type>
class RB_Tree
{typedef RBT_Data<data_type> RBT_Data;RBT_Data* root;
};

关于,创建新节点该怎么选颜色。

  • 如果我们选择黑色,那么我们一定会违反性质四(对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点 ),我们为了保持红黑树的结构,就需要调整其他所有的路径。
  • 如果我们选择红色,我们可能会违法性质三(如果一个节点是红色的,则它的两个孩子结点是黑色的 ),而且影响的只是局部,不会影响其他的兄弟树。

因此我们会选择红色作为默认颜色

在AVL树中我们关注树之间的高度,而到了红黑树我们需要关注节点之间的颜色

二,insert

 插入新节点,我们需要检测新节点是否破坏红黑树的性质。

因为 新节点的默认颜色是红色,因此:如果 其双亲节点的颜色是黑色,没有违反红黑树任何性质,则不需要调整;
当新插入节点的双亲节点颜色为红色时,就违反了性质三不能有连在一起的红色节点,此时需要对红黑树分情况来讨论:

情况一:仅染色

特点:uncle存在且为红,parent为红色,cur也为红

 用一个模板图总结该情况:

情况二:单旋 + 染色

特征:没有uncle, parent为红, cur为红

所以在情况二下,比较重要的就是旋转方法+变色,旋转如果有忘记了,可以参考本篇文章:

保姆级认识AVL树【C++】(精讲:AVL Insert)-CSDN博客

 

情况三:双旋 + 染色

特征:没有uncle或者uncle是黑色,parent为红,cur为红。相比较于情况二,情况三的旋转方法是双旋。

这里有一个区分情况二与情况三的小技巧,那就是看grandfather , parent, cur 三节点的线路。如果是直线,则情况二; 折线则情况三

insert代码

bool insert(const pair<K, V>& p){RBT_Data* new_a_d = new RBT_Data(p);if (!root){root = new_a_d;root->_col = BLACK;	}else{RBT_Data* cur = root;RBT_Data* parent = nullptr;while (cur){if (p.first < cur->_kv.first){parent = cur;cur = cur->left;}else if (p.first > cur->_kv.first){parent = cur;cur = cur->right;}else{delete(new_a_d); // 插入失败,删除新建结点return false;}}if (p.first < parent->_kv.first){parent->left = new_a_d;}else{parent->right = new_a_d;}new_a_d->parent = parent;// 调整颜色cur = new_a_d;RBT_Data* par = cur->parent;if (cur == root){cur->_col = BLACK;}while (par && par->_col == RED){RBT_Data* gf = par->parent;RBT_Data* uncle = nullptr;if (gf && par == gf->right){uncle = gf->left;}else if (gf && par == gf->left){uncle = gf->right;}else{assert(false);}if ( uncle && uncle->_col == RED)// 有u且为红{gf->_col = RED;uncle->_col = BLACK;par->_col = BLACK;cur = gf;  // 切换为祖先,进入循环向上par = cur->parent;}else if (!uncle ||(uncle && uncle->_col == BLACK)){   // 情况2 + 3,判断,是否是折线还是直线if (gf->left == par && par->left == cur){  // 右单选RotateR(gf);}else if (gf->right == par && par->right == cur){  // 左单旋RotateL(gf);}else if (gf->left == par && par->right == cur){  // 需要左双旋RotateLR(gf);}else if (gf->right == par && par->left == cur){  // 需要右双旋RotateRL(gf);}else{assert(false);}break;}else{assert(false);}}if ( root->_col == RED){root->_col = BLACK;}return true;}
}

左,右和双旋实现代码跟AVL章节中大差不差,这里给出左单旋的实现,大家照葫芦画瓢一下:

void RotateL(RBT_Data* parent){assert(parent->right);RBT_Data* par = parent;RBT_Data* par_R = par->right;RBT_Data* par_RL = par->right->left;RBT_Data* ppnode = par->parent;par->right = par_RL;if (par_RL)par_RL->parent = par;par_R->left = par;par->parent = par_R;par_R->parent = ppnode;if (!ppnode){root = par_R;}else if (ppnode->left == par){ppnode->left = par_R;}else{ppnode->right = par_R;}par->_col = RED;par_R->_col = BLACK;}

三, 红黑树验证(面试题)

验证红黑树性质

目标:

1. 根是否是黑

2. 没有连续红节点

3. 每条路径所经历的黑节点相同。 

代码:

public:
bool IsBalance(){if (root && root->_col == RED){return false;}int BlackNum = 0; // 所经黑节点的次数int standard = 0;  //设置一个最长路径RBT_Data* cur = root;while (cur){if (cur->_col == BLACK)standard++;cur = cur->left;}return _IsBalance(root->left, BlackNum, standard) && _IsBalance(root->right, BlackNum, standard);}private:
bool _IsBalance(const RBT_Data* cur, int BlackNum, int standard){if (cur == nullptr){return true;}if (cur->_col == BLACK)BlackNum++;if (cur->_col == RED && cur->_col == cur->parent->_col){return false;}return  _IsBalance(cur->left, BlackNum, standard) && _IsBalance(cur->right, BlackNum, standard);}

产生随机数验证

void Random_Test()
{srand(time(0));const size_t N = 10000000;RB_Tree<int, int> t;for (size_t i = 0; i < N; i++){size_t x = rand();t.insert(make_pair(x, x));}cout << t.IsBalance() << endl;
}

四,删除

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

下期预告:用红黑树封装map与 set

结语

   本小节就到这里了,感谢小伙伴的浏览,如果有什么建议,欢迎在评论区评论,如果给小伙伴带来一些收获请留下你的小赞,你的点赞和关注将会成为博主创作的动力

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

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

相关文章

基于跳蛛算法的无人机航迹规划-附代码

基于跳蛛算法的无人机航迹规划 文章目录 基于跳蛛算法的无人机航迹规划1.跳蛛搜索算法2.无人机飞行环境建模3.无人机航迹规划建模4.实验结果4.1地图创建4.2 航迹规划 5.参考文献6.Matlab代码 摘要&#xff1a;本文主要介绍利用跳蛛算法来优化无人机航迹规划。 1.跳蛛搜索算法 …

Python 生成Android不同尺寸的图标

源代码 # -*- coding: utf-8 -*- import sys import os import shutil from PIL import Imagedef generateAndroidIcons():imageSource icon.pngicon Image.open(imageSource)sizes [(android/drawable,512),(android/drawable-hdpi,72),(android/drawable-ldpi,36),(andro…

晨控CK-GW08系列网关控制器与CODESYS软件MODBUSTCP通讯手册

晨控CK-GW08系列是一款支持标准工业通讯协议ModbusTCP的网关控制器,方便用户集成到PLC等控制系统中。系统还集成了8路读写接口&#xff0c;用户可通过通信接口使用Modbus TCP协议对8路读写接口所连接的读卡器进行相对独立的读写操作。 晨控CK-GW08系列网关控制器适用于本公司多…

Docker 学习路线 5:在 Docker 中实现数据持久化

Docker 可以运行隔离的容器&#xff0c;包括应用程序和其依赖项&#xff0c;与主机操作系统分离。默认情况下&#xff0c;容器是临时的&#xff0c;这意味着容器中存储的任何数据在终止后都将丢失。为了解决这个问题并在容器生命周期内保留数据&#xff0c;Docker 提供了各种数…

应用安全四十二:SSO安全

一、什么是SSO SSO是单点登录(Single Sign On)的缩写,是指在多个应用系统中,用户只需要登录一次就可以访问所有相互信任的应用系统。这种方式减少了由登录产生的时间消耗,辅助了用户管理,是比较流行的企业业务整合的解决方案之一。 身份验证过程依赖于双方之间的信任关…

【Redis】hash类型-内部编码使用场景

文章目录 内部编码测试内部编码&#xff1a; 使用场景缓存方式对比 内部编码 哈希的内部编码有两种&#xff1a; ziplist&#xff08;压缩列表&#xff09;&#xff1a;当哈希类型元素个数⼩于hash-max-ziplist-entries配置&#xff08;默认512个&#xff09;、同时所有值都⼩…

Python类继承(单继承)

自定义“鸟”类&#xff0c;“鸣禽”、“猛禽”继承自“鸟”类&#xff0c;“画眉”、“百灵”继承自“鸣禽”&#xff0c;“鹰”、“雕”继承自“猛禽”。 (笔记模板由python脚本于2023年11月06日 19:08:56创建&#xff0c;本篇笔记适合初通Python类的coder翻阅) 【学习的细节…

React使用富文本CKEditor 5,上传图片并可设置大小

上传图片 基础使用&#xff08;标题、粗体、斜体、超链接、缩进段落、有序无序、上传图片&#xff09; 官网查看&#xff1a;https://ckeditor.com/docs/ckeditor5/latest/installation/integrations/react.html 安装依赖 npm install --save ckeditor/ckeditor5-react cked…

cookie、session和Token的区别?JWT又是什么?单点登录又是什么?头大?快进来看看,一文帮你捋清楚~

目录 0、HTTP是无状态的 1、前端标记cookie 1.1、cookie限制空间范围 1.2、cookie限制时间范围 1.3、cookie限制使用方式 2、服务端存储session库 2.1、我们先来简单聊聊session是什么&#xff1f; 2.2、session的存储方式 2.3、session的过期和销毁 2.4、session的分…

hugetlb核心组件

1 概述 hugetlb机制是一种使用大页的方法&#xff0c;与THP(transparent huge page)是两种完全不同的机制&#xff0c;它需要&#xff1a; 管理员通过系统接口reserve一定量的大页&#xff0c;用户通过hugetlbfs申请使用大页&#xff0c; 核心组件如下图&#xff1a; 围绕着…

十年老程序员分享13个最常用的Python深度学习库和介绍,赶紧收藏码住!

文章目录 前言CaffeTheanoTensorFlowLasagneKerasmxnetsklearn-theanonolearnDIGITSBlocksdeepypylearn2Deeplearning4j关于Python技术储备一、Python所有方向的学习路线二、Python基础学习视频三、精品Python学习书籍四、Python工具包项目源码合集①Python工具包②Python实战案…

选择合适的Python Web框架

Python 是一种功能强大的编程语言&#xff0c;广泛应用于 Web 开发领域。FastAPI 和 Flask 是 Python Web 开发中最受欢迎的两个框架。本文将对 FastAPI 和 Flask 进行综合对比&#xff0c;探讨它们在语法和表达能力、生态系统和社区支持、性能和扩展性、开发工具和调试支持、安…

MySQL数据库之表操作

目录 表的操作1.创建表创建表案例 2.查看表结构3.修改表4.删除表 表的操作 1.创建表 语法&#xff1a; CREATE TABLE table_name (field1 datatype,field2 datatype,field3 datatype ) character set 字符集 collate 校验规则 engine 存储引擎;说明&#xff1a; field 表示列…

无需专线、无需固定公网IP,各地安防数据如何高效上云?

某专注于安防领域的企业&#xff0c;供机场、金融、智慧大厦等行业&#xff0c;包括门禁系统、巡更系统、视频监控在内的整体解决方案。 在实际方案交付过程中&#xff0c;往往需要在多地分支机构分别部署相应的安防设备&#xff0c;并将产生的数据实时统一汇总至云平台进行管理…

SpringBoot项目打包与运行

1.clean生命周期 说明&#xff1a;为了项目能够正确打包&#xff0c;先清理打包文件。 2.package生命周期 说明&#xff1a;打包后生成以下目录。 2.1问题 说明&#xff1a;springboot_08_ssmp-0.0.1-SNAPSHOT.jar中没有主清单属性。 2.2解决 说明&#xff1a;注释skip&…

吃透BGP,永远绕不开这些基础概述,看完再也不怕BGP了!

你们好&#xff0c;我的网工朋友。 总有人在私信里抱怨&#xff0c;BGP实在是太难了&#xff01; 一是这玩意儿本来就很复杂&#xff0c;需要处理大量的路由信息和复杂的算法&#xff1b;再一个是需要你有一定的实战经验才能深入理解运作。 虽然BGP确实有一定难度&#xff0c…

JSP 中医知识管理系统myeclipse开发sql数据库BS模式java编程网页结构

一、源码特点 JSP 中医知识管理系统 是一套完善的web设计系统&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;比较流行的ssh框架系统具有完整的源代码和数据库&#xff0c;myeclipse开发系统主要采用B/S模式开发。 javaWeb中医知识系统 二、功能介绍 此次系统主要…

stm32 ADC

目录 简介 stm32的adc 框图 ①电压输入范围 ②输入通道 ​编辑③ADC通道 ④ADC触发 ⑤ADC中断 ⑥ADC数据 ⑦ADC时钟 ADC的四种转换模式 hal库代码 标准库代码 简介 自然界的信号几乎都是模拟信号&#xff0c;比如光亮、温度、压力、声音&#xff0c;而为了方便存储、…

Ps:PSDT 模板文件

自 Photoshop CC 2015.5 版以后&#xff0c;Ps 中新增了一种文件格式&#xff1a;.PSDT。 说明&#xff1a; PSD、PDD、PSDT 都是 Ps 的专用文件格式&#xff0c;需要继续在 Ps 中进行编辑的文件可存为此类格式。 PSD Photoshop document Photoshop 默认文档格式&#xff0c;支…