当前位置: 首页 > news >正文

高阶数据结构(2)-----红黑树(未完成)

一)红黑树的基本概念和基本性质:

1)红黑树就是一种高度平衡的二叉搜索树,但是在每一个节点上面都增加了一个存储位来表示结点的颜色,可以是红色或者是黑色,通过对任何一条从根节点到叶子节点上面的路径各个节点着色方式的限制,红黑树会自动确保没有一条路经会比其他路径的长度高出两倍,而是接近平衡的

2)红黑树最长路径是最短路径的两倍

3)每一个节点不是红色就是黑色

4)根节点是黑色的

5)如果一个节点是红色的,那么他的左右孩子的节点都是黑色的,说明红黑树没有两个连续相同的红色节点

6)对于每一个节点,从该节点到达后代的叶子结点的所有简单路径里面,均包含相同数目的黑色节点(每一条路径上都包含着相同数目的黑色节点,路径的计算必须指向空)

在红黑树中,对于每个节点,从该节点到其所有后代叶子节点的简单路径上,应包含相同数量的黑色节点,这也是红黑树的基本性质之一。

在计算路径上的黑色节点数量时,通常会包括空节点(NIL节点)因为空节点被视为黑色节点的一部分,并且它们对于保持红黑树的平衡性和性质是必要的,所以,在判断从任意节点到达后代叶子节点的所有简单路径是否包含相同数量的黑色节点时,应该将空节点(NIL节点)也计算在内

7)每一个叶子节点都是黑色的,此处的叶子节点指的是空节点

8)红黑树的最长路径:路径上节点黑红相间,一黑一红,最短路径:路径上全部是黑色节点

9)假设黑色节点总共有X个,整棵树的节点数量在[X,2X]之间

当总节点个数是X个的时候最短路径的长度:logX

当总结点个数是2X的时候最短路径长度是:logX+1,logX趋近于logN

所以最终总结:

最短路径长度为:logN

最长路径长度为:2logN

10)一个正常的二叉树,不会出现这种一条路径全部都是黑色的情况

 二)红黑树的插入:

1)首先要明白,插入的节点必须是红色的节点,如果最终插入的是黑色的节点,因为我们要最终保证每一条路径上都有数目相同的黑色节点,其他路经都必须得新增黑色节点,但是此时新插入的是一个黑色节点,其他路经也没有办法新增节点呀,但是此时就不满足一个条件,两个红色节点挨在一起了,所以需要调节成合适的颜色

2)红黑树是在二叉搜索树的基础上加上其平衡限制条件,因此红黑树的插入可以分为两步

2.1)按照二叉搜索树的规则插入新节点

2.2)检测插入新节点之后,判断红黑树的性质是否已经遭受到了破坏,因为新节点的默认颜色是红色,因此如果双亲结点的颜色是黑色,那么其实本质上并没有违反红黑树的任何性质,那么就不需要进行调整,但是当插入的新节点的双亲结点是红色的时候,就违反了不能有连在一起的红色节点,此时需要对红黑树来分情况进行讨论:

约定current为当前新插入的节点,parent为父亲节点,grandfather是祖父节点,uncle为叔叔节点

一)一共是有两种大的情况:parent是在grandfather的left节点:
1)current为红色节点,parent是红色节点,grandfather是黑色节点,uncle存在是红色节点,下面都是默认讨论curent是parent的左子树,但是实际情况current下可能是parent的左子树,还有可能是parent的右子树;

1.1)下面只是考虑到了grandfather以下的节点:发现只需要把parent节点和uncle节点变成黑色,就可以简单的满足以grandfather为根节点的树,从根节点到叶子节点的树是一颗标准的红黑树,此时gp的左子树一定是有一个黑色节点的;

1.2)第二个横线更深一步考虑,当考虑到granfather的父亲节点的时候,当grandfather的父亲节点是黑色的时候或者是grandfather节点是红色的时候,需要再进一步分情况进行讨论:

1.3)当grandfather的父亲节点是黑色的时候说明,grandfather的另一个孩子也是黑色节点

