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

二叉搜索树的详解及Map和Set的介绍

目录

1.二叉搜索树

1.1二叉搜索树的介绍

1.2.二叉搜索树的实现

1.2.1二叉搜索树的创建

1.2.2查找关键字

 1.2.3插入

 1.2.4删除

          1.3二叉搜索树的性能分析

2.Map

         Map官方文档

 2.1Map 的常用方法说明

2.2关于Map.Entry的说明,>

 2.3注意事项

2.4reeMap和HashMap的区别 

3.Set

3.1常见方法说明

 3.2注意事项

3.3TreeSet和HashSet的区别 


1.二叉搜索树

1.1二叉搜索树的介绍

二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树 :
(1)若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
(2)若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
(3)它的左右子树也分别为二叉搜索树

比如以下:

int[] array ={5,3,4,1,7,8,2,6,0,9};

1.2.二叉搜索树的实现

1.2.1二叉搜索树的创建
public class BinarySearchTree {class TreeNode {public int val ;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val = val;}}public TreeNode root;//根节点
}
1.2.2查找关键字

步骤:

若根节点不为空:

  • 如果根节点key==查找key,返回true
  • 如果根节点key > 查找key,在其左子树查找
  • 如果根节点key < 查找key,在其右子树查找

找不到,返回false

代码:

   public boolean search(int key) {TreeNode cur = root;while (cur != null) {if (cur.val ==key){return true;} else if (cur.val>key) {cur=cur.left;}else{cur=cur.right;}}return false;}
 1.2.3插入

插入操作可以分为以下两种情况:

(1)如果树为空树,即根 == null,直接插入

(2)如果树不是空树,按照查找逻辑确定插入位置,插入新结点

那怎么找合适位置呢?

  • 如果节点root.val==val,该值在搜索数中已经存在,无需插入,return flase;
  • 如果节点root.val>val,在其左子树找合适位置
  • 如果节点root.val<val,在其右子树找合适位置

代码:

    public boolean insert(int val) {TreeNode treeNode = new TreeNode(val);if (root == null) {root=treeNode;return true;}TreeNode cur=root;TreeNode parent = null;while(cur!=null){if (cur.val == val) {return false;} else if (cur.val > val) {parent=cur;cur = cur.left;} else {parent=cur;cur = cur.right;}}if(parent.val>val){parent.left=treeNode;}else {parent.right=treeNode;}return true;}
 1.2.4删除
设待删除结点为 cur, 待删除结点的双亲结点为 parent
1. cur.left == null
(1) cur root ,则 root = cur.right
         

(2) cur 不是 rootcur parent.left,则 parent.left = cur.right

(3) cur 不是 rootcur parent.right,则 parent.right = cur.right

2. cur.right == null
(1) cur root ,则 root = cur.left
(2) cur 不是 root cur parent.left ,则 parent.left = cur.left
(3) cur 不是 root cur parent.right ,则 parent.right = cur.left
这里与1. cur.left == null大同小异不做过多解释
3. cur.left != null && cur.right != null
步骤:

我们使用target来遍历寻找子树中关键节点,targetParent用来记录target的父亲节点

找到相应节点后与待删除的cur节点的值进行替换,最后删除target结点即可

 例子:

代码:

    public void remove(int val) {TreeNode cur = root;TreeNode parent = null;while (cur != null) {if (val == cur.val) {removeNode(parent, cur);break;} else if (val < cur.val) {parent = cur;cur = cur.left;} else {parent = cur;cur = cur.right;}}}private void removeNode(TreeNode parent, TreeNode cur) {if (cur.left==null){if(cur==root){root=cur.right;}else if(parent.left==cur){parent.left=cur.right;}else{parent.right=cur.right;}} else if (cur.right==null) {if(cur==root){root=cur.left;}else if(parent.left==cur){parent.left=cur.left;}else{parent.right=cur.left;}}else{TreeNode target = cur.right;TreeNode targetParent = cur;while(target.left!=null){targetParent = target;target = target.left;}if(targetParent.left==target){targetParent.left=target.right;}else{targetParent.right=target.right;}}}

 1.3二叉搜索树的性能分析

