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

【数据结构 | 红黑树】红黑树的性质和插入结点时的调整

文章目录

  • 红黑树
  • 红黑树插入时的调整?
    • 1. 插入结点是根结点
    • 2. 插入结点的叔叔是红色
    • 3. 插入结点的叔叔是黑色
      • LL 型
      • RR型
      • LR型
      • RL型

在这里插入图片描述

红黑树

  • 前提:二叉搜索树(左 < 根 < 右)—— 左根右
  • 根和**叶子(NULL)**都是黑色 —— 根叶黑
  • 不存在连续的两个红色节点 —— 不红红
  • 任一结点到叶所有路径黑结点数量相同 —— 黑路同

注意:叶子节点是空结点
原因:空结点可以帮助捋清所有路径,确保所有路径黑色结点数量都相同

  • 最长路径不超过最短路径的两倍(任一结点左右子树高度相差不超过两倍)
    • AVL树(平衡二叉树)左右子树高度绝对值不超过1,可发现 AVL 树对平衡要求更加严格,在树高上比红黑树控制得更加平衡 —— 查询上,红黑树略逊于 AVL 树,但时间复杂度都是O(logn)
    • 但红黑树在插入和删除上更高效

红黑树插入时的调整?

红黑树插入结点默认是红色,且只可能违反根叶红或者不红红

若插入时,红黑树性质被破坏,需要根据以下几种情况来进行调整:

1. 插入结点是根结点

  • 根结点直接变黑(违反根叶黑的性质)

2. 插入结点的叔叔是红色

  • 叔父爷变色(红变黑,黑变红),爷爷变插入节点(将爷爷视为插入结点,继续判定是否破坏红黑树的性质)
    在这里插入图片描述

3. 插入结点的叔叔是黑色

  • 根据(LL、RR、LR、RL)以爷爷作为旋转点进行旋转,然后对旋转点和旋转中心变色
    • 关于(LL、RR、LR、RL)是平衡二叉树的旋转操作,可看文章:【数据结构 | 平衡二叉树】失衡时如何调整
      也可以看视频讲解:平衡二叉树(AVL树)

LL 型

在这里插入图片描述

RR型

在这里插入图片描述

LR型

在这里插入图片描述

RL型

在这里插入图片描述

对上述过程有疑问,可以看这个视频来理解:红黑树 - 定义, 插入, 构建

相关文章:

【数据结构 | 红黑树】红黑树的性质和插入结点时的调整

文章目录 红黑树红黑树插入时的调整&#xff1f;1. 插入结点是根结点2. 插入结点的叔叔是红色3. 插入结点的叔叔是黑色LL 型RR型LR型RL型 红黑树 前提&#xff1a;二叉搜索树&#xff08;左 < 根 < 右&#xff09;—— 左根右根和**叶子&#xff08;NULL&#xff09;**都…...

mysql学习教程,从入门到精通,SQL导入数据(44)

1.SQL 导出数据 以下是一个关于如何使用 SQL 导出数据的示例。这个示例将涵盖从一个关系数据库管理系统&#xff08;如 MySQL&#xff09;中导出数据到 CSV 文件的基本步骤。 1.1、前提条件 你已经安装并配置好了 MySQL 数据库。你有访问数据库的权限。你知道要导出的表名。…...

【SpringAI】(二)让你的Java程序接入大模型——适合Java宝宝的大模型应用开发

开始之前&#xff0c;如果你对大模型完全没了解过&#xff0c;建议阅读之前的大模型入门文章&#xff1a; 【SpringAI】&#xff08;一&#xff09;从实际场景入门大模型——适合Java宝宝的大模型应用开发 那么今天就开始写一个基于Spring AI程序的HelloWord!将大模型接入到咱…...

音频剪辑在线工具 —— 让声音更精彩

你是否曾梦想过拥有自己的声音创作空间&#xff0c;却苦于复杂的音频编辑软件&#xff1f;接下来&#xff0c;让我们一同揭开这些音频剪辑在线工具的神秘面纱&#xff0c;看看它们如何帮助你实现从录音到发布的无缝衔接。 1.福昕音频剪辑 链接直达>>https://www.foxits…...

​http短连接和长连接​

参考短连接和长连接 短连接&#xff1a;客户端向服务器每进行一次Http操作&#xff0c;都需建立一次连接&#xff0c;任务完成后&#xff0c;断开连接&#xff1b;长连接&#xff1a;建立长连接后&#xff0c;传输数据的连接将不会中断&#xff0c;客户端每次访问服务器时都会…...

日志分析删除

日志分析 场景 运维嫌弃生产环境打印日志过多&#xff0c;而且日志存储需要费用&#xff0c;让我们减少打印日志大小&#xff0c;所以需要分析日志在哪里打印的过多 解决方案 读取生产日志文件&#xff0c;统计分析打印日志的地方&#xff0c;最后删除代码中打印日志的地方…...

DART: Implicit Doppler Tomography for Radar Novel View Synthesis 笔记

