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

数据结构—红黑树

红黑树介绍

红黑树(Red Black Tree)是一种自平衡二叉查找树。由于其自平衡的特性,保证了最坏情形下在 O(logn) 时间复杂度内完成查找、增加、删除等操作,性能表现稳定。

在 JDK 中,TreeMap、TreeSet 以及 JDK1.8 的 HashMap 底层都用到了红黑树。

为什么需要红黑树

红黑树的诞生就是为了解决二叉查找树的缺陷。

二叉查找树是一种基于比较的数据结构,它的每个节点都有一个键值,而且左子节点的键值小于父节点的键值,右子节点的键值大于父节点的键值。这样的结构可以方便地进行查找、插入和删除操作,因为只需要比较节点的键值就可以确定目标节点的位置。

但是,二叉查找树有一个很大的问题,就是它的形状取决于节点插入的顺序。如果节点是按照升序或降序的方式插入的,那么二叉查找树就会退化成一个线性结构,也就是一个链表。这样的情况下,二叉查找树的性能就会大大降低,时间复杂度就会从 O(logn) 变为 O(n)。

红黑树的诞生就是为了解决二叉查找树的缺陷,因为二叉查找树在某些情况下会退化成一个线性结构。

红黑树特点

  1. 每个节点非红即黑。黑色决定平衡,红色不决定平衡。
  2. 根节点总是黑色的。
  3. 每个叶子节点都是黑色的空节点也就是 NIL 节点。这里指的是红黑树都会有一个空的叶子节点,是红黑树自己的规则。
  4. 如果节点是红色的,则它的子节点必须是黑色的,反之不一定。通常这条规则也叫不会有连续的红色节点。一个节点最多临时会有 3 个节点,中间是黑色节点,左右是红色节点。
  5. 从任意节点出发,沿着这个节点到达其所有叶子节点的路径上,经过的黑色节点的数量必须相同。每一层都只是有一个节点贡献了树高决定平衡性,也就是对应红黑树中的黑色节点。

正是这些特点才保证了红黑树的平衡,让红黑树的高度不会超过 2log(n+1)。

红黑树数据结构

建立在 BST 二叉搜索树的基础上,AVL、2-3 树、红黑树都是自平衡二叉树(统称 B-树)。但相比于 AVL 树,高度平衡所带来的时间复杂度,红黑树对平衡的控制要宽松一些,红黑树只需要保证黑色节点平衡即可。

红黑树结构实现

public class Node {public Class<?> clazz;public Integer value;public Node parent;public Node left;public Node right;// AVL 树所需属性public int height;// 红黑树所需属性public Color color = Color.RED;}

1.左倾染色

