首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

红黑树

编程知识
2024年09月08日 15:08

概述

红黑树(Red-Black Tree,R-BTree)是一种自平衡的二叉查找树,在红黑树的每个节点都多出一个存储位表示节点的颜色,颜色只能是红(Red)或者黑(Black)。

红黑树的特性如下:

  • 每个节点或者是黑色的,或者是红色的
  • 根节点是黑色的
  • 每个叶子节点都是黑色的,这里的叶子节点指的是最底层的空节点,即图中值为 null 的节点,讨论时一般将其省略,值为 null 的根节点在红黑树中不看作叶子节点
  • 如果一个节点是红色的,则它的子节点必须是黑色的
  • 从任一个节点到叶子节点的所有路径下都包含相同数量的黑色节点

有了上面的几个性质作为限制,即可避免二叉查找树退化成单链表的情况。而有了性质 4 和性质 5,可保证任意节点到其每个叶子节点路径最长不会超过最短路径的 2 倍,因为当某条路径最短时,这条路径必然都由黑色节点构成。当某条路径长度最长时,这条路径必然由红色和黑色节点相间构成(性质 4)。而性质 5 又限定了任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点。因此,最长路径长度等于最短路径长度的 2 倍


红黑树的旋转

红黑树的左旋:以 a 节点为支点左旋,指将 a 节点的右子节点(b)设为 a 节点的父节点,则 a 节点变为 b 节点的左节点,b 节点原本的左子节点 d 则按照平衡二叉树的规则重新分配位置

红黑树的右旋也是同理


红黑树的添加

红黑树的添加分为三步:

  1. 将红黑树看作一颗二叉查找树,并以二叉查找树的规则插入新节点,此时新节点一定位于树的末端,即是叶子节点(不考虑值为 null 的黑色节点)
  2. 将插入的节点涂成红色(如果涂成是黑色,那么这个节点所在路径比其他路径多出一个黑色节点,调整起来比较麻烦;如果涂成红色,此时所有路径上的黑色节点数量不变,仅可能会出现两个连续的红色节点的情况,通过变色和旋转进行调整即可)
  3. 通过左旋、右旋或着色操作,使之重新成为一颗红黑树

根据被插入的节点的父节点的情况,可以将具体的插入分为三种情况来处理

第一种:如果被插入的节点是根节点,则直接把此节点涂成黑色

第二种:如果被插入的节点的父节点是黑色的,没有破坏二叉树的性质,不需要调整

第三种:如果被插入的节点的父节点是红色的,则被插入的节点一定存在非空祖父节点(黑色),即被插入的节点也一定存在叔叔节点,即使叔叔节点(当前节点的祖父节点的另一个子节点)为空,我们也视之为存在,空节点本身就是黑色节点。然后根据叔叔节点的颜色,进一步分为三种情况来处理:

  • 叔叔节点是红色的,则将父节点和叔叔节点设为黑色,祖父节点设为红色。需要注意的是祖父节点设为红色后,可能会和它的父节点形成连续的红色节点,此时需要将当前节点设为祖父节点,递归向上调整
  • 叔叔节点是黑色的,当前节点是父节点的右子节点,则将父节点设为当前节点,以当前节点为支点左旋,再根据其他情况调整
  • 叔叔节点是黑色的,当前节点是父节点的左子节点,则将父节点设为黑色,将祖父节点设为红色,以祖父节点为支点右旋

红黑树的删除

红黑树的删除分为两步:

  1. 将红黑树看作一颗二叉查找树,根据二叉查找树的删除规则删除节点
    1. 如果被删除的节点没有子节点,那么直接将该节点删除
    2. 如果被删除的节点只有一个子节点,那么直接删除该节点,并用该节点的唯一子节点替换该节点
    3. 如果被删除的节点有两个子节点,那么先找出该节点的替换节点,然后把替换节点的数据覆盖该节点的数据,之后删除替换节点
  2. 因为红黑树在删除节点后可能会违背红黑树的特性,所以需要通过旋转和重新着色来修正,使之重新成为一棵红黑树
    1. 如果当前节点的子节点是“红+黑”节点,则直接把当前节点设为黑色
    2. 如果当前节点的子节点是“黑+黑”节点,且当前节点是根节点,则什么都不做
    3. 如果当前节点的子节点是“黑+黑”节点,且当前节点不是根节点,则又可以分如下情况处理
      • 当前节点的兄弟节点是红色,则将当前节点的兄弟节点设置为黑色,将父节点设置为红色,对父节点进行左旋,重新设置当前节点的兄弟节点
      • 如果当前节点的子节点是“黑+黑”节点,且当前节点的兄弟节点是黑色,兄弟节点的两个子节点也都是黑色,则将当前节点的兄弟节点设置为红色,设置当前节点的父节点为新节点
      • 如果当前节点的子节点是“黑+黑”节点,且当前节点的兄弟节点是黑色,兄弟节点的左子节点是红色且右子节点是黑色,则将当前节点的左子节点设置为黑色,将兄弟节点设置为红色,对兄弟节点进行右旋,重新设置当前节点的兄弟节点
      • 如果当前节点的子节点是“黑+黑”节点,且当前节点的兄弟节点是黑色,兄弟节点的右子节点是红色且左子节点是任意颜色,则将当前节点的父节点的颜色赋值给兄弟节点,将父节点设置为黑色,将兄弟节点的右子节点设置为黑色,对父节点进行左旋,设置当前节点为根节点
