程序员经验分享-hwhale

红黑树原理

2023-05-16

文章目录

    • 参考链接
    • 红黑树简介
    • RB Tree的五条基本性质
    • RB Tree的基本操作
    • 增
        • 情景1：红黑树为空树
        • 情景2：插入结点的Key已存在
        • 情景3：插入结点的父结点为黑结点
        • 情景4：插入结点的父结点为红结点
            • 情景4.1：叔叔结点存在并且为红结点
            • 情景4.2：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的左子结点
            • 情景4.3：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的右子结点
    • 删
        • 情景1：替换结点是红色结点
        • 情景2：替换结点是黑结点
            • 情景2.1：替换结点是其父结点的左子结点
            • 删除情景2.2：替换结点是其父结点的右子结点
        • 寻找前后继
    • 改
    • 查

参考链接

看了这么多篇红黑树文章，你理解了嘛？
红黑树原理和算法介绍

红黑树简介

  • 红黑树是一种自平衡二叉查找树，是计算机科学领域中的一种数据结构，典型的用途是实现关联数组，存储有序的数据。
  • 它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的。它可以在O(logn)时间内做查找，插入和删除，
  • 红黑树和平衡二叉树(AVL树)都是二叉查找树的变体，但红黑树的统计性能要好于AVL树。因为，AVL树是严格维持平衡的，红黑树是黑平衡的。维持平衡需要额外的操作，这就加大了数据结构的时间复杂度，所以红黑树可以看作是二叉搜索树和AVL树的一个折中，维持平衡的同时也不需要花太多时间维护数据结构的性质。

RB Tree的五条基本性质

（1）每个节点只有两种颜色：红色和黑色。

（2）根节点是黑色的。

（3）每个叶子节点（NIL）都是黑色的空节点。

（4）从根节点到叶子节点，不会出现两个连续的红色节点。

（5）从任何一个节点出发，到叶子节点，这条路径上都有相同数目的黑色节点。

RB Tree的基本操作

增

时间复杂度：O(logn)
旋转量级：O(1) 最多两次

情景1：红黑树为空树

把插入结点作为根结点，并把结点设置为黑色。

情景2：插入结点的Key已存在

1）把插入结点设为当前结点的颜色。
2）更新当前结点的值为插入结点的值。

情景3：插入结点的父结点为黑结点

直接插入。

情景4：插入结点的父结点为红结点

情景4.1：叔叔结点存在并且为红结点

在这里插入图片描述
1）将P和S设置为黑色（当前插入结点I）
2）将PP设置为红色
3）把PP设置为当前插入结点，继续上溯。
在这里插入图片描述

情景4.2：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的左子结点

  • 情景4.2.1：插入结点是其父结点的左子结点
    在这里插入图片描述

  • 情景4.2.2：插入结点是其父结点的右子结点
    在这里插入图片描述

情景4.3：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的右子结点
  • 情景4.3.1：插入结点是其父结点的右子结点
    在这里插入图片描述
  • 情景4.3.2：插入结点是其父结点的右子结点

在这里插入图片描述

删

时间复杂度：O(logn)
旋转量级：O(1) 最多三次

二叉树删除结点找替代结点有3种情情景：

  • 情景1：若删除结点无子结点，直接删除。
  • 情景2：若删除结点只有一个子结点，用子结点替换删除结点。
  • 情景3：若删除结点有两个子结点，用后继结点（大于删除结点的最小结点）替换删除结点。
  • 基于此，上面所说的3种二叉树的删除情景可以相互转换并且最终都是转换为情景1！！
  • 情景2：删除结点用其唯一的子结点替换，子结点替换为删除结点后，可以认为删除的是子结点，若子结点又有两个子结点，那么相当于转换为情景3，一直自顶向下转换，总是能转换为情景1。（根据红黑树的性质来说，只存在一个子结点的结点肯定在树末了）
  • 情景3：删除结点用后继结点（后继结点肯定不存在左结点），如果后继结点有右子结点，那么相当于转换为情景2，否则转为为情景1。
    在这里插入图片描述

红黑树删除后自平衡的处理可以总结为：

  • 自己能搞定的自消化（情景1）
  • 自己不能搞定的叫兄弟帮忙（除了情景1、情景2.1.2.3和情景2.2.2.3）
  • 兄弟都帮忙不了的，通过父母，找远方亲戚（情景2.1.2.3和情景2.2.2.3）
    在这里插入图片描述

情景1：替换结点是红色结点

颜色变为删除结点的颜色（替换结点Q，删除结点P）
在这里插入图片描述

情景2：替换结点是黑结点