  • 染色时根据当前节点的爷爷节点,找到当前节点的叔叔节点。
  • 再把父节点染黑、叔叔节点染黑,爷爷节点染红。但爷爷节点染红是临时的,当平衡树高操作后会把根节点染黑。

2.右倾染色

3.左旋调衡

一次左旋

右旋+左旋

4.右旋调衡

一次右旋

左旋+右旋

相关文章:

数据结构—红黑树

红黑树介绍 红黑树&#xff08;Red Black Tree&#xff09;是一种自平衡二叉查找树。由于其自平衡的特性&#xff0c;保证了最坏情形下在 O(logn) 时间复杂度内完成查找、增加、删除等操作&#xff0c;性能表现稳定。 在 JDK 中&#xff0c;TreeMap、TreeSet 以及 JDK1.8 的 …...

MES实施之工控机和电脑的选择

在MES项目实施过程中,经常会碰到工控机和电脑的选型问题,那么他们的区别是什么? 1、控机和普通个人电脑(PC)相比,具有以下几个区别: 1.运行环境不同:工控机通常需要在各种恶劣的工业环境中运行,如高温、高湿、强电磁干扰等,因此需要具有防尘、防水、抗干扰等特点。而…...

京东云服务器4核8G主机租用价格418元一年,1899元3年

京东云轻量云主机4核8G服务器租用价格418元一年&#xff0c;1899元3年&#xff0c;配置为&#xff1a;轻量云主机4C8G-180G SSD系统盘-5M带宽-500G月流量&#xff0c;京东云主机优惠活动 yunfuwuqiba.com/go/jd 可以查看京东云服务器详细配置和精准报价单&#xff0c;活动打开如…...

【多模态融合】MetaBEV 解决传感器故障 3D检测、BEV分割任务

前言 本文介绍多模态融合中&#xff0c;如何解决传感器故障问题&#xff1b;基于激光雷达和相机&#xff0c;融合为BEV特征&#xff0c;实现3D检测和BEV分割&#xff0c;提高系统容错性和稳定性。 会讲解论文整体思路、模型框架、论文核心点、损失函数、实验与测试效果等。 …...

[通俗易懂]《动手学强化学习》学习笔记1-第1章 初探强化学习

文章目录 前言第1章 初探强化学习1.1 简介序贯决策&#xff08;sequential decision making&#xff09;任务&#xff1a;强化学习与有监督学习或无监督学习的**区别**&#xff1a;改变未来 1.2 什么是强化学习环境交互与有监督学习的区别1&#xff1a;改变环境 &#xff08;说…...

centOS如何升级python

centOS下升级python版本的详细步骤 1、可利用linux自带下载工具wget下载&#xff0c;如下所示&#xff1a; 笔者安装的是最小centos系统&#xff0c;所以使用编译命令前&#xff0c;必须安装wget服务&#xff0c;读者如果安装的是界面centos系统&#xff0c;或者使用过编译工具…...

【MYSQL锁】透彻地理解MYSQL锁

&#x1f525;作者主页&#xff1a;小林同学的学习笔录 &#x1f525;mysql专栏&#xff1a;小林同学的专栏 目录 1.锁 1.1 概述 1.2 全局锁 1.2.1 语法 1.2.1.1 加全局锁 1.2.1.2 数据备份 1.2.1.3 释放锁 1.2.1.4 特点 1.2.1.5 演示 1.3 表级锁 1.3.1 介绍 …...

【静态分析】静态分析笔记01 - Introduction

参考&#xff1a; BV1zE411s77Z [南京大学]-[软件分析]课程学习笔记(一)-introduction_南京大学软件分析笔记-CSDN博客 ------------------------------------------------------------------------------------------------------ 1. program language and static analysis…...

使用的sql

根据CODE去重 SELECT * FROM ( SELECT count( camera_code ) AS count, camera_code FROM n_camera_basic GROUP BY camera_code ) t WHERE t.count >1 DELETE FROM n_camera_basic WHERE camera_id NOT IN (SELECT dt.minno…...

【ZZULIOJ】1052: 数列求和4(Java)

目录 题目描述 输入 输出 样例输入 Copy 样例输出 Copy code 题目描述 输入n和a&#xff0c;求aaaaaa…aa…a(n个a)&#xff0c;如当n3,a2时&#xff0c;222222的结果为246 输入 包含两个整数&#xff0c;n和a,含义如上述&#xff0c;你可以假定n和a都是小于10的非负整…...

【Linux】tcpdump P3 - 过滤和组织返回信息

文章目录 基于TCP标志的过滤器格式化 -X/-A额外的详细选项按协议(udp/tcp)过滤低详细输出 -q时间戳选项 本文继续展示帮助你过滤和组织tcpdump返回信息的功能。 基于TCP标志的过滤器 可以根据各种TCP标志来过滤TCP流量。这里是一个基于tcp-ack标志进行过滤的例子。 # tcpdump…...

vscode免费登录ssh ,linux git配置免密码

1、vscode远程ssh免密 在windows下生成密钥 , cmd窗口下执行 ssh-keygen -t rsa 在C:\Users\xxxx\.ssh目录下生成 在linux下面 cd .ssh 创建authorized_keys 文件&#xff0c; 把之前windows下生成的 id_rsa.pub内容复制进去 2、gitlab 配置。 在linux下面 ssh-keygen -t rs…...

Netty 心跳(heartbeat)——服务源码剖析(上)(四十一)

剖析目的 Netty 作为一个网络框架&#xff0c;提供了诸多功能&#xff0c;比如编码解码等&#xff0c;Netty 还提供了非常重要的一个服务----心跳机制 heartbeat.通过心跳检査对方是否有效,这是 RPC 框架中是必不可少的功能。下面我们分析一下 Netty 内部心跳服务源码实现。 源…...

C语言—每日选择题—Day65

前言 我们的刷题专栏又又又开始了&#xff0c;本专栏总结了作者做题过程中的好题和易错题。每道题都会有相应解析和配图&#xff0c;一方面可以使作者加深理解&#xff0c;一方面可以给大家提供思路&#xff0c;希望大家多多支持哦&#xff5e; 第一题 1、如下代码输出的是什么…...

【环境变量】基本概念理解 | 查看环境变量echo | PATH的应用和修改

目录 前言 基本概念&理解 注意的点 查看环境变量的方法 PATH环境变量 PTAH应用系统指令 PTAH应用用户程序 命令行参数的修改&#xff08;内存级&#xff09; 配置文件的修改 windows环境变量 大家天天开心&#x1f642; bash进程的流程。环境变量在系统指…...

5.7Python之元组

元组&#xff08;Tuple&#xff09;是Python中的一种数据类型&#xff0c;它是一个有序的、不可变的序列。元组使用圆括号 () 来表示&#xff0c;其中的元素可以是任意类型&#xff0c;并且可以包含重复的元素。 与列表&#xff08;List&#xff09;不同&#xff0c;元组是不可…...

Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单视频处理实战案例 之一 简单视频放大抖动效果

Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单视频处理实战案例 之一 简单视频放大抖动效果 目录 Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单视频处理实战案例 之一 简单视频放大抖动效果 一、简单介绍 二、简单视频放大抖动效果实现原理 三、简单视频放大…...

如何通过VPN访问内网?

VPN&#xff08;Virtual Private Network&#xff09;是一种通过公共网络建立私有网络连接的技术&#xff0c;可以在不同地点的网络中建立安全通道&#xff0c;实现远程访问内网资源的目的。本文将介绍如何通过VPN访问内网&#xff0c;并介绍一款名为“天联”的VPN服务。 什么是…...

RabbitMQ3.13.0起支持MQTT5.0协议及MQTT5.0特性功能列表

RabbitMQ3.13.0起支持MQTT5.0协议及MQTT5.0特性功能列表 文章目录 RabbitMQ3.13.0起支持MQTT5.0协议及MQTT5.0特性功能列表1. MQTT概览2. MQTT 5.0 特性1. 特性概要2. Docker中安装RabbitMQ及启用MQTT5.0协议 3. MQTT 5.0 功能列表1. 消息过期1. 描述2. 举例3. 实现 2. 订阅标识…...

常用脚本01 - 生成证书

1 生成证书 第一步、准备脚本文件 [rootharbor-01 ssl]# vim gencert.sh #!/usr/bin/env bash set -eDOMAIN"$1" IP"$2" WORK_DIR"$(mktemp -d)"if [ -z "$DOMAIN" ]; thenecho "Domain name needed."exit 1 fiecho "…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...