Tree搜索二叉树、map和set_数据结构

数据结构专栏
如烟花般绚烂却又稍纵即逝的个人主页
本章讲述数据结构中搜索二叉树与HashMap的学习,感谢大家的支持!欢迎大家踊跃评论,感谢大佬们的支持!
在这里插入图片描述

目录

  • 搜索二叉树的概念
    • 二叉树搜索模拟实现
        • 搜索二叉树查找
        • 搜索二叉树插入
        • 搜索二叉树删除
  • HashMap 和HashSet的定义
    • hashCode(开散链法)
    • 哈希冲突
        • 模拟实现哈希桶(尾叉法)
        • 模拟创建泛型哈希桶

搜索二叉树的概念

二叉树左边的值小与根节点,右边的值大于根节点。
左树<根节点<右树
这样也大大提升了我们代码搜索的效率
这时通过中序遍历得到一个有序的数组。
在这里插入图片描述

二叉树搜索模拟实现

搜索二叉树查找

给一个值来判断数组中是否包含这个元素。
思想:1.节点不能为空,为空说明没有元素
2.明确左边的数都比跟节点要小,而右边的树比跟节点大,小往左走,大往右走,搜索到返回true,出了条件返回false(没有搜索到此元素)。
在这里插入图片描述

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

时间复杂度:最好情况下O(logN)
最坏情况下O(N)——在单分枝的情况下

搜索二叉树插入