此时如果将grandfather的这个节点的父亲节点是一个黑色的节点那么如果只是单纯的将p和u变成黑色是万万不可以的,这样只会增加黑色节点的个数

1.4)假设grandfather的父亲节点是红色,此时可以分析出gp的左孩子一定是黑色的

2)current为红色,parent是红色,grandfather是黑色,uncle不存在或者是uncle是黑色

此时current下面一定有子树其他节点:是再调整的过程中current变成红色的

先进行右旋:

然后修改颜色:

3)current是红色,parent是红色,grandFather是黑色,uncle不存在或者uncle是黑色

二)第二种情况parent是在grandfather的right节点:

相关文章:

高阶数据结构(2)-----红黑树(未完成)

一)红黑树的基本概念和基本性质: 1)红黑树就是一种高度平衡的二叉搜索树,但是在每一个节点上面都增加了一个存储位来表示结点的颜色,可以是红色或者是黑色,通过对任何一条从根节点到叶子节点上面的路径各个节点着色方式的限制,红黑…...

[mockjs]Mock使用过程中的坑

[mockjs]Mock使用过程中的坑 现象描述原因分析解决方案修改源码处理无法识别的文件流 现象描述 mockjs在使用的过程中出现了下载文件无法正常打开的问题,但是在线上环境是正常的 console.log打印返回的response,发现是本地无法正常解析response.data 在代码中&am…...

华为云云耀云服务器L实例评测|部署前后端分离项目

✅作者简介:大家好,我是Leo,热爱Java后端开发者,一个想要与大家共同进步的男人😉😉 🍎个人主页:Leo的博客 💞当前专栏: 学习测评 ✨特色专栏: MyS…...

02目标检测-传统检测方法

目录 一、目标学习的检测方法变迁及对比 二、 基于传统手工特征的检测算法的定义 三、传统主要手工特征与算法 Haar特征与 人脸检测算法 - Viola-Jones(了解) HOG特征与 SVM 算法(了解)(行人检测、opencv实现) SIFT特征与SIFT算法(了解) DPM&#…...

RP-母版 流程图 发布和预览 团队项目

母版 创建一个模版,可根据形态不同引用不同母版。若不想母版受页面变化影响,也可以在引用时脱离母版 创建母版: 1) 转换为母版 2)在母版页面中添加 母版拖放行为 拖放行为,在母版名称上右键, 、 任意…...

【第200篇原创文章】解决低于1%概率出现的芯片VPSS模块跑飞的问题

在发布SDK内测的时候,我们发现在切换视频分辨率的时候有低概率出现VPSS模块跑飞的情况,概率低于1%,试个两三百次,能出1~2次。切换视频分辨率这个功能在安防产品上也确实存在需求,网络带宽不大好的地方分辨率可以适当下…...

微信小程序——生命周期详解(代码解读)

✅作者简介:2022年博客新星 第八。热爱国学的Java后端开发者,修心和技术同步精进。 🍎个人主页:Java Fans的博客 🍊个人信条:不迁怒,不贰过。小知识,大智慧。 💞当前专栏…...

多分类中混淆矩阵的TP,TN,FN,FP计算

关于混淆矩阵,各位可以在这里了解:混淆矩阵细致理解_夏天是冰红茶的博客-CSDN博客 上一篇中我们了解了混淆矩阵,并且进行了类定义,那么在这一节中我们将要对其进行扩展,在多分类中,如何去计算TP&#xff0…...

Linux系统:OpenSSH7.4p升级到9.0p(服务器漏洞)

清华大学开源软件镜像站下载地址: https://mirrors.tuna.tsinghua.edu.cn/pub/OpenBSD/OpenSSH/portable/openssh-9.0p1.tar.gz 一、升级 0、安装Telnet (1)为防止安装失败,无法用ssh做远程连接,因此先安装telnet yum…...

【面试刷题】——C++的特点简单说明

C是一种通用的编程语言,具有许多强大的特点,以下是其中一些主要特点的简单说明: 面向对象编程(OOP): C支持面向对象编程,允许将数据和操作封装在类中,提高了代码的可维护性和重用性…...

