Red Black Tree 的一点感想

本贴最后更新于 2647 天前,其中的信息可能已经天翻地覆

红黑树的基本性质

  1. 每个节点或是红色的,或是黑色的。
     2) 根节点是黑色的。
     3) 每个叶节点(NIL)是黑色的。
     4) 如果一个节点是红色的,则它的两个子节点都是黑色的。
     5) 对每个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点。

红黑树插入时,如果插入红色节点则
(由于插入黑色节点一定会导致性质五被破坏,所以考虑插入为红色节点的情况)

  1. 性质一不会破坏
  2. 性质二可能破坏
  3. 性质三不会被破坏
  4. 性质四可能被破坏
  5. 性质五不会被破坏

当插入导致性质被破坏时需要调整:
由上面所述,只有性质二和四可能被破坏,而性质二只有在插入之前为空树时可能被破坏。所以我们需要关注性质四,即插入导致两个红色节点连在了一起。下面分情况表述:

  • **1.插入的节点为根节点:**若插入前无任何节点,则插入后的节点为根节点直接设置为黑色即可。
  • **2.插入的节点的父节点为黑色节点:**无需做任何改变因为不会影响红黑树性质
  • 3.插入的节点的父节点为红色且 uncle 节点也是红色: 此时将导致两个红色节点连接到了一起,此时我们考虑改变两个红色节点之中的一个,然而改变插入节点的颜色显然是无意义的,(如果改变相当于插入黑色节点),所以我们将插入节点的父节点设置为黑色,然而这样同时会导致性质五的违背,所以我们将其 uncle 节点也设置为黑色,并将 parent 的 parent 节点设置为红色,此时调整完成。插入节点为 M,如下图:
    3d65bdf1eef44c8d9856bcc9dba0f572-image.png
    (图片来源于网络)
  • **4.插入节点的父节点为红色且 uncle 节点为黑色(T.nil 也为黑色),插入节点为右节点:**以插入节点的的父节点作为支点左旋变成情况 5,再调整

    (图片来源于网络)
  • **5.插入节点父节点为红色,uncle 节点为黑色(T.nil 为黑色),插入节点为的左子节点:**将 parent 节点设置为黑色,parent 的 parent 节点设置为红色,并以 parent 节点为支点右旋。

    (图片来源于网络)
    删除节点:
    当我们删除一个节点时,z 指向删除节点,y 指向替换删除删除节点的节点,x 指向 y 的右子树,首先按照二叉搜索树的的删除方式进行删除,并在其中加入部分代码记录 Y 的踪迹和 y 的初始颜色,还有 x 的踪迹(见《算法导论》第三版 183 页)。
    删除节点的过程:当 z 只有一个子树时,y 指向该子树,并直接将子树 y 替换 z,当 z 有两个子树时选择右子树的最左侧节点作为 y,并用 y 替换 z,并用 x 替换 y,并进行 red-black tree 调整。
    所以实际过程相当于删除 Y

当 y 是红色时,删除后不会影响红黑树的基本性质,可直接删除

当如果 y 是黑色,会出现如下三种情况:
1.如果原先的 y 是根节点,y 的红色 x 替换 y 将导致违反性质 2
2.如果替换后 x 和 x 的父节点都为红色则违反性质 4
3.y 在树中移动将导致包含 y 的任何简单路径和高度减一。

所以我们需要对 y 为黑色节点时被 x 替换后的树进行调整。
由于懒得画图使用网络图片~~~~这时 N 上文所述的 x
1.如果 N 的兄弟节点为红色时
将 B 设置为黑色,N 的父节点 P 设置为红色,然后以 P 为中心左旋转,则转换情况 2

(图片来源于网络)

