程序员经验分享-hwhale

红黑树并没有我们想象的那么难(上)

2023-11-13

<红黑树并没有我们想象的那么难> 上、下两篇已经完成, 希望能帮助到大家.

红黑树并没有想象的那么难, 初学者觉得晦涩难读可能是因为情况太多. 红黑树的情况可以通过归结, 通过合并来得到更少的情况, 如此可以加深对红黑树的理解. 网络上的大部分红黑树的讲解因为没有「合并」. 红黑树的五个性质:

性质1. 节点是红色或黑色。

性质2. 根是黑色。

性质3. 所有叶子都是黑色（叶子是NIL节点）。

性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

性质5. 从任一节点到其每个叶子的所有简单路径 都包含相同数目的黑色节点。

红黑树的数据结构

摘自 sgi stl 红黑树数据结构定义:

typedef bool _Rb_tree_Color_type;
const _Rb_tree_Color_type _S_rb_tree_red = false ;
const _Rb_tree_Color_type _S_rb_tree_black = true ;
 
struct _Rb_tree_node_base
{
   typedef _Rb_tree_Color_type _Color_type;
   typedef _Rb_tree_node_base* _Base_ptr;
 
   _Color_type _M_color;
   _Base_ptr _M_parent;
   _Base_ptr _M_left;
   _Base_ptr _M_right;
 
   static _Base_ptr _S_minimum(_Base_ptr __x)
   {
     while  (__x->_M_left != 0) __x = __x->_M_left;
     return  __x;
   }
 
   static _Base_ptr _S_maximum(_Base_ptr __x)
   {
     while  (__x->_M_right != 0) __x = __x->_M_right;
     return  __x;
   }
};
 
template <class _Value>
struct _Rb_tree_node : public _Rb_tree_node_base
{
   typedef _Rb_tree_node<_Value>* _Link_type;
   _Value _M_value_field;
};

二叉搜索树的插入删除操作

在展开红黑树之前, 首先来看看普通二叉搜索树的插入和删除. 插入很容易理解, 比当前值大就往右走, 比当前值小就往左走. 详细展开的是删除操作.

二叉树的删除操作有一个技巧, 即在查找到需要删除的节点 X; 接着我们找到要么在它的左子树中的最大元素节点 M、要么在它的右子树中的最小元素节点 M, 并交换(M,X). 此时, M 节点必然至多只有一个孩子; 最后一个步骤就是用 M 的子节点代替 M 节点就完成了. 所以, 所有的删除操作最后都会归结为删除一个至多只有一个孩子的节点, 而我们删除这个节点后, 用它的孩子替换就好了. 将会看到 sgi stl map 就是这样的策略.

在红黑树删除操作讲解中, 我们假设代替 M 的节点是 N(下面的讲述不再出现 M).

红黑树的插入

插入新节点总是红色节点, 因为不会破坏性质 5, 尽可能维持所有性质.

假设, 新插入的节点为 N, N 节点的父节点为 P, P 的兄弟(N 的叔父)节点为 U, P 的父亲(N 的爷爷)节点为 G. 所以有如下的印象图:

rbtree0

插入节点的关键是:

  1. 插入新节点总是红色节点
  2. 如果插入节点的父节点是黑色, 能维持性质
  3. 如果插入节点的父节点是红色, 破坏了性质. 故插入算法就是通过重新着色或旋转, 来维持性质

插入算法详解如下, 走一遍红黑树维持其性质的过程:

第 0.0 种情况, N 为根节点, 直接 N->黑. over
第 0.1 种情况, N 的父节点为黑色, 这不违反红黑树的五种性质. over

第 1 种情况, N,P,U 都红(G 肯定黑). 策略: G->红, N,P->黑. 此时, G 红, 如果 G 的父亲也是红, 性质又被破坏了, HACK: 可以将 GPUN 看成一个新的红色 N 节点, 如此递归调整下去; 特俗的, 如果碰巧将根节点染成了红色, 可以在算法的最后强制 root->黑.

rbtre01

第 2 种情况, P 为红, N 为 P 右孩子, N 为红, U 为黑或缺少. 策略: 旋转变换, 从而进入下一种情况:

rbtree02

第 3 种情况, 可能由第二种变化而来, 但不是一定: P 为红, N 为 P 左孩子, N 为红. 策略: 旋转, 交换 P,G 颜色, 调整后, 因为 P 为黑色, 所以不怕 P 的父节点是红色的情况. over

rbtree03

