03-使用一个不可变对象作为key,红黑树怎么比较大小?
使用一个不可变对象作为key,红黑树怎么比较大小?
答:Java 中的红黑树是通过左旋、右旋的方式来维护树的平衡性,而左旋、右旋又依赖于节点大小的比较。对于使用不可变对象作为key实际上是可以的,因为比较key的大小本身不依赖于key是否可变性,而是依赖于key实现的比较大小的方法。
作为红黑树中的key有如下几个条件
- key必须是对象,不能是基本数据类型(如 int、double等,对应的包装类是可以的);
- 作为key的该对象必须要实现Comparable接口,并重写
compareTo方法,用于比较对象的顺序。compareTo方法返回值是一个整数,如果当前对象小于参数对象,应返回负整数;如果当前对象大于参数对象,应返回正整数;如果两个对象相等,应返回0。
使用红黑树实现排序的案例
import java.util.Comparator;
import java.util.TreeSet;class Person implements Comparable<Person> {private final String name;private final int age;public Person(String name, int age) {this.name = name;this.age = age;}public String getName() {return name;}public int getAge() {return age;}@Overridepublic int compareTo(Person other) {// 先按照姓名比较int nameComparison = this.name.compareTo(other.name);if (nameComparison != 0) {return nameComparison;}// 若姓名相同,则按照年龄比较return Integer.compare(this.age, other.age);}
}public class RedBlackTreeExample {public static void main(String[] args) {// 创建红黑树,并添加元素TreeSet<Person> treeSet = new TreeSet<>();treeSet.add(new Person("Alice", 25));treeSet.add(new Person("Bob", 30));treeSet.add(new Person("Charlie", 20));treeSet.add(new Person("Alice", 30));// 遍历红黑树for (Person person : treeSet) {System.out.println(person.getName() + ", " + person.getAge());}}
}
知识扩展:
(1)红黑树的插入和查找操作是如何利用键的比较结果来维护树的有序性的?
红黑树通过键的比较结果来维护树的有序性。在插入和查找操作中,红黑树根据键的比较结果来确定节点的位置,以保持树的有序性。
插入操作:
- 从根节点开始,将要插入的节点与当前节点进行键的比较。如果要插入的节点的键小于当前节点的键,则继续在当前节点的左子树中继续比较;如果要插入的节点的键大于当前节点的键,则继续在当前节点的右子树中继续比较。
- 重复上述步骤,直到找到一个空位置,将要插入的节点放入该位置。
- 插入节点后,通过旋转和重新着色操作,确保红黑树的性质得到恢复和维护。这些操作旨在保持红黑树的平衡性和有序性。
查询操作:
- 从根节点开始,将要查找的键与当前节点进行比较。如果要查找的键等于当前节点的键,则返回当前节点。
- 如果要查找的键小于当前节点的键,则继续在当前节点的左子树中继续比较。
- 如果要查找的键大于当前节点的键,则继续在当前节点的右子树中继续比较。
- 重复上述步骤,直到找到等于要查找键的节点或者遍历到叶子节点为止。如果遍历到叶子节点仍未找到匹配的节点,则表示键不存在于红黑树中。
相关文章:
03-使用一个不可变对象作为key,红黑树怎么比较大小?
使用一个不可变对象作为key,红黑树怎么比较大小? 答:Java 中的红黑树是通过左旋、右旋的方式来维护树的平衡性,而左旋、右旋又依赖于节点大小的比较。对于使用不可变对象作为key实际上是可以的,因为比较key的大小本身…...
2021江苏省赛热身赛 C Magic Rabbit(数形结合)
2021江苏省赛热身赛 C Magic Rabbit(数形结合) Magic Rabbit 非常好且巧妙地一道题。 大意:给出三种溶液 , 三种溶液分别含有不同浓度的 x ,y 两种物质。 溶液x (mg/ml)y (mg/ml)溶液1x1y1溶液2x2y2溶液3x3y3 给出 Q 组询问 ,…...
AES加密(2):AES代码实现解析
在我的上一篇文章AES基础知识和计算过程中,大概介绍了AES(Rijndael)加密的整个过程。那么在这一篇文章中,就来看一下AES在代码中是如何实现的,也有助于我们理解其中的一些细节。 本篇文章所用的AES代码来源于Szymon Stefanek的开源C代码 文章…...
SpringBoot项目通过分词器生成词云
目录 前言一、词云是什么?二、使用步骤1.引入依赖2.application.yml3.Controller4.分词工具类4.词云生成工具类、支持输出文件和字节流 注意 前言 公司项目涉及到员工任务管理,需要从员工任务中获取任务信息生成个人词云图,可以把员工任务中…...
Nacos 配置管理及相关使用
文章目录 Nacos 配置管理一、统一配置管理1、在Nacos 中添加配置文件2、从微服务拉取配置3、配置实现步骤(1)引入 nacos-config 依赖(2)添加 bootstrap.yml(4)在 nacos 中添加配置 二、配置热更新1、配置热…...
重发布与路由策略
华子目录 重发布重发布条件重发布配置规则重发布名词配置命令ospf往rip重发布(重发布动态)静态往rip重发布(重发布静态)直连往rip重发布(重发布直连)rip往ospf重发布(重发布动态)静态…...
57. 插入区间(C++题解)
57. 插入区间 插入区间 给你一个无重叠的 ,按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。 示例 1: 输入&#x…...
【数据结构Java版】 初识泛型和包装类
目录 1.包装类 1.1基本数据类型以及它们所对应的包装类 1.2装箱和拆箱 1.3自动装箱和自动拆箱 2.什么是泛型 3.引出泛型 4.泛型类的使用 4.1语法 4.2示例 4.3类型推导 5.泛型是如何编译的 5.1擦除机制 5.2正确的写法 6.泛型的上届 6.1语法 6.2示例 …...
Spring中如何解决循环依赖问题的三种方法
什么是循环依赖问题 在 Spring 中,循环依赖问题指的是两个或多个 bean 之间相互依赖形成的闭环。具体而言,当 bean A 依赖于 bean B,同时 bean B 也依赖于 bean A,就形成了循环依赖。 循环依赖问题在 Spring 容器中是一个非常常…...
【ArcGIS Pro二次开发】(65):进出平衡SHP转TXT、TXT转SHP
最近一个小伙伴提了这么一个需求,需要把TXT和SHP进行互转。 这种TXT文件其实遇到了好几个版本,都有一点小差异。之前已经做过一个TXT转SHP的工具,但好像不适用。于是针对这个版本,做了互转的2个工具。 【SHP转TXT】 一、要实现的…...
Shell开发实践:服务器的磁盘、CPU、内存的占用监控
🏆作者简介,黑夜开发者,CSDN领军人物,全栈领域优质创作者✌,CSDN博客专家,阿里云社区专家博主,2023年6月CSDN上海赛道top4。 🏆数年电商行业从业经验,历任核心研发工程师…...
超详细 async和await 项目实战运用(附加文字解答+源码)
文章目录 问题描述async什么是 asyncasync 的作用async 的应用场景async 优点 await什么是 awaitawait 的作用await 的应用场景await 的优点async和 await结合使用 结束语 大家好!又到了愉快的周末假期,今天是2023年9月3日|农历七月十九,我最…...
Maven入门教程(三):Maven语法
视频教程:Maven保姆级教程 Maven入门教程(一):安装Maven环境 Maven入门教程(二):idea/Eclipse使用Maven Maven入门教程(三):Maven语法 Maven入门教程(四):Nexus私服 Maven入门教程(五):自定义脚手架 6.Mav…...
C++技术点,故事解析
语言的魅力 从人类诞生开始 ,南方古猿到现代人类经历了非常多变化; 南方古猿到能人 有什么变化? 能人会使用工具,由于会使用工具 就可以获得肉类食物,当然只能吃一些动物腐肉 直到进化成直立人的晚期,在东…...
数据结构(Java实现)-字符串常量池与通配符
字符串常量池 在Java程序中,类似于:1, 2, 3,3.14,“hello”等字面类型的常量经常频繁使用,为了使程序的运行速度更快、更节省内存,Java为8种基本数据类型和String类都提供了常量池。…...
python强化学习--gym安装与使用
最近开始学习强化学习,第一步肯定是要学会安装和使用pym,原本以为很简单,事实上确实很简单,但是遇到一个小问题,就是安装gym之后,在应用的过程中,游戏界面没有显示出来,了解后才知道…...
105. 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。 思路:题目给出了先序遍历和中序遍历的结果,因为先序遍历遵循根–>左–>…...
(第六天)初识Spring框架-SSM框架的学习与应用(Spring + Spring MVC + MyBatis)-Java EE企业级应用开发学习记录
SSM框架的学习与应用(Spring Spring MVC MyBatis)-Java EE企业级应用开发学习记录(第六天)初识Spring框架 昨天我们已经把Mybatis框架的基本知识全部学完,内容有Mybatis是一个半自动化的持久层ORM框架,深入学习编写动态SQL&a…...
如何使用『Nginx』配置后端『HTTPS』协议访问
前言 本篇博客主要讲解如何使用 Nginx 部署后端应用接口 SSL 证书,从而实现 HTTPS 协议访问接口(本文使用公网 IP 部署,读者可以自行替换为域名) 申请证书 须知 请在您的云服务平台申请 SSL 证书,一般来说证书期限…...
Git仓库简介
1、工作区、暂存区、仓库 工作区:电脑里能看到的目录。 暂存区:工作区有一个隐藏目录.git,是Git的版本库,Git的版本库里存了很多东西,其中最重要的就是称为stage(或者叫index)的暂存区…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...
Chrome 浏览器前端与客户端双向通信实战
Chrome 前端(即页面 JS / Web UI)与客户端(C 后端)的交互机制,是 Chromium 架构中非常核心的一环。下面我将按常见场景,从通道、流程、技术栈几个角度做一套完整的分析,特别适合你这种在分析和改…...
Android写一个捕获全局异常的工具类
项目开发和实际运行过程中难免会遇到异常发生,系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler,它是Thread的子类(就是package java.lang;里线程的Thread)。本文将利用它将设备信息、报错信息以及错误的发生时间都…...
一些实用的chrome扩展0x01
简介 浏览器扩展程序有助于自动化任务、查找隐藏的漏洞、隐藏自身痕迹。以下列出了一些必备扩展程序,无论是测试应用程序、搜寻漏洞还是收集情报,它们都能提升工作流程。 FoxyProxy 代理管理工具,此扩展简化了使用代理(如 Burp…...
