数据结构和算法-红黑树（定义 性质 查找 插入 删除）

文章目录

  • 红黑树的定义和性质
    • 为什么要发明红黑树？
    • 红黑树怎么考
    • 总览
    • 红黑树的定义
      • 实例：一颗红黑树
      • 练习：是否符合红黑树的要求
      • 一种可能的出题思路
      • 补充概念：节点黑高
    • 红黑树的性质
  • 红黑树的查找
  • 红黑树的插入
    • 实例
    • 小结
    • 与黑高相关的理论
  • 红黑树的删除

红黑树的定义和性质

为什么要发明红黑树？

插入和删除即一般不会破坏特性，并且即使破坏，恢复的代价比较低
在这里插入图片描述
在这里插入图片描述

红黑树怎么考

在这里插入图片描述

总览

在这里插入图片描述

红黑树的定义

叶节点不是我们认为的没有子树的节点了，是空节点，即我们所认识的叶子节点的孩子就是叶节点
在这里插入图片描述

实例：一颗红黑树

在这里插入图片描述

练习：是否符合红黑树的要求

在这里插入图片描述
在这里插入图片描述
将6变为红后
在这里插入图片描述
但此时7不满足二叉排序树，替换为11即可
在这里插入图片描述

一种可能的出题思路

在这里插入图片描述

补充概念：节点黑高

注意不包括出发的节点
在这里插入图片描述

红黑树的性质

由于根节点到任意节点的的路径上所含黑节点的数目相同，最短就是全黑嘛，但最长就是有红节点在路径上，由于不存在相邻的红节点这个特性，所以节点树最多的情况就是在黑节点之间有红节点，此时总结点数模至多为全黑节点的两倍
在这里插入图片描述

红黑树的查找

和查找平衡二叉树和二叉排序树一样，小于走左子树，大于走右子树
在这里插入图片描述

红黑树的插入

在这里插入图片描述

实例

非根节点的插入只需关注不红红的这个问题

插入非根节点为红是为了保持黑路同
插入5后发现有红红，此时叔节点为黑，相对爷节点是LL型，此时父节点右旋换爷节点同时变色
在这里插入图片描述
插入后红红，此时叔为红，此时叔父爷变色，爷看作新节点，，此时爷节点是根但为红色再变色
在这里插入图片描述
此时再插入一个，存在红红，此时叔为黑，且为RR,此时父换爷，同时父和爷变色
在这里插入图片描述
此时加入节点，存在红红，且叔为红，此时叔父爷变色，同时将爷看作新加入的节点，发现没破坏红黑树的特性
在这里插入图片描述
插入3没啥大问题

在这里插入图片描述
插入2，此时红红，同样父换爷，同时染色

在这里插入图片描述
此时红叔，叔父爷变色，同时爷看作新节点
在这里插入图片描述
插入35
在这里插入图片描述
插入25

在这里插入图片描述
插入18
在这里插入图片描述
插入22
红红，叔为红，叔父爷变色，此时将爷看作新节点，此时存在红红，而该新节点叔为红，所以此时叔父爷都变色，此时的爷看作新节点，但为红节点，所以变黑

在这里插入图片描述
插入23，此时红红，叔为黑，且为LR，此时左旋再右旋，最后变色

在这里插入图片描述
左旋结果
在这里插入图片描述
右旋结果

在这里插入图片描述
最后将原来的儿爷节点变色

在这里插入图片描述
插入24
红红，此时叔父爷变色，爷看作新节点，存在红红
此时叔为黑，为LR
在这里插入图片描述
先左旋
在这里插入图片描述
再右旋
在这里插入图片描述
原本的儿爷变色
在这里插入图片描述
插入19
在这里插入图片描述
插入18
此时已经存在18，可以放18的左边也可以放右边

若插入右边
在这里插入图片描述
先右旋
在这里插入图片描述
再左旋

在这里插入图片描述
原本儿爷变色

在这里插入图片描述

小结

由根节点到叶节点的最长路径不大于最短路径的两倍可知道左右子树的高度也不过两倍关系
在这里插入图片描述

与黑高相关的理论

外部节点就是空节点
根节点黑高为h的红黑树，此时内部节点要最少的话，必须即全黑即可，因为有红的话不能有相邻的。而此时全黑的情况下也是吗，满树，不然达不到从根节点的黑高为h
在这里插入图片描述
黑高大于等于h/2是由于如果是一个黑一红那么黑高将大于等于h/2，又由根节点黑高可得出内部节点数最少数量，最后可得出总高度的范围
在这里插入图片描述