情景2.1：替换结点是其父结点的左子结点
  • 情景2.1.1：替换结点的兄弟结点是红结点
    在这里插入图片描述
  • 情景2.1.2：替换结点的兄弟结点是黑结点

    • 情景2.1.2.1：替换结点的兄弟结点的右子结点是红结点，左子结点任意颜色
      即将删除的左子树的一个黑色结点，显然左子树的黑色结点少1了，然而右子树又有红色结点，那么我们直接向右子树“借”个红结点来补充黑结点就好啦，此时肯定需要用旋转处理了。
      在这里插入图片描述
      平衡后的图怎么不满足红黑树的性质？前文提醒过，R是即将替换的，它还参与树的自平衡，平衡后再替换到删除结点的位置，所以R最终可以看作是删除的。另外图15是考虑到第一次替换和自底向上处理的情况，如果只考虑第一次替换的情况，根据红黑树性质，SL肯定是红色或为Nil，所以最终结果树是平衡的。如果是自底向上处理的情况，同样，每棵子树都保持平衡状态，最终整棵树肯定是平衡的。后续的情景同理，不做过多说明了。

    • 情景2.1.2.2：替换结点的兄弟结点的右子结点为黑结点，左子结点为红结点
      兄弟结点所在的子树有红结点，我们总是可以向兄弟子树借个红结点过来，显然该情景可以转换为情景2.1.2.1。如图17所示。
      在这里插入图片描述

    • 删除情景2.1.2.3：替换结点的兄弟结点的子结点都为黑结点
      好了，此次兄弟子树都没红结点“借”了，兄弟帮忙不了，找父母呗，这种情景我们把兄弟结点设为红色，再把父结点当作替代结点，自底向上处理，去找父结点的兄弟结点去“借”。但为什么需要把兄弟结点设为红色呢？显然是为了在P所在的子树中保证平衡（R即将删除，少了一个黑色结点，子树也需要少一个），后续的平衡工作交给父辈们考虑了，还是那句，当每棵子树都保持平衡时，最终整棵总是平衡的。
      在这里插入图片描述

删除情景2.2：替换结点是其父结点的右子结点
  • 情景2.1.1：替换结点的兄弟结点是红结点
    在这里插入图片描述
  • 情景2.1.2：替换结点的兄弟结点是黑结点
    • 删除情景2.2.2.1：替换结点的兄弟结点的左子结点是红结点，右子结点任意颜色
      在这里插入图片描述
    • 删除情景2.2.2.2：替换结点的兄弟结点的左子结点为黑结点，右子结点为红结点

在这里插入图片描述

  • 删除情景2.2.2.3：替换结点的兄弟结点的子结点都为黑结点
    在这里插入图片描述

寻找前后继

在这里插入图片描述

改

时间复杂度：O(logn)
不能改key值，只能改value值。

查

时间复杂度：O(logn)
查操作与二叉查找树相同。

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