红黑树的插入就为上面的三种情况. 你可以做镜像变换从而得到其他的情况.

红黑树的删除

假设 N 节点见上面普通二叉树删除中的定义, P 为 N 父节点, S 为 N 的兄弟节点, SL,SR 分别是 S 的左右子节点. 有如下印象图:

rbtree04 N 没有任何的孩子!

删除节点的关键是:

  1. 如果删除的是红色节点, 不破坏性质
  2. 如果删除的是黑色节点, 那么这个路径上就会少一个黑色节点, 破坏了性质. 故删除算法就是通过重新着色或旋转, 来维持性质

删除算法详解如下, 走一遍红黑树维持其性质的过程:

第 0.0 情况, N 为根节点. over
第 0.1 情况, 删除的节点为红. over
第 0.2 情况, 删除节点为黑, N 为红. 策略: N->黑, 重新平衡. over

第 1 情况, N,P,S,SR,SL 都黑. 策略: S->红. 通过 PN,PS 的黑色节点数量相同了, 但会比其他路径多一个, 解决的方法是在 P 上从情况 0 开始继续调整. 为什么要这样呢? HANKS: 因为既然 PN,PS 路径上的黑节点数量相同而且比其他路径会少一个黑节点, 那何不将其整体看成了一个 N 节点! 这是递归原理.

rbtree05

第 2 情况, S 红, 根据红黑树性质 P,SL,SR 一定黑. 策略: 旋转, 交换 P,S 颜色. 处理后关注的范围缩小, 下面的情况对应下面的框图, 算法从框图重新开始, 进入下一个情况:

rbtree06

第 2.1 情况, S,SL,SR 都黑. 策略: P->黑. S->红, 因为通过 N 的路径多了一个黑节点, 通过 S 的黑节点个数不变, 所以维持了性质 5. over. 将看到, sgi stl map 源代码中将第 2.1 和第 1 情况合并成一种情况, 下节展开.

rbtree07

第 2.2.1 情况, S,SR 黑, SL 红. 策略: 旋转, 变换 SL,S 颜色. 从而又进入下一种情况:

rbtree08
第 2.2.2 情况, S 黑, SR 红. 策略: 旋转, 交换 S,P 颜色, SR->黑色, 重新获得平衡.

rbtree09

上面情况标号 X.X.X 并不是说这些关系是嵌套的, 只是这样展开容易理解. 此时, 解释三个地方:

  1. 通过 N 的黑色节点数量多了一个
  2. 通过 SL 的黑色节点数量不变
  3. 通过 SR 的黑色节点数量不变

红黑树删除重新调整伪代码如下:

/ /  第 0.0  情况, N 为根节点. over
if  N.parent = =  NULL:
     return ;
 
/ /  第 0.1  情况, 删除的节点为红. over
if  color = =  RED:
     return ;
 
/ /  第 0.2  情况, 删除节点为黑, N 为红, 简单变换: N - >黑, 重新平衡. over
if  color = =  BLACK && N.color = =  RED:
     N.color =  BLACK;
 
/ /  第 1  种情况, N,P,S,SR,SL 都黑. 策略: S - >红. 通过 N,S 的黑色节点数量相同了, 但会比其他路径多一个, 解决的方法是在 P 上从情况 0  开始继续调整.
if  N,P,S,SR,SL.color = =  BLACK:
     S.color =  RED;
 
     / /  调整节点关系
     N =  P
     N.parent =  P.parent
     S =  P.paernt.another_child
     SL =  S.left_child
     SR =  S.right_child
     continue ;
 
/ /  第 2  情况, S 红, 根据红黑树性质 P,SR,SL 一定黑. 旋转, 交换 P,S 颜色. 此时关注的范围缩小, 下面的情况对应下面的框图, 算法从框图重新开始.
if  S.color = =  RED:
     rotate(P);
     swap(P.color,S.color);
 
     / /  调整节点关系
     S =  P.another_child
     SL =  S.left_child
     SR =  S.right_child
 
/ /  第 2.1  情况, S,SL,SR 都黑. 策略: P - >黑. S - >红, 因为通过 N 的路径多了一个黑节点, 通过 S 的黑节点个数不变, 所以维持了性质 5.  over. 将看到, sgi stl map  源代码中将第 2.1  和第 1  情况合并成一种情况, 下节展开.
if  S,SL,SR.color = =  BLACK:
     P.color =  BLACK;
     S.color =  RED;
     return
 