如果要插入数据的情况下,插入的数据大于根节点一直走,如果小于根节点则插入左树,如果一直大于则直到为空插入,因为遍历的cur为空出来后没有最后一个节点的位置,在插入之前需要定义一个parent来记录根节点的,来放到左树或者右树。
在这里插入图片描述

  public boolean insert(int val){if(this.root==null){//root为空情况下this.root=new TreeNode(val);return true;}TreeNode cur=this.root;//定义一个值来接收前一个父亲节点值TreeNode parent=null;while(cur!=null){parent=cur;if(cur.val>val){parent=cur;cur=cur.left;} else if (cur.val< val) {parent=cur;cur=cur.right;}else{//不需两个相同元素存在return false;}}TreeNode node=new TreeNode(val);if(parent.val>val){//插入左边parent.left=node;}else{parent.right=node;}return true;}
搜索二叉树删除

当我们要删除树中某一个节点的时候我们要考虑的情况比较多当left为空节点.
这里分三种情况讨论
第一种情况:
1.如果想要删除的节点为root,且左树为空情况下,则直接指向right。
因为parent事cur的上一个节点的记录
2.如果parent的左树为cur且cur的左树为空,则parent.left=cur.right。
3.如果parent的右树是cur且cur的左树为空,则parent.right=cur.right。

在这里插入图片描述

第二种情况:
1当cur==root时且没有右树,则左树为新的根节点。
2.parent指向的左树为cur时,因为cur没有右树则parent.left=cur.left。
3.parent指向的右树为cur时,因cur没有右树则parent.right=cur.left。

在这里插入图片描述

第三种情况:要删除的cur的左右子树都不为空。
如果都不为空,需要找到比左树大,但是比右树要小的值。
如果cur的下一个右树节点的左树存在最小值则直接将其cur覆盖。或者cur的右树没有左树节点,则右树第一个节点覆盖掉cur。

cur的左右树都不为空,则cur是比左树要到,所以不需要考虑cur的左树部分。
定义两个值来标记targetParent和target的右树,从右树的左侧找到最小值,进行覆盖(curParent来作为上一个的父亲节点),这时候要删除target节点,当targetParent的左树为target时,因为target一定是在最后一个左树位置,target的右树赋值给targetParent来取消与target的连接。
如果target为右树则targetParent直接指向target的下一个右树。

  public void  removeThisNode(TreeNode cur,TreeNode parent){if(cur.left==null){//如果cur根节点为要删除的节点,直接将root指向cur.rightif(cur==this.root){this.root=cur.right;} else if (cur==parent.left) {parent.left=cur.right;}else{parent.right=cur.right;}} else if (cur.right==null) {if(cur==root){this.root=cur.left;} else if (cur==parent.left) {parent.left=cur.left;}else{parent.right=cur.left;}}else{TreeNode targetParent=cur;TreeNode target=cur.right;while(target.left!=null){targetParent=target;target=target.left;}//cur的值被target覆盖掉cur.val=target.val;//这里target的指向修改if(targetParent.left==target){targetParent.left=target.right;}else{targetParent.right=target.right;}}}

时间复杂度O(logN)

HashMap 和HashSet的定义

HashSet是java集合框架中Set的常用类。
HashSet不允许存储重复元素的集合,它使用哈希表来存储元素(val),确保每一个元素是唯一的,时间复杂度为O(1).

HashMap是java集合框架Map的常用类。
HashMap也是用哈希表通过key键值来存储val,与HashMap不同,它通过key键值来存储,元素可以相同,但是key键值一单相同val值就会被覆盖掉。

hashCode(开散链法)

二叉搜索树是通过对半切的方式进行比较,类似于我们的二分法查找,但是它的如果是两边的树是平衡时,时间复杂度是O(logN),如果是一棵单分枝树时间复杂度来到O(N)都要进行遍历。

而哈希可以不经过比较,一次性从想要查找的范围内获取到该元素。
如果想要实现,通过哈希函数使元素的存储位置与它的关键码之间能够建立一一映射的关系,通过公式:hash=key(查找的下标)%capacity(容量)如下图所示:

5%10=5将19到5下标
13%10=3将24放到3下标
15%10=5将52放到5下标的链表的next处
在这里插入图片描述

哈希冲突

而通过上述我们发现,5,15都已经放到了5下标位置,不同关键字通过相同的哈希函数计算出相同的哈希地址
如何避免哈希冲突?
哈希冲突无法直接避免,因为key我们的元素是不能改变的,我们只能控制空间的大小,来减少链表中元素
负载因子 = 表中有效数据个数 / 空间的大小。
>负载因子越大,产出冲突的概率越高,增删查改的效率越低。
负载因子越小,产出冲突的概率越低,增删查改的效率越高

负载因子设定为0.75
当我们的元素个数/空间的长度如果超出0.75,则需要扩容,加大空间,将负载因子缩小,从而让查改效率加强。
在这里插入图片描述

模拟实现哈希桶(尾叉法)

1.这里我们创建一个哈希表来进行搜索,通过数组和链表的方式来构成,让其更快搜索到想要搜索到的值,将下标值放入指定的数组链表中来存储。
2.每个数组的下标对应一个链表,当想要搜索某个下标值时,hash=key%capacity 得到的就是某一下标的链表,通过链表连接该key的每一个元素。
3.判断是否需要大于负载因子(扩容 )
当我们扩容时,通过2*len的长度进行扩容,然后通过key%新定义的数组的容量,给到新的数组链表中,将之前存储的链表指向其他下一个节点即可。
在这里插入图片描述

public class HashBucket {
//内部类static class Node{public int key;public int val;public Node next;//内部类构造方法public Node(int key, int val) {this.key = key;this.val = val;}}//申请一个数组public Node[] array;int size;//长度public static final float loadFactor=0.75f;//负载因子的默认值public HashBucket(){//构造方法this.array=new Node[10];}//放入元素public void put(int key,int val){int index=key%array.length;Node node=new Node(key,val);Node preV=null;//为空if(this.array[index]==null){this.array[index]=node;}else{//不为空Node cur=this.array[index];while(cur!=null){if(cur.key==key){cur.val=val;return;}preV=cur;cur=cur.next;}assert preV!=null;preV.next=node;}size++;if(judgThisLoadFactorFull())//扩容grow();}//判断是否大于负载因子public boolean judgThisLoadFactorFull(){return size*1.0f/array.length>loadFactor;}//扩容private void grow() {Node[] newArray=new Node[2*array.length];//两倍的扩容for(int i=0;i<array.length;i++){Node cur=this.array[i];Node preV=null;while(cur!=null){int index= cur.key%newArray.length;if(newArray[index]==null){newArray[index]=cur;cur=cur.next;this.array[i]=cur;newArray[index].next=null;}else{Node newCur=newArray[index];while(newCur!=null){preV=newCur;newCur=newCur.next;}assert preV!=null;preV.next=cur;cur=cur.next;this.array[i]=cur;preV.next.next=null;}}}this.array=newArray;}//通过key搜索到值public int getValByThisKey(int key){int index=key%this.array.length;Node cur=this.array[index];while (cur!=null){if(cur.key==key){return cur.val;}cur=cur.next;}return -1;}

当我们创建了一个泛型的类型后,生成了hashCode方法,我们生成两个参数相同的对象时,如果将student1放入到hashmap中,当我们想要查找hashmap1中的值时,使用student2也可以查到student1中的值,这里的哈希函数通过计算关键码,因为两者的关键码相同,得到关键码的数值。

 Student student1=new Student("12313");Student student2=new Student("12313");System.out.println(student1.hashCode());System.out.println(student2.hashCode());HashMap<Student,Integer> hashMap=new HashMap<>();hashMap.put(student1,2);System.out.println(hashMap.get(student2));

在这里插入图片描述
而我们如何自己模拟实现一个自定义类型的哈希桶呢?
接下来我们实现以下

模拟创建泛型哈希桶

这里泛类型哈希桶实现与上述哈希桶实现类似,但是这里注意get方法中的比较关键码是通过equals来判断

public class HashBucket<K,V>{static class Node<K,V>{public K key;public V val;public Node<K,V> next;public Node(K key, V val) {this.key = key;this.val = val;}}public Node<K,V>[] array;public int usedSize;public static final float DefaultFactor=0.75f;public HashBucket(){this.array=(Node<K, V>[]) new Node[10];}//放入值public void put(K key,V val){int hash=key.hashCode();int index=hash%array.length;Node<K,V> cur=array[index];Node<K,V> node=new Node<>(key,val);Node<K,V> preV=null;if(cur==null){this.array[index]=node;}else{while(cur!=null){if(cur.key==key){cur.val=val;}preV=cur;cur=cur.next;}preV.next=node;}usedSize++;}//获取值public V get(K key){int hash= key.hashCode();int index=hash % array.length;Node<K,V> cur=this.array[index];while(cur!=null){//这里比较不是==if(cur.key.equals(key)){return cur.val;}cur=cur.next;}return null;}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C#使用ExcelDataReader读取Xlsx文件为DataTable对象

创建控制台项目 在NuGet中安装ExcelDataReader.DataSet 3.7.0 创建一个xlsx文件 测试代码 读取xlsx文件内容&#xff0c;为一个DataTable对象。 读取xlsx时&#xff0c;xlsx文件不能被其他软件打开&#xff0c;否则会报“进程无法访问此文件”的错。 using ExcelDataRead…

【JavaEE初阶】应是天仙狂醉,乱把白云揉碎 - (重点)线程

本篇博客给大家带来的是线程的知识点, 由于内容较多分几天来写. &#x1f40e;文章专栏: JavaEE初阶 &#x1f680;若有问题 评论区见 ⭐欢迎大家点赞 评论 收藏 分享 ❤❤❤ 如果你不知道分享给谁,那就分享给薯条. 你们的支持是我不断创作的动力 . 1. 认识线程 1.1 概念 )1 …

精准用户获取与私域流量运营:多商户链动 2+1 模式商城小程序的赋能策略

摘要&#xff1a;本文聚焦于精准用户对商业运营的核心价值&#xff0c;深入剖析获取精准用户的有效途径&#xff0c;特别围绕目标用户画像及出没场景展开分析。同时&#xff0c;探讨在私域流量构建进程中&#xff0c;多商户链动 21 模式商城小程序如何融入精准用户运营体系&…

Spring Boot教程之十一:获取Request 请求 和 Put请求

如何在 Spring Boot 中获取Request Body&#xff1f; Java 语言是所有编程语言中最流行的语言之一。使用 Java 编程语言有几个优点&#xff0c;无论是出于安全目的还是构建大型分发项目。使用 Java 的优点之一是 Java 试图借助类、继承、多态等概念将语言中的每个概念与现实世…

DVWA靶场文件包含(File Inclusion)通关教程(high级别)

目录 DVWA 靶场建立闯关 DVWA 靶场建立 需要的东西&#xff1a; phpStudy&#xff1a; 链接&#xff1a; phpStudy 提取码&#xff1a;0278 DVWA-master 链接&#xff1a; DVWA靶场 提取码&#xff1a;0278 建议在虚拟机中操作&#xff0c;以防数据库冲突&#xff0c;下面有…

基于yolov8、yolov5的铝材缺陷检测识别系统(含UI界面、训练好的模型、Python代码、数据集)

摘要&#xff1a;铝材缺陷检测在现代工业生产和质量管理中具有重要意义&#xff0c;不仅能帮助企业实时监控铝材质量&#xff0c;还为智能化生产系统提供了可靠的数据支撑。本文介绍了一款基于YOLOv8、YOLOv5等深度学习框架的铝材缺陷检测模型&#xff0c;该模型使用了大量包含…

力扣刷题TOP101:8.BM10 两个链表的第一个公共结点

目录&#xff1a; 目的 思路 复杂度 记忆秘诀 python代码 目的 两个无环的单向链表&#xff0c;它们的第一个公共结点{{6,7}。 思路 这个任务是找到两个链表的第一个公共结点。可以看作两个心机boy偷偷补课翻车事件。平时嘴上说自己在家玩游戏&#xff0c;实际上背地里都偷…

哪些行业对六西格玛管理方法的需求较大?

六西格玛作为一种追求极致质量和流程优化的管理哲学&#xff0c;自诞生以来&#xff0c;便在多个行业中展现出了巨大的应用价值。该方法通过定义、测量、分析、改进和控制&#xff08;DMAIC&#xff09;五个阶段&#xff0c;帮助企业实现流程的持续改进&#xff0c;提高产品质量…

Spring Web MVC其他扩展(详解下)

文章目录 Spring MVC其他扩展&#xff08;下&#xff09;异常处理异常处理机制声明式异常好处基于注解异常声明异常处理 拦截器拦截器概念拦截器使用拦截器作用位置图解拦截器案例拦截器工作原理源码 参数校验校验概述操作演示SpringMVC自定义参数验证ValueObject(VO) 文件上传…

排序学习整理(1)

1.排序的概念及运用 1.1概念 排序&#xff1a;所谓排序&#xff0c;就是使⼀串记录&#xff0c;按照其中的某个或某些关键字的大小&#xff0c;递增或递减的排列起来的操作&#xff0c;以便更容易查找、组织或分析数据。 1.2运用 购物筛选排序 院校排名 1.3常见排序算法 2.实…

【linux学习指南】Linux进程信号产生(三) 硬件异常除零出错?野指针异常?core文件

文章目录 &#x1f4dd;前言&#x1f320;模拟除0&#x1f309;除0出错&#xff1f;&#x1f309;野指针异常? &#x1f320;⼦进程退出coredump&#x1f309;Core Dump &#x1f6a9;总结 &#x1f4dd;前言 硬件异常被硬件以某种⽅式被硬件检测到并通知内核,然后内核向当前…

【人工智能-科普】图神经网络(GNN):与传统神经网络的区别与优势

文章目录 图神经网络(GNN):与传统神经网络的区别与优势什么是图神经网络?图的基本概念GNN的工作原理GNN与传统神经网络的不同1. 数据结构的不同2. 信息传递方式的不同3. 模型的可扩展性4. 局部与全局信息的结合GNN的应用领域总结图神经网络(GNN):与传统神经网络的区别与…

青藤云安全携手财信证券,入选金融科技创新应用优秀案例

11月29日&#xff0c;由中国信息通信研究院主办的第四届“金信通”金融科技创新应用案例评选结果正式发布。财信证券与青藤云安全联合提交的“基于RASP技术的API及数据链路安全治理项目”以其卓越的创新性和先进性&#xff0c;成功入选金融科技创新应用优秀案例。 据悉&#x…

Python系列 - MQTT协议

Python系列 - MQTT协议 资源连接 MQTT的介绍和应用场景的示例说明 一、什么是MQTT 百度关于MQTT的介绍如下&#xff1a; MQTT(消息队列遥测传输)是ISO 标准(ISO/IEC PRF 20922)下基于发布订阅范式的消息协议。它工作在 TCP/IP协议之上&#xff0c;是为硬件性能低下的远程设…

winform跨线程更新界面

1、报错代码 下面的代码中的this.Text指的是一个winform的窗体&#xff0c;开启Task执行下面的代码以后直接报错&#xff0c;提示线程间操作无效&#xff0c;这是因为在WinForms应用程序中&#xff0c;UI元素&#xff08;如控件&#xff09;通常只能在创建它们的线程&#xff…

Mybatis:CRUD数据操作之多条件查询及动态SQL

Mybatis基础环境准备请看&#xff1a;Mybatis基础环境准备 本篇讲解Mybati数据CRUD数据操作之多条件查询 1&#xff0c;编写接口方法 在 com.itheima.mapper 包写创建名为 BrandMapper 的接口。在 BrandMapper 接口中定义多条件查询的方法。 而该功能有三个参数&#xff0c;…

音视频技术扫盲之预测编码的基本原理探究

预测编码是一种数据压缩技术&#xff0c;广泛应用于图像、视频和音频编码等领域。其基本原理是利用数据的相关性&#xff0c;通过对当前数据的预测和实际值与预测值之间的差值进行编码&#xff0c;从而实现数据压缩的目的。 一、预测编码的基本概念 预测编码主要包括预测器和…

5. langgraph实现高级RAG (Adaptive RAG)

1. 数据准备 from langchain.text_splitter import RecursiveCharacterTextSplitter from langchain_community.document_loaders import WebBaseLoader from langchain_community.vectorstores import Chromaurls ["https://lilianweng.github.io/posts/2023-06-23-age…

自动化配置

自动化配置共享目录 nfs&#xff1a;共享某个目录&#xff0c;共享给哪些客户端&#xff0c;rw&#xff08;读写&#xff09;——rwx&#xff08;给目录权限设置&#xff09;&#xff0c;ro&#xff08;只读&#xff09; 写脚本 1、装包 可以调用仓库之前装包的脚本 &#x…

AtomicIntegerFieldUpdater能否降低内存

1. 代码如下&#xff1a; import java.util.LinkedList; import java.util.List; import java.util.concurrent.atomic.AtomicInteger;public class AtomicIntegerTest {final AtomicInteger startPosition new AtomicInteger(0);final AtomicInteger wrotePosition new Atom…