红黑树原理 的相关文章

  • 2020华为软挑总结

    文章目录 一 热身赛编程闯关 xff1a 评价标准 xff1a 问题分析 二 初赛问题描述评价标准 xff1a 问题分析思路一 xff1a 思路二 xff1a 思路三 xff1a 针对思路三的提速 xff1a 最终结果 xff1a 三 co

  • Linux命令总结之目录命令

    文章目录 Linux 目录命令1 96 ls 96 命令2 96 cd 96 命令3 96 pwd 96 命令4 96 mkdir 96 命令5 96 rm 96 命令6 96 mv 96 命令7 96 cp 96 命令8 96 cat 9

  • Markdown 公式指导手册

    Markdown 公式指导手册

  • Linux学习

    文章目录 一 基础入门二 Linux 命令总结一 Linux 目录命令 https blog csdn net weixin 42715287 article details 105825021 二 Linux 文件管理命令 https e

  • Linux命令总结之文件管理命令

    文章目录 二 Linux 文件管理命令1 96 which 96 命令到底什么是命令 xff1f 2 96 whereis 96 命令3 96 locate 96 命令4 96 find 96 命令5 96 xargs 96 命令 二 Li

  • Linux命令总结之文本编辑命令

    文章目录 Linux 文本编辑命令1 96 wc 96 命令2 96 grep 96 命令3 96 正则表达式 96 命令4 96 cut 96 命令5 96 paste 96 命令6 96 tr 96 命令7 96 sort 96 命令8

  • Linux命令总结之Linux 磁盘管理命令

    文章目录 Linux 磁盘管理命令1 96 df 96 命令2 96 du 96 命令3 96 time 96 命令 Linux 磁盘管理命令 1 df命令 linux 中 df 命令的功能是用来检查 linux 服务器的文件系统的磁盘空间

  • linux基础操作之一

    文章目录 1 基本概念及操作常用快捷键 xff1a 2 用户及文件权限管理1 Linux 用户管理1 查看用户 xff1a 2 创建账户 xff1a 3 用户组4 删除用户和用户组5 鲲鹏服务器安装 96 perf 96 6 阿里云服务器安

  • 重庆思庄Linux技术分享-linux中VDO的使用

    VDO xff08 Virtual Data Optimize虚拟数据优化 xff09 通过压缩或删除存储设备上的数据来优化存储空间 VDO层放置在现有块存储设备例如RAID设备或本地磁盘的顶部 这些块设备也可以是加密设备 存储层 xff0

  • 排序算法之快排

    1 快排 快速排序算法的关键在于先在数组中选一个数字 xff0c 接下来把数组中的数字分成两部分 span class token comment achieve quick sorting span span class token ma

  • 排序算法之归并排序

    充分利用了把大问题转化成一个个小的子问题的思想 xff08 由迭代或递归来实现 xff09 span class token comment achieve merge sorting span span class token macro

  • 排序算法之堆排序(附源码)

    1 将顺序存储的数据看成是一颗完全二叉树 2 对于大顶堆 xff0c 确保每棵子树的根节点都是整个子树中的最大值 xff1b 这就保证了根节点是所有数据中的最大值 xff0c 但不保证所有数据有序 span class token comm

  • LED灯源控制

    1 LED五种调光控制方式详解 LED的发光原理同传统照明不同 xff0c 是靠P N结发光 xff0c 同功率的LED光源 xff0c 因其采用的芯片不同 xff0c 电流电压参数则不同 xff0c 故其内部布线结构和电路分布也不同 xf

  • LED驱动电路的分析

    文章目录 一 方案一 1 电路工作原理 2 组件选择 3 个人分析 二 方案二 在方案一的基础上改进 1 电路工作原理 2 个人分析 三 方案三 在方案一的基础上改进 1 电路工作原理 2 个人分析 参考连接 常见驱动电路的分析 一 方案一

  • linux基础操作之二

    文章目录 6 文件解压与打包1 概念讲解2 实战1 zip 压缩打包程序2 使用 unzip 命令解压缩 zip 文件3 tar 打包工具4 总结 7 文件系统操作与磁盘管理1 查看磁盘和目录的容量2 dd 命令简介3 使用 dd 命令创建

  • mmap的使用

    参考资料 mmap 函数 xff1a 原理与使用 含代码 mmap函数使用与实例详解 Linux系统编程 xff1a mmap使用技巧 mmap和普通文件读写的区别和比较 amp mmap的注意点 认真分析mmap xff1a 是什么 为什

  • LED高效恒流驱动电源的设计指导书

    参考链接 LED高效恒流驱动电源的设计指导书 LED灯驱动电源设计 LED恒流驱动电路 精 LED恒流驱动电路 led灯驱动电源电路图 led灯的驱动原理电路图方案详解 KIA MOS管 一 LED驱动电源原理 1 由于LED的光特性通常都

  • 恒流源驱动电路 随笔一

    方案一 参考论文 LED光源驱动电路研究 华科 硕士 08 06 采用恒流源控制的原因 1 LED的PN结的温度系数为负 温度升高时LED的势垒电势降低 由于这个特点 所以LED不能直接用电压源供电 必须采用限流措施 否则LED随着工作时温

  • 恒流源驱动电路 随笔二

    参考论文 LED的驱动电路研究 大理 硕士 07 06 三个简单方案 电荷泵驱动的典型电路 CAT3604是一个工作在1x 1 5x分数模式下的电荷泵 可调节每只LED白光管脚 xff08 共4只LED管脚 xff09 的电流 使背光的亮度

  • gcc编译c文件常用命令参数解释

    gcc编译c文件 gcc是常用来编译c语言程序的编译器 xff0c 了解它编译c语言的命令参数 xff0c 对c c 43 43 语言的学习是有一定好处的 gcc编译文件一步到位的命令格式 gcc main c o main exe 设置了