C2基础设施威胁情报对抗策略

威胁情报是指在信息安全和安全防御领域,收集、分析和解释与潜在威胁相关的信息,以便预先发现并评估可能对组织资产造成损害的潜在威胁,是一种多维度、综合性的方法,其通过信息的收集、分析和研判,帮助组织了解可能对其…...

差异备份详细说明(InsCode AI 创作助手)

差异备份详细说明 差异备份(Differential Backup)是一种备份策略,它与增量备份类似,但有一些关键区别。差异备份备份的是自上一次完整备份以来的所有更改数据,而不是自上一次备份以来的所有更改。这意味着差异备份文件…...

flask要点与坑

简介 Flask是一个用Python编写的Web应用程序框架,该框架简单易用、模块化、灵活性高。 该笔记主要记录Flask的关键要点和容易踩坑的地方 Flask 日志配置 Flask 中的自带logger模块(也是python自带的模块),通过简单配置可以实现…...

EasyUI combobox 实现搜索(模糊匹配)功能

很简单的一个下拉框搜索模糊匹配功能&#xff0c;在此记录&#xff1a; 1&#xff1a;页面实现&#xff1a; <select class"easyui-combobox" name"combobox" id"combobox" style"width:135px;height:25px;" headerValue"请选…...

Postman的高级用法一:重新认识postman核心模块

本请求示例来自于免费天气API&#xff1a; 实况天气接口API开发指南 未来一天天气预报api - 天气API 关于Postman的核心模块 全局变量请求接口请求体预处理脚本 类似beforeTest&#xff0c;在发起请求前的预执行逻辑&#xff0c;通常是生成一些动态变量值 测试用例模块 测试者…...

git命令的操作

git命令操作及命令大全 1.创建一个新的本地仓库&#xff1a;2.添加文件到仓库&#xff1a;3.远程仓库操作&#xff1a;4.分支操作&#xff1a;5.git命令大全 1.创建一个新的本地仓库&#xff1a; 使用命令git init在本地目录中创建一个新的git仓库。 2.添加文件到仓库&#x…...

超级详细 SQL 优化大全

1、MySQL的基本架构 1&#xff09;MySQL的基础架构图 左边的client可以看成是客户端&#xff0c;客户端有很多&#xff0c;像我们经常你使用的CMD黑窗口&#xff0c;像我们经常用于学习的WorkBench&#xff0c;像企业经常使用的Navicat工具&#xff0c;它们都是一个客户端。右…...

数据治理-数据存储和操作-数据库组织模型

数据库存储系统提供了一种将数据放入磁盘并管理和处理这些数据所需指令的封装方法&#xff0c;因此开发人员可以简单地使用指令来操作数据。数据库通常以3种形式进行组织&#xff1a;层次性、关系型和非关系型&#xff1b;这种归类并不是完全互斥的。一些数据库系统可以同时读写…...

IDEA最新激 20活23码

人狠话不多 大家好&#xff0c;最近Intelli Idea官方的校验规则进行了更新&#xff0c;之前已经成功激20活23的Idea可能突然无法使用了。 特地从网上整理了最新、最稳定的激20活23码分享给大家&#xff0c;希望可以帮助那些苦苦为寻找Idea激20活23码而劳累的朋友们。 本激23…...

flutter产物以aar形式嵌入android原生工程

以前做的项目中&#xff0c;flutter都是作为module嵌入原生工程中&#xff0c;新公司项目却是以aar形式嵌入android工程&#xff0c;这种优点是原生工程不必配置flutter环境也能跑了&#xff0c;这里记录一下简单步骤。 创建一个flutter module 通过android studio创建一个fl…...

Unity安卓构建实战指南:解决APK真机安装闪退与构建失败

1. 这不是一本“从零开始”的书&#xff0c;而是一份你真正上手Unity安卓游戏开发前必须撕开的说明书我带过三届Unity实习工程师&#xff0c;也帮二十多个独立开发者把Demo打包进Google Play。每次看到新人在“安卓构建失败”报错里反复挣扎&#xff0c;或者对着“IL2CPP编译卡…...