2.如果 N 的兄弟节点为黑色,并且两个子节点都为黑色(包括 T.nil):
将 N 的兄弟节点 B 变红,然后用 N 的父节点 P 作为新的 N,进行递归操作。因为 N 是 P 的左子树,P 的左子树路径中,删除 N 后,会缺少一个黑色节点,因此递归的将右树上的路径也减少一个黑色节点,知道 N 的颜色为红色。最后把当前的 N 节点置为黑色。最后产生的结果就是将右侧的黑色节点上移,这样右子树和左子树都没有减少黑色节点。

(图片来源于网络)
3.如果 N 的兄弟节点 B 是黑色的他的左孩子为红色,右孩子为黑色
将 B 变红,b1 变黑,然后以 B 为中心右旋,则转换为情况 4

(图片来源于网络)
4.如果 N 的兄弟节点 B 是黑色他的右孩子为红色,左孩子可红可黑
将 B 的颜色设置为与 P 的颜色一致,然后 P 和 b2 设置为黑色,以 P 为中心左旋。

(图片来源于网络)
至此正文结束
分割线------------------------------------------------------------------------
花了我整整一下午加一晚上时间才看懂了此算法,并立刻跟新博客,也为以后如果忘记也是一个不错的复习资料,不过很开心今晚的迎新晚会很棒棒~~~~~~,不早了再不睡要猝死啦。。。。。

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • 深度学习

    深度学习(Deep Learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。

    54 引用 • 40 回帖
  • 强迫症

    强迫症(OCD)属于焦虑障碍的一种类型,是一组以强迫思维和强迫行为为主要临床表现的神经精神疾病,其特点为有意识的强迫和反强迫并存,一些毫无意义、甚至违背自己意愿的想法或冲动反反复复侵入患者的日常生活。

    15 引用 • 161 回帖 • 1 关注
  • Python

    Python 是一种面向对象、直译式电脑编程语言,具有近二十年的发展历史,成熟且稳定。它包含了一组完善而且容易理解的标准库,能够轻松完成很多常见的任务。它的语法简捷和清晰,尽量使用无异义的英语单词,与其它大多数程序设计语言使用大括号不一样,它使用缩进来定义语句块。

    549 引用 • 674 回帖
  • 游戏

    沉迷游戏伤身,强撸灰飞烟灭。

    179 引用 • 818 回帖 • 1 关注
  • JavaScript

    JavaScript 一种动态类型、弱类型、基于原型的直译式脚本语言,内置支持类型。它的解释器被称为 JavaScript 引擎,为浏览器的一部分,广泛用于客户端的脚本语言,最早是在 HTML 网页上使用,用来给 HTML 网页增加动态功能。

    729 引用 • 1278 回帖 • 1 关注
  • Ngui

    Ngui 是一个 GUI 的排版显示引擎和跨平台的 GUI 应用程序开发框架,基于
    Node.js / OpenGL。目标是在此基础上开发 GUI 应用程序可拥有开发 WEB 应用般简单与速度同时兼顾 Native 应用程序的性能与体验。

    7 引用 • 9 回帖 • 397 关注
  • Word
    13 引用 • 40 回帖
  • Sphinx

    Sphinx 是一个基于 SQL 的全文检索引擎,可以结合 MySQL、PostgreSQL 做全文搜索,它可以提供比数据库本身更专业的搜索功能,使得应用程序更容易实现专业化的全文检索。

    1 引用 • 213 关注
  • 笔记

    好记性不如烂笔头。

    311 引用 • 796 回帖
  • OAuth

    OAuth 协议为用户资源的授权提供了一个安全的、开放而又简易的标准。与以往的授权方式不同之处是 oAuth 的授权不会使第三方触及到用户的帐号信息(如用户名与密码),即第三方无需使用用户的用户名与密码就可以申请获得该用户资源的授权,因此 oAuth 是安全的。oAuth 是 Open Authorization 的简写。

    36 引用 • 103 回帖 • 27 关注
  • Tomcat

    Tomcat 最早是由 Sun Microsystems 开发的一个 Servlet 容器,在 1999 年被捐献给 ASF(Apache Software Foundation),隶属于 Jakarta 项目,现在已经独立为一个顶级项目。Tomcat 主要实现了 JavaEE 中的 Servlet、JSP 规范,同时也提供 HTTP 服务,是市场上非常流行的 Java Web 容器。

    162 引用 • 529 回帖 • 4 关注
  • Sublime

    Sublime Text 是一款可以用来写代码、写文章的文本编辑器。支持代码高亮、自动完成,还支持通过插件进行扩展。

    10 引用 • 5 回帖
  • webpack

    webpack 是一个用于前端开发的模块加载器和打包工具,它能把各种资源,例如 JS、CSS(less/sass)、图片等都作为模块来使用和处理。

    41 引用 • 130 回帖 • 251 关注
  • BND

    BND(Baidu Netdisk Downloader)是一款图形界面的百度网盘不限速下载器,支持 Windows、Linux 和 Mac,详细介绍请看这里

    107 引用 • 1281 回帖 • 30 关注
  • Ubuntu

    Ubuntu(友帮拓、优般图、乌班图)是一个以桌面应用为主的 Linux 操作系统,其名称来自非洲南部祖鲁语或豪萨语的“ubuntu”一词,意思是“人性”、“我的存在是因为大家的存在”,是非洲传统的一种价值观,类似华人社会的“仁爱”思想。Ubuntu 的目标在于为一般用户提供一个最新的、同时又相当稳定的主要由自由软件构建而成的操作系统。

    127 引用 • 169 回帖
  • NGINX

    NGINX 是一个高性能的 HTTP 和反向代理服务器,也是一个 IMAP/POP3/SMTP 代理服务器。 NGINX 是由 Igor Sysoev 为俄罗斯访问量第二的 Rambler.ru 站点开发的,第一个公开版本 0.1.0 发布于 2004 年 10 月 4 日。

    315 引用 • 547 回帖 • 4 关注
  • Solidity

    Solidity 是一种智能合约高级语言,运行在 [以太坊] 虚拟机(EVM)之上。它的语法接近于 JavaScript,是一种面向对象的语言。

    3 引用 • 18 回帖 • 429 关注
  • 持续集成

    持续集成(Continuous Integration)是一种软件开发实践,即团队开发成员经常集成他们的工作,通过每个成员每天至少集成一次,也就意味着每天可能会发生多次集成。每次集成都通过自动化的构建(包括编译,发布,自动化测试)来验证,从而尽早地发现集成错误。

    15 引用 • 7 回帖
  • 旅游

    希望你我能在旅途中找到人生的下一站。

    93 引用 • 901 回帖
  • Jenkins

    Jenkins 是一套开源的持续集成工具。它提供了非常丰富的插件,让构建、部署、自动化集成项目变得简单易用。

    54 引用 • 37 回帖
  • Postman

    Postman 是一款简单好用的 HTTP API 调试工具。

    4 引用 • 3 回帖 • 4 关注
  • FreeMarker

    FreeMarker 是一款好用且功能强大的 Java 模版引擎。

    23 引用 • 20 回帖 • 462 关注
  • Follow
    4 引用 • 12 回帖 • 8 关注
  • Spring

    Spring 是一个开源框架,是于 2003 年兴起的一个轻量级的 Java 开发框架,由 Rod Johnson 在其著作《Expert One-On-One J2EE Development and Design》中阐述的部分理念和原型衍生而来。它是为了解决企业应用开发的复杂性而创建的。框架的主要优势之一就是其分层架构,分层架构允许使用者选择使用哪一个组件,同时为 JavaEE 应用程序开发提供集成的框架。

    945 引用 • 1460 回帖 • 1 关注
  • Access
    1 引用 • 3 回帖 • 5 关注
  • 知乎

    知乎是网络问答社区,连接各行各业的用户。用户分享着彼此的知识、经验和见解,为中文互联网源源不断地提供多种多样的信息。

    10 引用 • 66 回帖
  • Latke

    Latke 是一款以 JSON 为主的 Java Web 框架。

    71 引用 • 535 回帖 • 816 关注