插入和删除操作都必须先查找,查找效率代表了二叉搜索树中各个操作的性能。
对有 n 个结点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是结点在二叉搜索树的深度 的函数,即结点越深,则比较次数越多。
但对于同一个关键码集合,如果各关键码插入的次序不同,可能得到不同结构的二叉搜索树:

 但对于同一个关键码集合,如果各关键码插入的次序不同,可能得到不同结构的二叉搜索树:

 


2.Map

Map官方文档

Map 是一个接口类,该类没有继承自 Collection ,该类中存储的是 <K,V> 结构的键值对,并且 K 一定是唯一的,不 能重复

 

 2.1Map 的常用方法说明

 举例部分方法:

public class TestMap {public static void main(String[] args) {Map<String,Integer> map=new TreeMap<>();map.put("wang",1);map.put("zhang",3);map.put("li",5);System.out.println(map);//{li=5, wang=1, zhang=3}// GetOrDefault(): 如果key存在,返回与key所对应的value,如果key不存在,返回一个默认值System.out.println(map.getOrDefault("wang",0));//1System.out.println(map.getOrDefault("abcdef",0));//0// 返回所有 key 的不重复集合Set keys=map.keySet();System.out.println(keys);//[li, wang, zhang]//返回所有 value 的可重复集合Collection vals=  map.values();System.out.println(vals);//[5, 1, 3]// 打印所有的键值对// entrySet(): 将Map中的键值对放在Set中返回了for(Map.Entry<String, Integer> entry : map.entrySet()){System.out.println(entry.getKey() + "--->" + entry.getValue());}//li--->5//wang--->1//zhang--->3}}

2.2关于Map.Entry<K, V>的说明

Map.Entry<K, V> Map 内部实现的用来存放 <key, value> 键值对映射关系的内部类 ,该内部类中主要提供了 <key, value>的获取, value 的设置以及 Key 的比较方式。

注意:Map.Entry<K,V>并没有提供设置Key的方法

 2.3注意事项

1. Map 是一个接口,不能直接实例化对象 ,如果 要实例化对象只能实例化其实现类 TreeMap 或者 HashMap
2. Map 中存放键值对的 Key 是唯一的, value 是可以重复的
3. TreeMap 中插入键值对时, key 不能为空,否则就会抛 NullPointerException 异常 value 可以为空。但 是HashMap key value 都可以为空。
4. Map 中的 Key 可以全部分离出来,存储到 Set 来进行访问 ( 因为 Key 不能重复 )
5. Map 中的 value 可以全部分离出来,存储在 Collection 的任何一个子集合中 (value 可能有重复 )
6. Map 中键值对的 Key 不能直接修改, value 可以修改,如果要修改 key ,只能先将该 key 删除掉,然后再来进行 重新插入。

2.4reeMap和HashMap的区别 


3.Set

Set官方文档

SetMap主要的不同有两点:Set是继承自Collection的接口类Set中只存储了Key

set的底层是map

3.1常见方法说明

举例部分方法:

public class TextSet {public static void main(String[] args) {Set<String> set=new TreeSet<>();// add(key): 如果key不存在,则插入,返回ture// 如果key存在,返回falseset.add("wang");set.add("hang");set.add("li");Iterator<String> it=set.iterator();while(it.hasNext()){System.out.println(it.next());}//hang//li//wang}
}