51单片机驱动ST7735S彩屏避坑指南:从5秒刷屏到流畅贪吃蛇的优化实战

51单片机驱动ST7735S彩屏性能优化实战&#xff1a;从卡顿到流畅游戏的蜕变之路当一块128x160分辨率的ST7735S彩屏遇上传统的51单片机&#xff0c;这种组合看似矛盾却又充满挑战。许多开发者初次尝试时会发现&#xff0c;原本在STM32等平台上运行流畅的显示驱动&#xff0c;移植…...

从多路复用到三维光阵:Arduino驱动8x8x8 LED立方体全解析

1. 项目概述&#xff1a;用Arduino点亮一个三维世界几年前&#xff0c;我第一次在创客展上看到一个8x8x8的LED立方体&#xff0c;那种由数百个光点构成的、在三维空间中流动的动画效果&#xff0c;瞬间就把我吸引住了。它不像普通的平面LED屏&#xff0c;而是真正有“深度”的光…...

Agent开发面试通关攻略:吃透稳拿offer

阅读前置&#xff1a;2026年当下最卷也最缺人的AI岗位&#xff0c;一定是AI Agent开发。最近刷遍CSDN、牛客、力扣最新面经&#xff0c;发现一个非常明显的招聘趋势&#xff1a;普通大模型微调岗位饱和内卷&#xff0c;而AI Agent开发岗位人才严重缺口&#xff0c;薪资更高、竞…...

钱钟书《围城》第1-5章阅读笔记:一场关于人生困境的提前预演

前言 钱钟书先生的《围城》被誉为"新儒林外史"&#xff0c;是中国现代文学史上风格独特的讽刺经典。这部创作于20世纪40年代的长篇小说&#xff0c;以抗战初期为背景&#xff0c;通过主人公方鸿渐的人生轨迹&#xff0c;深刻揭示了知识分子群体的精神困境与人性弱点。…...

如何让Rhino 3D模型在Blender中保持完整数据:import_3dm插件深度解析

如何让Rhino 3D模型在Blender中保持完整数据&#xff1a;import_3dm插件深度解析 【免费下载链接】import_3dm Blender importer script for Rhinoceros 3D files 项目地址: https://gitcode.com/gh_mirrors/im/import_3dm 当建筑师需要在Blender中渲染Rhino设计的建筑模…...

Burp Suite证书安装全解:HTTPS抓包失败的根源与跨平台命令行方案

1. 为什么必须亲手安装Burp Suite证书——不是“点一下就完事”的操作很多人第一次在手机或测试设备上配置Burp Suite代理时&#xff0c;会下意识认为&#xff1a;只要把电脑上的Burp监听地址填进Wi-Fi代理设置&#xff0c;再用浏览器访问http://burp&#xff0c;点击那个绿色的…...

render_async嵌套渲染:构建复杂异步界面的完整解决方案

render_async嵌套渲染&#xff1a;构建复杂异步界面的完整解决方案 【免费下载链接】render_async render_async lets you include pages asynchronously with AJAX 项目地址: https://gitcode.com/gh_mirrors/re/render_async 在现代Web开发中&#xff0c;页面加载速度…...

Log4Shell漏洞深度解析:Spring Boot日志注入原理与四层修复方案

1. 这个漏洞不是“远程执行代码”那么简单——它是一次对Java生态信任链的系统性击穿Log4j CVE-2021-44228&#xff0c;业内常简称为“Log4Shell”&#xff0c;2021年12月爆发时&#xff0c;我正在给一家金融客户的Spring Boot微服务集群做灰度发布前的安全加固。凌晨三点收到告…...

如何用Untrunc拯救损坏视频?2025年终极MP4修复工具完全指南

如何用Untrunc拯救损坏视频&#xff1f;2025年终极MP4修复工具完全指南 【免费下载链接】untrunc Restore a damaged (truncated) mp4, m4v, mov, 3gp video. Provided you have a similar not broken video. 项目地址: https://gitcode.com/gh_mirrors/unt/untrunc 当你…...