数据结构-红黑树_况祥彬的博客-程序员宅基地_红黑树增删改查时间复杂度

技术标签: 数据结构与算法  数据结构  

红黑树

红黑树的五大特性:

  1. 根节点是【黑色】
  2. 【红色】节点的子节点一定都是【黑色】,反之亦然
  3. 每个叶子节点都是黑色的空节点(NIL),因为叶子节点不存储数据
  4. 任意一个节点到叶子节点的路径上所包含的【黑色】节点的数量是相同的
    这个也称之为【黑色完美平衡】
  5. 新插入的节点必须是【红色】
    为什么?如果新插入的节点是【黑色】,那不管是在插入到那里,一定会破坏黑色完美平衡的

为什么红黑树被广泛应用?

二叉搜索树bst极端情况下时间复杂度退化为O(n)

平衡二叉树AVL 虽然效率非常高,但是每次插入、删除都要做调整,所以对于有频繁的插入、删除操作的数据集合,使用 AVL 树的代价就有点高了。

红黑树即不像二叉查找树那样存在复杂度退化的问题,
也不会像完成平衡二叉树那样为了保证完全的平衡而过多的旋转调整。
算是在查找和增删之间取了很好的平衡。
红黑树的高度近似 log2n,增删改查操作的时间复杂度都是 O(logn)

应用场景:

  • java的hashmap、 TreeMap 、TreeSet 底层用到红黑树

  • c++ stl中的map、set底层就是红黑树

  • epoll在内核中的实现,用红黑树管理文件描述符fd

插入过程的旋转变色

详细图文

1、当前节点为空,直接插入即可
2、插入的节点已经存在,直接替换即可
3、插入节点的父节点为【黑色节点】,找到父节点,直接插入即可。因为这个树本来就是黑色完美平衡了,再新插入一个新的红色节点,并不会破坏树的平衡以及红黑树的特性。

4、插入节点的父节点为红色
现在,插入的节点的父节点为红色节点,而红色节点一定不可能为根节点,所以可以推断出新插入节点的父节点一定还有父节点
在这里插入图片描述
那现在很显然违反了上面的特性 3( 每个【红色】节点的两个子节点一定都是【黑色】),而现在是两个红色节点相连了,这个该怎么处理?此时又继续拆分不同的情况了

第 4-1 种情况:插入节点的叔叔节点存在,且为红色
这个时候你看的树大致是这样子的结构
在这里插入图片描述
解决办法:① 将 P 和 U 变成黑色;② 将 PP 变成 红色
如下图:
在这里插入图片描述
第 4-2 种情况:叔叔节点不存在,且插入节点的【父节点】是插入节点爷爷节点的【左子节点】
在这里插入图片描述

  • 第 4-2-1 种情况:
    插入节点为其父节点的左子节点,也即 LL 双红色的情况(第一个 L 表示插入节点的父节点,第二个 L 表示插入节点)
    这种情况的完整的变换流程如下:

在这里插入图片描述

  • 第 4-2-2 种情况:
    插入节点为其父节点的右子节点,也即 LR 双红色的情况
    其完成的变换流程如下:
    在这里插入图片描述
    第 4-3 种情况:叔叔节点不存在,且插入节点的【父节点】是插入节点爷爷节点的【右子节点】
    在这里插入图片描述
    这种情况依旧是继续区分插入节点是其父节点的左子节点还是右子节点

  • 第 4-3-1 种情况:
    插入节点为其父节点的右子节点,也即 RR 双红色的情况(第一个 R 是插入节点的父节点,第二个 R 是插入节点)
    其整个转换流程是这样的
    在这里插入图片描述

  • 第 4-3-2 种情况:
    插入节点为其父节点的左子节点,也即 RL 双红色的情况
    其完整的转换流程是这样子的:
    在这里插入图片描述

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_40337086/article/details/113702730

智能推荐

Ubuntu Linux下的PDF阅读器推荐——Okular_DechinPhy的博客-程序员宅基地

安装方法在Ubuntu下直接使用sudo apt-get install okular即可,如果中间遇到依赖项的问题,可以通过运行sudo apt --fix-broken install来自动修复。参考连接https://blog.csdn.net/flycappuccino/article/details/80816311...

用好Lua+Unity,让性能飞起来——Lua与C#交互篇_FreedomRoad~的博客-程序员宅基地

用好Lua+Unity,让性能飞起来——Lua与C#交互篇张鑫6 个月前转载自:https://zhuanlan.zhihu.com/p/23559893原文地址:用好Lua+Unity,让性能飞起来——Lua与C#交互篇整合Lua是目前最强大的Unity热更新方案,毕竟这是唯一可以支持iOS热更新的办法。然而作为一个重度uLua用户,我们踩过了很多坑才将u

