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

Java:数据结构-MapSet

搜索树

二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树

  • 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
  • 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
  • 它的左右子树也分别为二叉搜索树

搜索二叉树的操作 

1.查找

public class BinarySearchTree {class TreeNode{TreeNode left;TreeNode right;public int val;public TreeNode(int val){this.val=val;}}public TreeNode root;public TreeNode search(int key){TreeNode cur=root;while (cur!=null) {if (cur.val == key) {return cur;} else if (cur.val < key) {cur = cur.right;} else {cur = cur.left;}}return null;}

2.插入

public class BinarySearchTree {class TreeNode{TreeNode left;TreeNode right;public int val;public TreeNode(int val){this.val=val;}}public TreeNode root;
public void insert(int key){if(root==null){root=new TreeNode(key);return;}TreeNode parent=null;TreeNode cur=root;TreeNode node=new TreeNode(key);while (cur!=null){if(cur.val<key){parent=cur;cur=cur.right;}else if(cur.val>key){parent=cur;cur=cur.left;}else {return;  //插入不能插入两个相同的数}}if(parent.val>key){parent.left=node;}else {parent.right=node;}}

3.删除

1. cur.left == null

  • 1. cur 是 root,则 root = cur.right
  • 2. cur 不是 root,cur 是 parent.left,则 parent.left = cur.right
  • 3. cur 不是 root,cur 是 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

3. cur.left != null && cur.right != null

  • 1. 需要使用替换法进行删除,即在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被 删除节点中,再来处理该结点的删除问题 

public class BinarySearchTree {class TreeNode{TreeNode left;TreeNode right;public int val;public TreeNode(int val){this.val=val;}}public TreeNode root;
public void remove(int key){TreeNode parent=null;TreeNode cur=root;while (cur!=null){if(cur.val<key){parent=cur;cur=cur.right;}else if(cur.val>key){parent=cur;cur=cur.left;}else {removeNode(parent,cur);return;}}}public void removeNode(TreeNode parent,TreeNode cur){if(cur.left==null){if(cur==root){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){root=cur.left;}else if(cur==parent.left){parent.left=cur.left;}else {parent.left=cur.left;}}else {TreeNode targetParent=parent;TreeNode target=cur;while (target.left!=null){targetParent=target;target=target.left;}cur.val=target.val;if(targetParent.left==target){targetParent.left=target.right;}else {targetParent.right=target.right;}}}

MapSet 是常用的接口,分别用于表示键值对和不重复的集合

Map

Map.Entry<K, V>Map 接口的一个静态嵌套接口,表示 Map 中的一个键值对(entry)。它提供了对单个键值对的访问,使得可以在遍历 Map 时处理每个条目。K 表示键的类型,V 表示值的类型。

        

import java.util.HashMap;
import java.util.Map;public class Main {public static void main(String[] args) {Map<String, Integer> map = new HashMap<>();map.put("Alice", 25);map.put("Bob", 30);map.put("Charlie", 28);// 遍历 Mapfor (Map.Entry<String, Integer> entry : map.entrySet()) {String key = entry.getKey();Integer value = entry.getValue();System.out.println(key + ": " + value);}}
}

Map的常用的方法及使用

V get(Object key)返回 key 对应的 value
V getOrDefault(Object key, V defaultValue)返回 key 对应的 value,key 不存在,返回默认值
V put(K key, V value)设置 key 对应的 value
V remove(Object key)删除 key 对应的映射关系
Set keySet()返回所有 key 的不重复集合
Collection values()返回所有 value 的可重复集合
Set<Map,Integer<K,V>>  entrySet()返回所有的 key-value 映射关系
boolean containsKey(Object key)判断是否包含 key
boolean containsValue(Object value)判断是否包含 value
public class Test {public static void main(String[] args) {Map<String,Integer> map=new HashMap<>();map.put("h",012);map.put("p",123);map.put("l",234);map.put("k",456);map.put("m",567);map.put("n",789);map.get(123);map.get(234);map.get(234);map.get(567);map.getOrDefault(123,5);map.remove(123);}
}

注:

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删除掉,然后再来进行 重新插入 

Set

Set 是无重复元素的集合。Set 接口的常见实现有 HashSetLinkedHashSetTreeSet。其中,HashSet 无序,LinkedHashSet 按插入顺序保存,TreeSet 则按自然顺序排序。

 

 Set常用的方法及其使用

public class Test {public static void main(String[] args) {Set<Integer> set=new HashSet<>();set.add(123);set.add(234);set.add(345);set.add(456);System.out.println(set);set.isEmpty();set.remove(123);set.remove(234);set.remove(345);set.remove(456);System.out.println(set);}

注:

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可以。

希望能对大家有所帮助!!!!!


http://www.mrgr.cn/news/61816.html

相关文章:

  • 刷代随有感(134):单调栈——下一个更大元素I(难点涉及哈希表与单调栈的结合)
  • 沪深A股上市公司数据报告分析
  • ubuntu openmpi安装(超简单)
  • Spring Cloud 和 Dubbo 的区别
  • 个人学习React Native的实际意义探讨
  • C#自定义事件的案例
  • Deep InfoMax(DIM)(2019-02-ICLR)
  • 7000元投影仪性价比哪款好?当贝F7 Pro脱颖而出
  • 浏览器本地存储和token封装和浏览器导航栏title的笔记
  • 【遗传算法】孤岛模式下的微电网优化调度模型
  • 将多个commit合并成一个commit并提交
  • 探访宇树科技的G1人形机器人:未来消费级机器人的先驱
  • 闲一品交易平台:SpringBoot技术的新境界
  • Win7如何安装支持asp+mdb程序,安装配置IIS
  • [实时计算flink]安全访问最佳实践
  • 新版达梦数据库查看数据库版本信息id_code无法直接显示版本号
  • NewStarCTF2024-Week4-Web-WP
  • 关于我、重生到500年前凭借C语言改变世界科技vlog.12——深入理解指针(2)
  • 【原创分享】详述中间件的前世今生
  • 北斗短报文终端-全星魅北斗手持终端-北斗有源终端
  • 提升RAG系统的回答质量:PDF解析代码详解-PdfParser核心流程
  • ELK之路第三步——日志收集筛选logstash和filebeat
  • Java Lock/AQS ReentrantLock 源码
  • 3DDFA-V3——基于人脸分割几何信息指导下的三维人脸重建
  • IP-guard与Ping32文档加密解决方案对比,选择适合自己的解决方案
  • html设置颜色相关等样式,需要在js层传入相关颜色参数