Link&#xff1a;https://wiselabcmu.github.io/dart/ Publish&#xff1a; 2024CVPR Abstract DART主要任务就是用来合成雷达距离多普勒图像range-droppler&#xff0c;可用于生成高质量的断层扫描图像。 Related Work 1 Radar Simulation 基于模型的方法 任务&#xff…...

redis-cli执行lua脚本

连接redis服务器命令 redis-cli -h 10.10.xx.xx -p 6380 -a password执行lua脚本传递KEY VALUE redis-cli -h 10.10.xx.xx -p 6380 -a password key1 key2 , arg1 arg2key和参数通过逗号分割&#xff0c;逗号前后必须有一个空格 如下执行lua脚本示例&#xff1a; -- script.…...

MySQL9的3个新特性

【图书推荐】《MySQL 9从入门到性能优化&#xff08;视频教学版&#xff09;》-CSDN博客 《MySQL 9从入门到性能优化&#xff08;视频教学版&#xff09;&#xff08;数据库技术丛书&#xff09;》(王英英)【摘要 书评 试读】- 京东图书 (jd.com) 本文讲解MySQL9的3个新特性&…...

《网络基础之 HTTP 协议:状态码含义全解析》

《网络基础之 HTTP 协议&#xff1a;状态码含义全解析》 在网络通信的浩瀚世界中&#xff0c;HTTP 协议犹如一座坚实的桥梁&#xff0c;连接着客户端与服务器。而其中的状态码&#xff0c;则是这座桥梁上的重要标识&#xff0c;为双方的交互提供了关键的反馈信息。 一、状态码…...

java真的正在越来越失去竞争力了吗

题记&#xff1a; java真的在越来越失去竞争力了吗&#xff1f;最近参加校招面试&#xff0c;过程中有问道java的问题&#xff0c;有的同学很直接了当&#xff08;或者是不假思索&#xff09;地说&#xff0c;java已经过时了吧&#xff0c;现在学java的人越来越少了。那么事实…...

【通过zip方式安装mysql服务】

通过zip方式安装mysql服务 Mysql安装包下载mysql安装及环境配置1.解压缩配置环境变量初始化mysql配置安装mysql服务启动MySQL服务连接mysql修改root用户密码 Mysql安装包下载 通过访问mysql官网下载&#xff1a;mysql下载地址 mysql安装及环境配置 1.解压缩 下载完成后&am…...

每日OJ题_WY3小易的升级之路_数学模拟_C++_Java

目录 牛客_WY3小易的升级之路_数学模拟 题目解析 C代码 Java代码 牛客_WY3小易的升级之路_数学模拟 小易的升级之路_牛客题霸_牛客网 (nowcoder.com) 描述&#xff1a; 小易经常沉迷于网络游戏.有一次,他在玩一个打怪升级的游戏,他的角色的初始能力值为 a.在接下来的一段…...

python xml的读取和写入

import xml.etree.ElementTree as ET from xml.dom import minidom# 读取XML文档 tree ET.parse("./xml_3/z_20240827_001.xml") root tree.getroot() # 获取size元素 size_find_0 root.find("size") # 获取width子元素 size_w size_find_0.find("…...

WebGL 小白入门学习

1. WebGL是什么&#xff1f; WebGL&#xff08;Web Graphics Library&#xff09;是一种JavaScript API&#xff0c;它允许你在不需要安装任何额外插件的情况下&#xff0c;直接在浏览器中渲染高性能的2D和3D图形。WebGL利用了用户的图形处理单元&#xff08;GPU&#xff09;来…...

OSI七层协议

OSI&#xff08;Open System Interconnection&#xff09;七层协议&#xff0c;即开放式系统互联参考模型&#xff0c;是一个由国际标准化组织&#xff08;ISO&#xff09;提出的用于描述计算机网络中通信的结构和功能的理论模型。它将网络通信过程分为七个层次&#xff0c;每个…...

超平面(Hyperplane)和半空间(Halfspace)

文章目录 一、超平面&#xff08;Hyperplane&#xff09;1. 定义2. 超平面的方程3. 例子4. 超平面的性质 二、半空间&#xff08;Halfspace&#xff09;1. 定义2. 半空间的表示3. 半空间的性质 三、超平面与半空间的关系四、应用1. 线性规划2. 机器学习3. 计算几何4. 凸分析 五…...

TCP(Transmission Control Protocol,传输控制协议)整理

TCP&#xff08;Transmission Control Protocol&#xff0c;传输控制协议&#xff09;是一种面向连接的、可靠的传输协议&#xff0c;它是OSI&#xff08;Open System Interconnection&#xff0c;开放式系统互联&#xff09;模型中的第四层协议&#xff0c;通常使用于网络中的…...

R语言绘制线性回归图

线性回归图以二维坐标系展示两个变量关系。数据点代表实际观测值&#xff0c;核心是线性回归线。此线通过统计方法确定&#xff0c;与数据点距离平方和最小。它反映变量间线性趋势&#xff0c;斜率正负决定相关方向。可用于预测因变量值&#xff0c;也能进行推断统计。在数据分…...