mysql强制开启ssl_MySQL Server 5.7 开启SSL功能_18125857287的博客-程序员宅基地

背景描述MySQLserver默认不开启SSL安全通信,非本地用户登录时只要求提供用户名、密码、登录源IP即可进入鉴权;本地用户可以使用socket连接,进入鉴权。启用SSL安全通信以后,在以上鉴权基础上,需要client提供对应的认证文件和Key文件。检查SSL配置状态SSL检查方式:show variables like ‘%ssl%’have_ssl和have_openssl默认为DISAB...

[Coolite]上传文件_厦门德仔的博客-程序员宅基地

我刚开始学习COOLITE 今天群里一个朋友发一个上传文件的代码 收藏先看看了 好像没啥新意

在Yarn上运行spark-shell和spark-sql命令行_迷途小码的博客-程序员宅基地

spark-shell On Yarn如果你已经有一个正常运行的Hadoop Yarn环境,那么只需要下载相应版本的Spark,解压之后做为Spark客户端即可。需要配置Yarn的配置文件目录,export HADOOP_CONF_DIR=/etc/hadoop/conf   这个可以配置在spark-env.sh中。运行命令:cd $SPARK_HOME/bin./s

随便推点

Unity Shader-后处理:景深_cbbbc的博客-程序员宅基地

一.简介景深一直是我最喜欢的效果之一,最早接触CE3的时候,发现CE引擎默认就支持景深的效果,当时感觉这个效果特别酷炫,如今投身于Unity的怀抱中,准备用Unity实现以下传说中的景深效果。所谓景深,是摄影的一个专业术语:在聚焦完成后,在焦点前后的范围内都能形成清晰的像,这一前一后的距离范围,便叫做景深,也是被摄物体能清晰成像的空间深度。在景深范围内景物影像的清晰度并

ubuntu安装(Wireless 8265 / 8275网卡)---failed, not work!!!!_narutojxl的博客-程序员宅基地

Failed, not work!!!!, please do not try!!!linux官网无线驱动: https://wireless.wiki.kernel.org/(Wireless 8265 / 8275网卡) 支持的内核版本是 4.6+, Ubuntu14.04内核是4.4 ,按照前面的帖子升级到 4.6.4。先安装固件 https://wireless....

PBC Library Manual(PBC库手册)翻译(五)_BufferPools的博客-程序员宅基地

目录5.参数(Param)函数5.1 Param生成5.参数(Param)函数Pairing是由 pairing parameter初始化得到,这些参数是pbc_param_t类型的对象。一些应用程序可以忽略此数据类型,因为pairing_init_set_str()函数在后台处理了这类数据:这个函数读取了一个字符串作为一个pbc_param_t,然后使用这些参数初始化了pairing。// 从字符串s初始化pairing参数,成功则返回0,其他情况返回1int pbc_pa..

SQL SERVER 与ACCESS、EXCEL的数据转换_厦门德仔的博客-程序员宅基地

<br />--这是用代码的.SQL SERVER 与ACCESS、EXCEL的数据转换熟悉SQL SERVER 2000的数据库管理员都知道,其DTS可以进行数据的导入导出,其实,我们也可以使用Transact-SQL语句进行导入导出操作。在Transact-SQL语句中,我们主要使用OpenDataSource函数、OPENROWSET 函数,关于函数的详细说明,请参考SQL联机帮助。利用下述方法,可以十分容易地实现SQL SERVER、ACCESS、EXCEL数据转换,详细说明如下:一

Activty中实现左右滑动屏幕监听_generallizhong的博客-程序员宅基地

如今,手机屏幕越来越大,连菜单键都逐渐被取缔,为了方便用户操作,这里提供一个向屏幕左右滑动可监听其滑动来处理跳转等相关动作。最后会附上DEMO。1、在这里使用的是简单listview,左右滑动时不会影响item的监听,以下是核心代码,代码中基本都有注释。public class GestureTestActivity extends Activity { /** * 自...

登录PL/SQL后操作oracle提示ORA-01109:数据库未打开_四方云动的博客-程序员宅基地

SQL> startup mountORA-01081: 无法启动已在运行的 ORACLE - 请首先关闭它SQL> shutdown immediateORA-01109: 数据库未打开已经卸载数据库。ORACLE 例程已经关闭。SQL> startup mountORACLE 例程已经启动。Total System Global Area 6123683

推荐文章

热门文章

相关标签