/ /  第 2.2 . 1  情况, S,SR 黑, SL 红. 策略: 旋转, 变换 SL,S 颜色. 从而又进入下一种情况:
if   S,SR.color = =  BLACK && SL.color = =  RED:
     rotate(P);
     swap(S.color,SL.color);
 
     / /  调整节点关系
     S =  SL
     SL =  S.left_child
     SR =  S.right_child
 
/ /  第 2.2 . 2  情况, S 黑, SR 红. 策略: 旋转, 交换 S,P 颜色.
if  S.color = =  BLACK && SR.color = =  RED:
     rotate(P);
     swap(P.color,S.color);
     return ;

总结

所以, 插入的情况只有三种, 删除的情况只有两种. 上面的分析, 做镜像处理, 就能得到插入删除的全部算法, 脑补吧. 从上面的分析来看, 红黑树具有以下特性: 插入删除操作都是 0(lnN), 且最多旋转三次.

下节中会重点展开 sgi stl map 的源代码.

参考文档: wikipedia

捣乱 2013-9-25

http://daoluan.net

更多请访问：http://daoluan.net
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

rbtree

红黑树并没有我们想象的那么难(上) 的相关文章

  • Windows 仍在设置此设备的类配置。 (代码 56)

    家里电脑有线网卡出现 Windows 仍在设置此设备的类配置 代码 56 解决方法 键盘按win r 弹出运行窗口 输入 redegit 进入注册表 删除HKEY CLASSES ROOT CLSID 3d09c1ca 2bcc 40b7

  • JavaScript的OO思想(一)

    类class是Object Oriented面向对象的语言有一个标志 通过类我们可以创建任意多个具有相同属性和方法的对象 JavaScript中没有类的概念 但它也是面向对象的 只是实现方法会有所不同 创建单个对象有两种基本方法 1 使用O

  • 从平面设计转行软件测试，喜提11K+13薪，回头看看我很幸运

    如何能够成为一个优秀的人 答 一以贯之的努力 不得懈怠的人生 每天的微小积累会决定最终结果 对待未来 人生与知识的敬意 永远值得我们学习 前言 我是2020年数字媒体技术专业毕业的 转行软件测试之前做的是平面设计 毕业的时候 我并不知道有软

  • transformers库的使用【一】——pipeline的简单使用

    transformers库的使用 使用pipeline API来快速使用一些预训练模型 使用预训练模型最简单的方法就是使用pipeline transformers提供了一些任务 1 情感分析 Sentment analysis 分析文本是

  • upload-labs

    在打本靶场之前 首先写一个一句话木马 关闭计算机的安全防护 不然计算机会杀掉 配合蚁剑可进行进一步操作 注 为避免部分题目可能无法实现 这里推荐使用phpstudy2016进行操作 目录 Pass 01 Pass 02 Pass 03 Pa

  • ethereumjs/ethereumjs-util

    ethereumjs ethereumjs util Most of the string manipulation methods are provided by ethjs util 更多的字符串处理方法可以看ethjs util ad

  • 几个常用的图片处理和图像识别API

    鸟类识别 http www inspirvision cn www product 支持鸟类品种鉴别 不同种类鸟类检测 鸟类数量统计 提供API Camera360 https github com pinguo PGSkinPrettif

  • [ kubernetes ] 基础名词解释

    Service RC RS和Deployment只是保证了支撑服务的微服务Pod的数量 但是没有解决如何访问这些服务的问题 一个Pod只是一个运行服务的实例 随时可能在一个节点上停止 在另一个节点以一个新的IP启动一个新的Pod 因此不能以

  • 跨域性的常识性推理

    跨域性的常识性推理是指在不同领域或知识领域之间进行推理和迁移的能力 它涉及将已有的知识和经验应用于新的情境或领域 以生成新的推理和理解 以下是关于跨域性常识性推理的一些常见观点 基础知识迁移 跨域性常识性推理可以帮助我们将基础知识从一个领域

  • 深度学习的发展方向： 深度强化学习！

    点击上方 小白学视觉 选择加 星标 或 置顶 重磅干货 第一时间送达 作者 莫凡 马晶敏 上海交通大学 转载自 Datawhale 深度学习不够智能 强化学习又太抽象 深度强化学习是两套理论体系乘风破浪以后的成团产物 其骨架来自强化学习 而

  • 整理了适合新手的20个Python练手小程序

    100个Python练手小程序 学习python的很好的资料 覆盖了python中的每一部分 可以边学习边练习 更容易掌握python 本文附带基础视频教程 私信回复 基础 就可以获取的 程序1 题目 有1 2 3 4个数字 能组成多少个互

  • 通过poi+java实现Excel表格的列宽度自适应

    新建sheet同时往sheet加入数据后 进行列宽设置 代码如下 固定首行 下拉时实现首行固定不动 sheet createFreezePane 0 1 0 1 列宽自适应 outputList get 0 size 为首行的列数 根据首行

  • web容器与servlet容器的区别

    servlet容器 负责管理servlet生命周期 web容器 负责管理和部署web应用 其本身可能具备servlet容器组件 如果没有 一般能将第三方servlet容器作为组件整合进web容器 1 web容器好比电视机 servlet容器

  • Hibernate（二）——一对多查询

    1 前言 本章节我们讨论Hibernate一对多查询的处理 在上一章节中 Hibernate 一 入门 我们探讨了Hibernate执行最基本的增删改查操作 现在我们将情况复杂化 加入我们在查询用户信息的时候需要同时查询其登录日志 这样就涉

  • 七、MySql-锁与事物

    MySql 锁与事物 锁 锁的简介 为什么需要锁 锁的概念 MySQL 中的锁 表锁与行锁的使用场景 MyISAM 锁 共享读锁 独占写锁 总结 InnoDB 锁 语法 注意 锁的等待问题 事务 什么存储引擎支持事务 事务特性 原子性 at

  • PyQt5接入高德地图搜索API出现Request Failed提示

    PyQt5接入高德地图搜索API出现Request Failed提示 Dcan1994的博客 CSDN博客 pyqt5 加载高德地图 PyQt5接入高德地图搜索功能API Windows版本 10 Python版本 3 6 5 高德地图AP

  • VC怎样调用COM控件的接口函数

    COM库函数 利用COM库函数使用代码组件的方法是本文介绍的三种方法中实现起来最麻烦和困难的方法 它要求开发人员必须具有对COM原理的深入理解 该方法实现步骤如下 1 首先添加COM初始和终止代码 在应用程序类的初始化实例函数InitIns

  • 跨时钟域信号传输（一）——控制信号篇

    1 跨时钟域与亚稳态 跨时钟域通俗地讲 就是模块之间有数据交互 但是模块用的不是同一个时钟进行驱动 如下图所示 左边的模块1由clk1驱动 属于clk1的时钟域 右边的模块2由clk2驱动 属于clk2的时钟域 当clk1比clk2的频率高