C++进阶:map和set的使用

目录 一.序列式容器和关联式容器 二.set系列的使用 2.1set容器的介绍 2.2set的构造和迭代器 2.3set的增删查 2.4insert和迭代器遍历的样例 2.5find和erase的样例 ​编辑 2.6multiset和set的差异 2.7简单用set解决两道题 两个数组的交集 环形链表二 三.map系列的使用…...

nlp_structbert_sentence-similarity_chinese-large 赋能智能客服:基于Vue前端的问题相似度匹配实践

nlp_structbert_sentence-similarity_chinese-large 赋能智能客服&#xff1a;基于Vue前端的问题相似度匹配实践 你有没有遇到过这种情况&#xff1f;在某个网站的客服对话框里&#xff0c;输入一个问题&#xff0c;等了半天&#xff0c;要么是机器人答非所问&#xff0c;要么…...

万象视界灵坛基础教程:PyTorch+Transformers环境搭建与CLIP零样本推理入门

万象视界灵坛基础教程&#xff1a;PyTorchTransformers环境搭建与CLIP零样本推理入门 1. 环境准备与快速部署 1.1 系统要求 Python 3.8或更高版本支持CUDA的NVIDIA GPU&#xff08;推荐&#xff09;至少8GB显存&#xff08;CLIP-ViT-L/14模型需求&#xff09;10GB以上可用磁…...

文明降级指南:回归纸笔躲避AI监控

AI监控时代的测试者困境在软件测试领域&#xff0c;人工智能的渗透已从效率工具演变为一种全景式的监控架构。AI驱动的测试套件能够以前所未有的速度执行用例、预测缺陷并生成报告&#xff0c;将测试周期与人力成本压缩至惊人水平。然而&#xff0c;这一技术乌托邦的背后&#…...

如何快速解锁AMD 780M APU的完整AI性能?终极优化指南

如何快速解锁AMD 780M APU的完整AI性能&#xff1f;终极优化指南 【免费下载链接】ROCmLibs-for-gfx1103-AMD780M-APU ROCm Library Files for gfx1103 and update with others arches based on AMD GPUs for use in Windows. 项目地址: https://gitcode.com/gh_mirrors/ro/…...

Origin绘图进阶:如何在现有图形上叠加散点图与等高线(附MATLAB对比)

Origin数据可视化进阶&#xff1a;多层图表叠加与等高线绘制实战 科研图表的美观性与信息密度往往决定了研究成果的呈现效果。作为一款专业的数据分析与可视化工具&#xff0c;Origin在复杂图表叠加方面展现出独特优势&#xff0c;尤其适合需要同时展示散点分布与等高线趋势的科…...

如何快速解锁网易云音乐NCM文件:ncmdumpGUI终极指南

如何快速解锁网易云音乐NCM文件&#xff1a;ncmdumpGUI终极指南 【免费下载链接】ncmdumpGUI C#版本网易云音乐ncm文件格式转换&#xff0c;Windows图形界面版本 项目地址: https://gitcode.com/gh_mirrors/nc/ncmdumpGUI 还在为网易云音乐下载的NCM格式文件无法在其他…...

虚拟同步发电机这玩意儿搞并网真心刺激!今天咱们直接拆解一个双机并联的MATLAB/Simulink仿真模型,手把手看它怎么扛住240kW的暴力测试

MATLAB/Simulink虚拟同步发电机&#xff08;vsg) 双机并联 仿真模型&#xff0c;附参考文献。 电压电流双闭环控制&#xff0c;SPWM调制技术&#xff1a;运用正弦波脉宽调制&#xff08;SPWM&#xff09;技术&#xff0c;优化波形输出。 总负荷承载 轻松应对240kW有功功率及10k…...

实战指南:从零构建PyTorch版Latent Diffusion Models(含DDPM/DDIM/PLMS全流程解析)

1. 环境准备与项目搭建 在开始构建Latent Diffusion Models之前&#xff0c;我们需要准备好开发环境。这里推荐使用Python 3.8和PyTorch 1.12版本。如果你有GPU设备&#xff0c;建议安装CUDA 11.3以上版本以获得更好的训练性能。 首先创建一个conda虚拟环境&#xff1a; conda …...

哈工大深圳LaTeX论文模板:5分钟搞定专业学位论文排版的终极方案

哈工大深圳LaTeX论文模板&#xff1a;5分钟搞定专业学位论文排版的终极方案 【免费下载链接】hitszthesis A dissertation template for Harbin Institute of Technology, ShenZhen (HITSZ), including bachelor, master and doctor dissertations. 项目地址: https://gitcod…...

Pixel Script Temple 为C++高性能计算项目生成优化脚本

Pixel Script Temple 为C高性能计算项目生成优化脚本 1. 高性能计算开发的痛点 在C高性能计算领域&#xff0c;开发者经常面临一个共同困境&#xff1a;明明硬件资源充足&#xff0c;但程序性能就是上不去。你可能也遇到过这样的情况 - 代码逻辑没问题&#xff0c;算法也正确…...