From:https://www.cnblogs.com/Yee-Q/p/18401801
本文地址: http://www.shuzixingkong.net/article/1832
0评论
提交 加载更多评论
其他文章 关于求合法括号子序列个数
求合法括号子序列个数 题意 背景 合法括号串的定义如下: () 是合法括号串。 如果 A 是合法括号串,则 (A) 是合法括号串。 如果 A,B 是合法括号串,则 AB 是合法括号串。 子串与不同的子串的定义如下: 字符串 S 的子串是 S 中连续的任意个字符组成的字符串。S 的子串可用起始位置 \
万字长文带你窥探Spring中所有的扩展点
写在前面 Spring的核心思想就是容器,当容器refresh的时候,外部看上去风平浪静,其实内部则是一片惊涛骇浪,汪洋一片。Springboot更是封装了Spring,遵循约定大于配置,加上自动装配的机制。很多时候我们只要引用了一个依赖,几乎是零配置就能完成一个功能的装配。 由spring提供的、
万字长文带你窥探Spring中所有的扩展点 万字长文带你窥探Spring中所有的扩展点
Git Extensions:一个.NET开源的 Git 图形用户界面(GUI)工具
前言 今天大姚给大家分享一个.NET开源、免费的用于管理 Git 存储库的独立图形用户界面(GUI)工具,它还与 Windows 资源管理器和 Microsoft Visual Studio (2015/2017/2019/2022) 集成:Git Extensions。 Git新手指南:从基础到实
Git Extensions:一个.NET开源的 Git 图形用户界面(GUI)工具 Git Extensions:一个.NET开源的 Git 图形用户界面(GUI)工具 Git Extensions:一个.NET开源的 Git 图形用户界面(GUI)工具
红日靶机(一) 笔记
红日靶机(一)笔记 概述 域渗透靶机,可以练习对域渗透的一些知识,主要还是要熟悉 powershell 语法,powershell 往往比 cmd 的命令行更加强大,而很多渗透开源的脚本都是 powershell 的。例如 NiShang,PowerView 等等。这是域渗透的初学靶机。其中也遇到了
红日靶机(一) 笔记 红日靶机(一) 笔记 红日靶机(一) 笔记
实现人形角色的攀爬
在Unity实现角色攀爬 前言 开放世界类型的游戏近年也热门起来了,自由攀爬也成了这一类游戏的一大特色。攀爬给了玩家更多探索路径的选择,也让地图设计有了更多思路。这次,我们就来尝试在Unity中制作一个人形角色的攀爬。 注:攀爬是一个角色完整动作系统的一部分,本文暂且抛开其它动作,也不涉及动画,仅针
实现人形角色的攀爬 实现人形角色的攀爬 实现人形角色的攀爬
Pipeline流水线通过git拉取Jenkinsfile报错 error: RPC failed; result=22, HTTP code = 404
Pipeline流水线通过git拉取Jenkinsfile报错 error: RPC failed; result=22, HTTP code = 404 在学习共享库时使用通过git拉取jenkinsfile时,报错在排查gitlab服务状态,网络通讯,防火墙规则以及Jenkins凭据均可以正常使
Pipeline流水线通过git拉取Jenkinsfile报错 error: RPC failed; result=22, HTTP code = 404 Pipeline流水线通过git拉取Jenkinsfile报错 error: RPC failed; result=22, HTTP code = 404 Pipeline流水线通过git拉取Jenkinsfile报错 error: RPC failed; result=22, HTTP code = 404
题解:AT_arc116_b [ARC116B] Products of Min-Max
在题库里面乱翻,就翻到了。 因为在这道题里面子序列不需要考虑元素顺序,所以原序列无论是什么顺序都不会影响答案。 所以先把元素按照从大到小的顺序排列,然后考虑每个元素的贡献。 在当前序列中,对于元素 \(a_i\),不妨设其为最小值,并去寻找它能作为哪些序列的最小值。容易发现它作为最小值的时候只能和
编译和分发 Chez Scheme 应用程序
参考 Building and Distributing Applications. 假设源码由两个文件组成,A.ss 和 B.ss,其中 A.ss 依赖 B.ss。下面我们将其编译为可供分发的二进制文件。 将源码转为 object file 在 Chez Scheme 的 REPL 中(下同)输入