随机推荐

  • 线性代数 --- 什么是高斯消元法，什么又是高斯-若尔当消元法？

    高斯 若尔当消元法 写在最前面 我这个人比较喜欢炫耀 尤其发现别人在我面前炫耀的时候 我就会试图用我所学的知识盖过他的锋芒 所以呢 当初在Gilbert string老爷爷的课程里面第一次听到高斯若尔当这个词汇的时候 整个人就炸了 为什么我

  • 【计算机视觉

    文章目录 一 检测相关 11篇 1 1 Benchmarking Anomaly Detection System on various Jetson Edge Devices 1 2 High Performance Fine Defec

  • 双buffer防止 map读写并发

    package main import fmt strconv sync var s 2 map string string current 0 wg sync WaitGroup func w s1 string tmpIndex cur

  • c语言程序书写遵循的规则,C程序书写时应遵循的规则

    在C语言的应用领域 如通讯领域和嵌入式系统领域 一个的软件项目通常包含很多复杂的功能 实现这个项目不是一个程序员单枪匹马可以胜任的 往往需要一个团队的有效合作 另外 在一个以C代码为主的完整的项目中 经常也需要加入一些其他语言的代码 例如

  • 【Jenkins】Jenkins : Mac中Jenkins的停止和启动

    1 美图 2 命令 启动 重启 sudo launchctl load Library LaunchDaemons org jenkins ci plist 停止 sudo launchctl unload Library LaunchDa

  • 【2023】java打印PDF（不需要调用浏览器直接静默打印）

    java打印PDF 不需要调用浏览器直接静默打印 一 简 需求 实现步骤 二 代码实现 0 打印模板 1 服务器部分 端口 8090 1 1 maven依赖 1 2 实体 1 2 1 接口返回类 1 2 2 标签纸页面参数类 1 2 3 P

  • C++ Primer阅读笔记--语句的使用

    空语句 最简单的语句是空语句 其只含有一个单独的分号 switch语句 case 关键字和它对应的值一起被称为 case 标签 case 标签必须是整型常量表达式 char ch getVal int iVal 42 switch ch c

  • java接口的多实现可能遇到的问题与解决方法

    目录 接口中的多实现 代码演示 作用 问题总结 1 多实现接口中多个接口的抽象方法名重复 2 多实现接口中默认方法名重复 3 多实现类中默认方法与抽象方法重名 原理 1 默认方法与接口方法重名 2 默认方法重名 3 抽象类方法重名 接口中的

  • 如何进行PHP中的算术运算和字符串操作？

    PHP中需要进行算术运算和字符串操作的时候 我们可以使用相应的运算符和函数 不过 从新手的角度来说 可能会感到一些困扰 不用紧张 我来给你讲解一下 首先 让我们来谈谈算术运算 在PHP中 可以使用 运算符来进行加法运算 使用 运算符来进行减

  • 以太网PHY芯片MDIO寄存器读写-verilog

    MDIO实现还是比较简单的 应用xilinx FPGA内的VIO核就可以直接读写查看 如果板子有串口 做个简单的处理就可以直接通过电脑读写 时序如下图所示 将下面时序实现就可以实现读写 在实际应用时基本不需要配置 有特殊需求可以做一些应用

  • STM32——TIM输入捕获

    文章目录 一 TIM输入捕获 输入捕获简介 频率测量 二 通用定时器的输入捕获通道 通用定时器框图 通道的输出部分 三 主从触发模式 主模式 从模式 四 输入捕获基本结构 五 PWMI基本结构 六 输入捕获模式测频率 电路设计 关键代码 七

  • 微信二次分享不显示摘要和图片的解决方法

    微信二次分享不显示摘要和图片的解决方法 解决不显示摘要和图片的问题 需要调用微信公众号的js sdk的api 需要前端和后台的配合 后台需要返回 appid 公众号的appid timestamp 生成签名的时间戳 nonceStr 签名的

  • 【狂神Java学习笔记】Java基础

    狂神Java学习笔记 Java基础 参考网址 https www bilibili com video BV12J41137hu 一 注释 单行注释 多行注释 文档注释 用于生产说明文档 二 标识符和关键字 1 标识符概念 在java程序中

  • 只有某个网站无法访问的问题

    某个网站登录不上的问题 楼主遇到了只有百度登录不上 而其他网站及软件都能正常使用的问题 经过多次尝试终于解决 有以下几种解决方案 修改DNS地址 可能是由于DNS设置不正确的问题导致 可以打开网络和internet选项 更改适配器设置点击I

  • Linux学习之系统编程篇：读写锁（pthread_ rwlock _init / rdlock / wrlock / unlock / destroy）

    一 读写锁的认识 1 读写锁是1把锁 2 读写锁的类型 pthread rwlock t lock 又分 读锁 不让读内存 和 写锁 不让写内存 3 读写锁的特性 1 读共享 例如 线程 A 加读锁成功 有来个 3 个线程 作读操作 也可加

  • EOS开发者资源的大清单

    EOS开发者资源的大清单 自主网推出仅3个多月后 EOS正迅速发展其用户和开发者社区 在撰写本文时 EOS已经达到了超过20 000 000个不可逆块 并且具有大约3996个每秒交易 TPS 的一致吞吐量 更令人印象深刻的是不断增长的活跃用

  • 远程访问VM虚拟机方式记录

    网络环境 因个人办公网络相关限制 所使用的虚拟机网络环境为NAT模式 操作步骤 1 获取物理机的IP地址 2 获取虚拟机IP地址 确保要连接的虚拟机开启了相关的远程服务 3 VMware相关设置 先使用点击更改设置获取NAT设置的操作权限

  • TiDB学习

    TiDB 简介 SQL 基本操作 分类 查看 创建和删除数据库 创建 查看和删除表 创建 查看和删除索引 记录的增删改 记录的查询 创建 授权和删除用户 部署集群 数据迁移 运维操作 监控和告警 故障诊断 性能调优 教程 生态工具 参考指南

  • 打开Unity项目，加载进度条一直显示busy不消失

    打开Unity项目 加载进度条一直显示busy不消失 解决办法 我的项目路径存在中文 改成全英文路径再打开一下就好了

  • 红黑树并没有我们想象的那么难(上)

    lt 红黑树并没有我们想象的那么难 gt 上 下两篇已经完成 希望能帮助到大家 红黑树并没有我们想象的那么难 上 红黑树并没有我们想象的那么难 下 红黑树并没有想象的那么难 初学者觉得晦涩难读可能是因为情况太多 红黑树的情况可以通过归结 通

热门标签