 3.2注意事项

1. Set 是继承自 Collection 的一个接口类
2. Set 中只存储了 key ,并且要求 key 一定要唯一
3. TreeSet 的底层是使用 Map 来实现的,其使用 key Object 的一个默认对象作为键值对插入到 Map 中的
4. Set 最大的功能就是对集合中的元素进行去重
5. 实现 Set 接口的常用类有 TreeSet HashSet ,还有一个 LinkedHashSet LinkedHashSet 是在 HashSet 的基础 上维护了一个双向链表来记录元素的插入次序。
6. Set 中的 Key 不能修改,如果要修改,先将原来的删除掉,然后再重新插入
7. TreeSet 中不能插入 null key HashSet 可以。

3.3TreeSetHashSet的区别 


以上为我个人的小分享,如有问题,欢迎讨论!!! 

都看到这了,不如关注一下,给个免费的赞 

相关文章:

二叉搜索树的详解及Map和Set的介绍

目录 1.二叉搜索树 1.1二叉搜索树的介绍 1.2.二叉搜索树的实现 1.2.1二叉搜索树的创建 1.2.2查找关键字 1.2.3插入 1.2.4删除 1.3二叉搜索树的性能分析 2.Map Map官方文档 2.1Map 的常用方法说明 2.2关于Map.Entry的说明,> 2.3注意事项 2.4reeMap和HashMap的区别 …...

【Android知识笔记】JNI专题

一、JNI 基础知识 JNI 的数据类型以及和Java层之间的数据转换 前面总结了一篇,这里不再展开,可以参考: JNI 的数据类型以及和Java层之间的数据转换 注:这些知识都收集自网络文章,比较零散,对于JNI基础来说应该够用了。主要是一些API的使用,记不住时当成手册来查询一下…...

C++面试题目汇总【持续更新】

面试题目汇总 C基础1. 面向对象是什么&#xff1f;[GPT]2. 面向对象的三大特征是什么&#xff1f;[GPT]3. 重载&#xff0c;重写&#xff0c;隐藏的区别&#xff1f;[GPT]4. 构造函数的类别有哪些&#xff1f;[GPT]5. 定义一个空类时&#xff0c;默认生成哪些函数&#xff1f;[…...

【PXIE301-211】青翼科技基于PXIE总线的16路并行LVDS数据采集、1路光纤数据收发处理平台

板卡概述 PXIE301-211是一款基于PXIE总线架构的16路并行LVDS数据采集、1路光纤收发处理平台&#xff0c;该板卡采用Xilinx的高性能Kintex 7系列FPGA XC7K325T作为实时处理器&#xff0c;实现各个接口之间的互联。板载1组64位的DDR3 SDRAM用作数据缓存。板卡具有1个FMC&#xf…...

WPF实现签名拍照功能

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

基于RuoYi-Flowable-Plus的若依ruoyi-nbcio支持自定义业务表单流程的集成方法与步骤(二)

更多ruoyi-nbcio功能请看演示系统 gitee源代码地址 前后端代码&#xff1a; https://gitee.com/nbacheng/ruoyi-nbcio 演示地址&#xff1a;RuoYi-Nbcio后台管理系统 前面讲了集成的后端部分内容&#xff0c;下面简单介绍一下前端的内容 1、前端生成的页面需要进行修改&…...

【Qt控件之微调框、进度条】QSpinBox、QDoubleSpinBox、QDial、QProgressBar介绍及使用

概述 QSpinBox类提供了一个微调框小部件。 QSpinBox适用于处理整数和离散的值集&#xff08;例如&#xff0c;月份名称&#xff09;&#xff1b;对于浮点数值&#xff0c;请使用QDoubleSpinBox。 QSpinBox允许用户通过点击上下按钮或按键盘上的上下箭头来增加/减少当前显示的值…...

Python学习-----Day09

一、利用装饰器来获取函数运行的时间、 #导入time模块 import timedef decorated(fn):def inner():#time.time获取函数执行的时间a time.time() # func开始的时间fn()b time.time() # func结束的时间print(f"{fn.__name__}程序运行的总数时间:{b - a}秒")return…...

世界国家/地区行驶方向数据

Part1数据背景 道路通行方向规则是交通规则的重要部分之一。不同国家及地区通行方向并不一样&#xff0c;受风俗、习惯、风潮因素等影响。 最近也在学道路行驶&#xff0c;结果差强人意&#xff0c;继续努力吧。祝学车的小伙伴们一次过~ Part2数据详情 今天分享的国家/地区行…...

idgen导入Android11源码

文章目录 配置下载AS编译源码依赖导入玩一下andorid.iml 注意&#xff1a; 有些时候发现为啥自己编译就这么难呢&#xff1f;不是卡死就无数次重启虚拟机&#xff0c;一切的原罪在配置过低&#xff0c;换句话说就是穷。关于导入源码的下载参考 Android Studio for Platform (AS…...

大同小异!如何在苹果不同类型设备上更改AirDrop的名称

你可以更改你的AirDrop ID&#xff0c;让其他人看到你名字之外的东西。本文介绍了如何在iPhone、iPad和Mac上更改AirDrop名称。 如何在iPhone上更改AirDrop名称 在iPhone上更改AirDrop名称涉及到你可能不想做的更改。幸运的是&#xff0c;这在iPad和Mac上不是真的&#xff0c…...

sqlmap --os-shell选项原理解析

文章目录 sqlmap --os-shell选项原理解析原理解析总结 sqlmap --os-shell选项原理解析 以sqli第一关为例。 --os-shell 是 SQLMap 工具的一个参数&#xff0c;用于在成功注入数据库后&#xff0c;执行操作系统命令并获取其输出。 sqlmap -u "http://192.168.188.199/sq…...

谈谈 Redis 持久化机制,RDB、AOF

谈谈 Redis 持久化机制&#xff0c;RDB&#xff0c;AOF RDB&#xff1a;相当于对内存中的数据&#xff0c;拍一张数据快照。存储的是数据。 AOF&#xff1a;存储的是具体的命令。 企业实践中&#xff0c;实际是使用RDB结合AOF。 这个方法是在 Redis 4.0 提出的&#xff0c;该方…...

并发编程——2.基础概念及其它相关的概述

这篇文章我们来讲一下并发编程中的线程及其相关的概述内容。 目录 1.J.U.C 2.进程、线程、协程 2.1进程 2.2线程 2.3纤程&#xff08;协程&#xff09; 2.4概念小结 3.并发、并行、串行 3.1并发 3.2并行 3.3串行 3.4概念小结 4.CPU核心数和线程数的关系 5.上下文…...

20231019 filezilla 配置 Windows与Ubuntu文件传输

SFTP协议&#xff0c;传文件&#xff0c;否则会报无权限错...

一个.Net开发的轻量级SQLite数据库ORM

SQLite是一种流行的开源关系型数据库&#xff0c;它的设计目标是提供轻量级、高效、可靠和易用的数据存储服务。由于SQLite无需单独的服务器进程&#xff0c;它通常被用于嵌入式系统和单机应用程序中&#xff0c;也可以用于网络应用程序的辅助数据库。 今天给大家推荐一个.NET开…...

gRPC通信

1. gRPC简介 gRPC是一种高性能、开源和通用的远程过程调用&#xff08;RPC&#xff09;框架&#xff0c;由Google开源并维护。它使用Protocol Buffers&#xff08;protobuf&#xff09;作为接口定义语言&#xff08;IDL&#xff09;&#xff0c;提供跨平台、跨语言的RPC调用支…...

湖仓一体架构的特性

湖仓一体架构是一种数据架构模式&#xff0c;具有以下特性&#xff1a; 统一存储&#xff1a;湖仓一体架构将数据湖和数据仓库合并为一个整体&#xff0c;将结构化数据和非结构化数据存储在同一个存储系统中&#xff0c;如Hadoop分布式文件系统&#xff08;HDFS&#xff09;或云…...

Python中使用包含_和__的变量名之间的区别

_:单下划线 例子&#xff1a;_count、_temp 含义&#xff1a;成员的私有成员变量&#xff0c;就像Java中用private关键字修饰一样。 作用&#xff1a;只允许当前类创建的对象和子类对象访问此变量。外部无法访问此变量。 __:双下划线 例子&#xff1a;__count、__temp 含义&am…...

019-第三代软件开发-Git提交规范

第三代软件开发-Git提交规范 文章目录 第三代软件开发-Git提交规范项目介绍Git提交规范分支规范Commit Message FormatHeaderBodyFooterRevert 总结一下 关键字&#xff1a; Qt、 Qml、 git、 Commit、 release 项目介绍 欢迎来到我们的 QML & C 项目&#xff01;这个…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

逻辑回归暴力训练预测金融欺诈

简述 「使用逻辑回归暴力预测金融欺诈&#xff0c;并不断增加特征维度持续测试」的做法&#xff0c;体现了一种逐步建模与迭代验证的实验思路&#xff0c;在金融欺诈检测中非常有价值&#xff0c;本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...