红黑树的删除

删除方式和二叉排序树一样
只是调整方式不同
在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/263259.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

深入浅出：Swagger annotations （注解）在API文档中的应用

深入浅出：Swagger annotations （注解）在API文档中的应用

Swagger 提供的注解集是其框架中定义 API 规范和文档的重要工具。这些注解在代码里标注重要部分，为 Swagger 的解析工作铺路，进而生成详尽的 API 文档。开发者编写的注释能够被转换成直观的文档，并展现API端点、参数和响应等信息。这不仅提升…
阅读更多...
创新固定资产管理方式：易点易动集成企业微信的全新解决方案

创新固定资产管理方式：易点易动集成企业微信的全新解决方案

在当今竞争激烈的商业环境中，高效的固定资产管理对于企业的成功至关重要。然而，传统的资产管理方式往往繁琐、容易出错，并且缺乏实时性和准确性。为了解决这些挑战，易点易动与企业微信进行了集成合作，推出了一种全新的…
阅读更多...
Enge问题解决教程

Enge问题解决教程

目录 解决问题的一般步骤： 针对"Enge问题"的具体建议： 以下是一些普遍适用的解决问题的方法： 以下是一些更深入的Enge浏览器问题和解决办法： 浏览器性能问题： 浏览器插件与网站冲突： 浏览…
阅读更多...
输电线路定位：应对复杂环境，确保电力传输畅通无阻

输电线路定位：应对复杂环境，确保电力传输畅通无阻

在现代社会，电力作为我们生活和工业生产的重要能源，其安全、稳定、高效的传输显得尤为重要。而输电线路的定位与监测，正是保障电力传输畅通无阻的关键环节。恒峰智慧科技将详细介绍输电线路分布式故障定位及隐患监测装置HFP-GZS2000的技术原理…
阅读更多...
RabbitMQ 常用知识点总结，纯手绘23张图带你拿下

RabbitMQ 常用知识点总结，纯手绘23张图带你拿下

请访问原文 Java面试必备！RabbitMQ 常用知识点总结，纯手绘23张图带你拿下 - 知乎 思维导航： 基础 为什么使用 MQ？MQ缺点几种 MQ 实现总结完整架构图RabbitMQ 六种工作模式 1、Simple 简单模式2、work 工作模式3、publish/subsc…
阅读更多...
阻塞 IO(BIO)

阻塞 IO(BIO)

文章目录 阻塞 IO(BIO)模型等待队列头init_waitqueue_headDECLARE_WAIT_QUEUE_HEAD 等待队列项使用方法驱动程序应用程序模块使用参考 阻塞 IO(BIO) 模型 等待队列是内核实现阻塞和唤醒的内核机制。 等待队列以循环链表为基础结构，链表头和链表项分别为等待队列头和…
阅读更多...
Notepad++：多行数据操作

Notepad++：多行数据操作

1）删除关键字之后（或之前）的所有字符 删除s之后（包含s）的所有内容；快捷键：s.*$ 替换成功 删除s之前（包含s）的所有内容；快捷键：^.*s 2&#xff09…
阅读更多...
ssh远程管理服务

ssh远程管理服务

什么是ssh SSH是一种加密的网络协议，用于在不安全的网络中安全地传输数据。它允许用户通过一个安全的通道连接到远程计算机，并在该通道上执行各种网络服务，例如远程登录和文件传输。 SSH使用公钥加密技术来验证远程计算机的身份，并…
阅读更多...
NXP iMX8MM 通过 TFTP和 NFS 启动示例

NXP iMX8MM 通过 TFTP和 NFS 启动示例

By Toradex秦海 1). 简介 嵌入式 Linux 设备开发调试时候为了方便部署各种配置和修改常用的一种方法就是通过网络启动，具体就是将 Linux Kernel（以及 Device tree/Device Tree overlays) 从开发主机的 TFTP 服务加载， Linux rootfs 通过开发…
阅读更多...
mysql SQL执行超时问题

mysql SQL执行超时问题

show variables like max_execution_time 使用这个命令查看了，没有设置sql执行超时时间，那么大概率问题就出在阿里的Druid数据库连接池出了问题 尝试着socketTimeout由60000毫秒改成10000毫秒，果然执行了十几秒就超时报错了 socketTime…
阅读更多...
【JS】按照a＞b＞c＞d＞e＞f的优先级，将a,b,c,d,e,f元素进行筛选，选出三个不为空字符的元素进行字符拼接