随机推荐

  • 恒流源驱动电路 随笔三

    参考论文一 LED蓝绿光黄疸光疗系统的研究与设计 天工 硕士 15 12 AMC7150是一种仅需 xff15 个外部零件的高功率LED驱动IC AMC7150内建P xff37 xff2d 和功率晶体管 xff0c 工作频率可达200kH

  • 光源系统厂商、结构

    参考论文 基于PWM的LED机器视觉光源技术的研究 哈工大 硕士 span class token number 2009 span fpga 前言 机器视觉系统包括 xff1a 照明 镜头 相机 图像采集卡 视觉处理器 led光源分为两大

  • LED驱动IC厂家

    厂家芯片类别 世微半导体 英飞凌Infineon 壹芯半导体科技 xff08 深圳 xff09 有限公司 欧司朗OSRAM xff1a 汽车照明 深圳天微电子有限公司 中铭电子 深圳市华芯光电有限公司 宁波欧特电子科技有限公司 芯片介绍 l

  • 2D/3D模板匹配

    2D 对象 正交视图 物体的组成部分之间的角度和距离可以改变 xff0c 不需要缩放 需要缩放 存在遮挡 杂乱或颜色 物体的特征是具有特定的纹理 xff0c 而不是清晰可见的轮廓 图像高度散焦 对象变化显著 期望物体轮廓的局部变形 xff0

  • linux基础操作之三

    文章目录 10 命令执行顺序控制与管道命令执行顺序的控制1 顺序执行多条命令2 有选择的执行命令 管道3 1 试用3 2 cut 命令 xff0c 打印每一行的某一字段3 3 grep 命令 xff0c 在文本中或 stdin 中查找匹配字

  • 2020华为软挑总结——baseline

    span class token macro property span class token directive keyword include span span class token string lt bits stdc 43

  • 2020华为软挑总结——复赛方案一code

    span class token macro property span class token directive keyword include span span class token string lt iostream gt s

  • 2020华为软挑总结——方案二code

    span class token macro property span class token directive keyword include span span class token string lt iostream gt s

  • 机器视觉照明技术与装置实验研究（论文纪要）

    参考文献 机器视觉照明技术与装置实验研究 中原 硕士 2016 有用 摘要 图片质量很大程度上是由目标周围的照明环境和目标物体表面材质 物体摆放位置所决定的 1 首先 xff0c 对照明系统主要技术进行了研究 研究内容包括光源的参数与选择

  • Affine Transformations(仿射变换)

    英文版原文链接 先修教程 xff1a Remapping 重映射 下一教程 xff1a Histogram Equalization 直方图均衡化 文章目录 结果目标原理什么是仿射变换 我们如何得到一个仿射变换 代码这个程序是做什么的 代码

  • Linux 网桥功能使用

    Linux 网桥功能使用 网桥是在数据链路层 xff0c 将两个LAN连接起来 xff0c 根据MAC地质来转发帧 xff0c 可以看作是低层的路由器 安装网桥配置工具 检测系统中是否有有bridge 工具 xff1a rpm qa gre

  • Remapping(重映射)

    英文版原文链接 上一教程 xff1a Hough Circle Transform Hough圆变换 下一教程 xff1a Affine Transformations 仿射变换 文章目录 结果目标原理什么是重映射 xff1f 代码这个程序

  • 机器视觉(Robot Vision)——1

    参考书籍 Robot Vision MIT机器视觉课程指定教材 机器视觉探究两个基本问题 xff1a 成像过程的基本原理是什么 xff1f 如何探索对成像过程 求逆 的基本知识和方法 所谓 求逆 xff1a 具体来说 xff0c 就是从一张

  • 机器视觉实验架套装选型

    文章目录 0 机器视觉集成商0 1 上海热驰自动化1 海康威视2 集云誉创3 深圳新次元4 机器视觉光源控制器厂5 恒视科技6 小厂商6 机器视觉检测配套商 0 机器视觉集成商 购买链接 基础款 xff1a 580 970 加强款 xff1

  • meiqua / shape_based_matching（issue记录）

    文章目录 readmeissue 1 如何加快responsemap的创建 issue 2 请问一下是否抗缩放呢 xff1f issue 3 匹配准确定位精度还能再提高吗 xff1f branch有些多了 xff0c 能否写个文档介绍一下各

  • 机器视觉(Robot Vision)——2

    参考书籍 Robot Vision MIT机器视觉课程指定教材 机器视觉探究两个基本问题 xff1a 成像过程的基本原理是什么 xff1f 如何探索对成像过程 求逆 的基本知识和方法 所谓 求逆 xff1a 具体来说 xff0c 就是从一张

  • git同步远程仓库的所有分支

    方法一 span class token comment 找一个干净目录 xff0c 假设是clone span span class token function cd span clone span class token commen

  • linux基础操作之四

    文章目录 14 Linux下软件安装2 简介2 1 先体验一下2 2 apt 包管理工具介绍2 3 apt get2 4 安装软件包2 5 软件升级2 6 卸载软件2 7 软件搜索 3 使用 dpkg3 1 dpkg 介绍3 2 使用 dp

  • FPGA开发板选型

    1 Micro Phase微相官方旗舰店 淘宝链接 1 小熊猫嵌入式电子 淘宝链接 2 正点原子 淘宝链接 3 黑金ALINX 淘宝链接

  • 红黑树原理

    文章目录 参考链接红黑树简介RB Tree的五条基本性质RB Tree的基本操作增情景1 xff1a 红黑树为空树情景2 xff1a 插入结点的Key已存在情景3 xff1a 插入结点的父结点为黑结点情景4 xff1a 插入结点的父结点为红

热门标签