【JS】按照a＞b＞c＞d＞e＞f的优先级，将a,b,c,d,e,f元素进行筛选，选出三个不为空字符的元素进行字符拼接

设计思路： 1、定义一个数组，把元素按照优先级进行排序； 2、 使用 filter() 方法过滤掉空字符串元素，得到一个新的数组; 3、在排序函数中，循环数组，使用 indexOf() 方法获取元素 a 和 b 在数组中的索引&a…
阅读更多...
消息队列选型：RocketMQ 适用哪些场景？

消息队列选型：RocketMQ 适用哪些场景？

关于消息队列的应用场景有很多，不同消息队列由于在实现上有着细微的差别，所以就有各自适合的应用场景。 如果你的工作以业务开发为主，建议了解一下消息队列背后的设计思想，以及其基本的特性，这样才能在业务开发中应用…
阅读更多...
24 同学聚会

24 同学聚会

出局记1&#xff0c;未出局记0 #include <iostream> using namespace::std; using std::cout; using std::cin; int main() {int num,n;cin >> num >> n;int nums[num];for(int i0; i<num; i){nums[i]0;}int t-1;for(int i0; i<num-1; i){for(int j0…
阅读更多...
鸿蒙原生应用/元服务开发-Stage模型能力接口（九）下

鸿蒙原生应用/元服务开发-Stage模型能力接口（九）下

ohos.app.ability.UIAbility (UIAbility)Caller 通用组件Caller通信客户端调用接口, 用来向通用组件服务端发送约定数据。 Caller.call call(method: string, data: rpc.Parcelable): Promise<void>; 向通用组件服务端发送约定序列化数据。 系统能力&#xff1a;Syste…
阅读更多...
一款好用又强大的开源社区

一款好用又强大的开源社区

大家好&#xff0c;我是 Java陈序员。 作为程序员&#xff0c;平时上班的时候逛技术论坛是必不可少的&#xff0c;如CSDN、掘金、博客园… 逛技术论坛一般都是为了查找一些问题的解决方案&#xff0c;毕竟遇到的坑全是别人踩过的&#xff01;或者有时候是在上面学习&#xff…
阅读更多...
27、ResNet50处理STEW数据集，用于情感三分类+全备的代码

27、ResNet50处理STEW数据集，用于情感三分类+全备的代码

1、数据介绍 IEEE-Datasets-STEW:SIMULTANEOUS TASK EEG WORKLOAD DATASET &#xff1a; 该数据集由48名受试者的原始EEG数据组成&#xff0c;他们参加了利用SIMKAP多任务测试进行的多任务工作负荷实验。受试者在休息时的大脑活动也在测试前被记录下来&#xff0c;也包括在其…
阅读更多...
测试——VS断点调试

测试——VS断点调试

1、问题 本文使用VS对c程序执行简单的断点调试。调试的c程序&#xff1a; #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <Windows.h> #include <string.h>using namespace std;int main(void) {float r0;float s0;printf("请输入圆的…
阅读更多...
【Java】Mybatis

【Java】Mybatis

MyBatis JavaEE三层框架&#xff1a;表现层、业务层、持久层。 现在开始学习持久层。持久层就是负责与数据库打交道的代码。 框架&#xff1a;就是一个半成品软件。在框架的基础上&#xff0c;可以更加高效地写出代码。 1、MyBatis快速入门 1、准备工作&#xff08;创建sp…
阅读更多...
Spring Environment 注入引起NPE问题排查

Spring Environment 注入引起NPE问题排查

文章目录 背景原因分析1&#xff09;Spring Aware Bean 是什么&#xff1f;2&#xff09;从 Spring Bean 的生命周期入手 解决方案 背景 写业务代码遇到使用 Spring Environment 注入为 null 的情况&#xff0c;示例代码有以下两种写法&#xff0c;Environment 实例都无法注入…
阅读更多...
华为OD机试 - 多段线数据压缩（Java JS Python C）

华为OD机试 - 多段线数据压缩（Java JS Python C）

题目描述 下图中，每个方块代表一个像素，每个像素用其行号和列号表示。 为简化处理，多线段的走向只能是水平、竖直、斜向45度。 上图中的多线段可以用下面的坐标串表示：(2,8),(3,7),(3,6),(3,5),(4,4),(5,3),(6,2),(7,3),(8,4),(7,5)。 但可以发现，这种表示不是最简的，…
阅读更多...
最新文章

Copyright @ 2022~2023