美工做网站尺寸多少钱,网上买手表哪个网站可以买到正品,没有企业邮箱怎么认证,社交网站开发语言⭐ 作者#xff1a;小胡_不糊涂 #x1f331; 作者主页#xff1a;小胡_不糊涂的个人主页 #x1f4c0; 收录专栏#xff1a;浅谈数据结构 #x1f496; 持续更文#xff0c;关注博主少走弯路#xff0c;谢谢大家支持 #x1f496; Map、Set 1. 搜索树1.1 概念1.2 性能… ⭐ 作者小胡_不糊涂 作者主页小胡_不糊涂的个人主页 收录专栏浅谈数据结构 持续更文关注博主少走弯路谢谢大家支持 Map、Set 1. 搜索树1.1 概念1.2 性能分析 2. 搜索2.1 概念及场景2.2 模型 3. Map的使用3.1 关于Map.EntryK, V的说明3.2 Map的常用方法说明3.4 TreeMap的使用案例 4. Set的说明4.1 常见方法说明4.2 TreeSet的使用案例 1. 搜索树
1.1 概念
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:
若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树
下图就是一个二叉搜索树 进行查找操作
进行插入操作 1. 树为空树 2. 如果树不是空树按照查找逻辑确定插入位置插入新结点 进行删除操作 设待删除结点为 cur, 待删除结点的双亲结点为 parent
cur.left null cur 是 root则 root cur.right cur 不是 rootcur 是 parent.left则 parent.left cur.right cur 不是 rootcur 是 parent.right则 parent.right cur.rightcur.right null cur 是 root则 root cur.left cur 不是 rootcur 是 parent.left则 parent.left cur.left cur 不是 rootcur 是 parent.right则 parent.right cur.leftcur.left ! null cur.right ! null 需要使用替换法进行删除即在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点中再来处理该结点的删除问题 代码实现
public class BinarySearchTree {public static class TreeNode{int val;TreeNode left;TreeNode right;public TreeNode(int val){this.valval;}}public TreeNode root;/*** 查找元素* 最好情况完全二叉树 O(logN)* 最坏情况: 单分支的树 O(N)* param key* return*/public boolean search(int key){TreeNode curroot;while(cur!null){if(cur.valkey){return true;}else if(cur.valkey){curcur.left;}else{curcur.right;}}return false;}//插入元素public boolean insert(int key){if(rootnull){rootnew TreeNode(key);return true;}TreeNode curroot;TreeNode parentnull;while(cur!null){if(cur.valkey){parentcur;curcur.left;}else if(cur.valkey){parentcur;curcur.right;}else{return false;//树中不能有相等元素}}//若curnull判断key与父亲节点的大小if(parent.valkey){parent.leftnew TreeNode(key);}if(parent.valkey){parent.rightnew TreeNode(key);}return true;}//删除元素public void remove(int key){TreeNode cur root;TreeNode parent null;while (cur ! null) {if(cur.val key) {parent cur;cur cur.right;}else if(cur.val key) {parent cur;cur cur.left;}else {//开始删除removeNode(cur,parent);}}}public void removeNode(TreeNode cur,TreeNode parent){//第一种情况if(cur.leftnull){if(curroot){rootcur.right;}if(curparent.left){parent.leftcur.right;}if(curparent.right){parent.rightcur.right;}}//第二种情况if(cur.right null) {if(cur root) {root cur.left;}else if(cur parent.left) {parent.left cur.left;}else {parent.right cur.left;}}//第三种情况if(cur.left!null cur.right!null){TreeNode targetParent cur;TreeNode target cur.right;while (target.left ! null) {targetParent target;target target.left;}cur.val target.val;//删除targetif(targetParent.left target) {targetParent.left target.right;}else {targetParent.right target.right;}}}
}1.2 性能分析
插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。 对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多。
但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 最优情况下二叉搜索树为完全二叉树其平均比较次数为log2(N) 最差情况下二叉搜索树退化为单支树其平均比较次数为N/2 2. 搜索
2.1 概念及场景
Map 和 Set 是一种专门用来进行搜索的容器或者数据结构其搜索的效率与其具体的实例化子类有关。 以前常见的搜索方式有
直接遍历时间复杂度为O(N)元素如果比较多效率会非常慢二分查找时间复杂度为但搜索前必须要求序列是有序的
上述排序比较适合静态类型的查找即一般不会对区间进行插入和删除操作了而现实中的查找比如
根据姓名查询考试成绩通讯录即根据姓名查询联系方式不重复集合即需要先搜索关键字是否已经在集合中 可能在查找时进行一些插入和删除即动态查找那上述两种方式就不太适合了而 Map 和 Set 则是一种适合动态查找的集合容器。
2.2 模型
一般把搜索的数据称为关键字Key和关键字对应的称为值Value将其称之为Key-value的键值对所以模型会有两种
纯 key 模型比如
有一个英文词典快速查找一个单词是否在词典中快速查找某个名字在不在通讯录中
Key-Value 模型比如
统计文件中每个单词出现的次数统计结果是每个单词都有与其对应的次数单词单词出现的次数 而Map中存储的就是key-value的键值对Set中只存储了Key
3. Map的使用 Map是一个接口类该类没有继承自Collection该类中存储的是K,V结构的键值对并且K一定是唯一的不能重复。
3.1 关于Map.EntryK, V的说明
Map.EntryK, V 是Map内部实现的用来存放key, value键值对映射关系的内部类该内部类中主要提供了key, value的获取value的设置以及Key的比较方式。
方法解释K getKey()返回 entry 中的 keyV getValue()返回 entry 中的 valueV setValue(V value)将键值对中的value替换为指定value
Map.EntryK,V并没有提供设置Key的方法
3.2 Map的常用方法说明
方法解释V get(Object key)返回 key 对应的 valueV getOrDefault(Object key, V defaultValue)返回 key 对应的 valuekey 不存在返回默认值V put(K key, V value)设置 key 对应的 valueV remove(Object key)删除 key 对应的映射关系Set keySet()返回所有 key 的不重复集合Collection values()返回所有 value 的可重复集合SetMap.EntryK, V entrySet()返回所有的 key-value 映射关系boolean containsKey(Object key)判断是否包含 keyboolean containsValue(Object value)判断是否包含 value
注
Map是一个接口不能直接实例化对象如果要实例化对象只能实例化其实现类TreeMap或者HashMapMap中存放键值对的Key是唯一的value是可以重复的在TreeMap中插入键值对时key不能为空否则就会抛NullPointerException异常value可以为空。但是HashMap的key和value都可以为空。Map中的Key可以全部分离出来存储到Set中来进行访问(因为Key不能重复)。Map中的value可以全部分离出来存储在Collection的任何一个子集合中(value可能有重复)。Map中键值对的Key不能直接修改value可以修改如果要修改key只能先将该key删除掉然后再来进行重新插入。TreeMap和HashMap的区别
Map底层结构TreeMapHashMap底层结构红黑树哈希桶插入/删除/查找时间复杂度O(log2(N))O(1)是否有序关于Key有序无序线程安全不安全不安全插入/删除/查找区别需要进行元素比较通过哈希函数计算哈希地址比较与覆写key必须能够比较否则会抛出ClassCastException异常自定义类型需要覆写equals和hashCode方法应用场景需要Key有序场景下Key是否有序不关心需要更高的时间性能
3.4 TreeMap的使用案例
public static void TestMap(){MapString, String m new TreeMap();// put(key, value):插入key-value的键值对// 如果key不存在会将key-value的键值对插入到map中,返回nullm.put(林冲, 豹子头);m.put(鲁智深, 花和尚);m.put(武松, 行者);m.put(宋江, 及时雨);String str m.put(李逵, 黑旋风);System.out.println(m.size());//5System.out.println(m);//{宋江及时雨, 李逵黑旋风, 林冲豹子头, 武松行者, 鲁智深花和尚}// put(key,value): 注意key不能为空但是value可以为空// key如果为空会抛出空指针异常//m.put(null, 花名);str m.put(无名, null);System.out.println(m.size());//6// put(key, value):// 如果key存在会使用value替换原来key所对应的value返回旧valuestr m.put(李逵, 铁牛);// get(key): 返回key所对应的value// 如果key存在返回key所对应的value// 如果key不存在返回nullSystem.out.println(m.get(鲁智深));//花和尚System.out.println(m.get(史进));//null//GetOrDefault(): 如果key存在返回与key所对应的value如果key不存在返回一个默认值System.out.println(m.getOrDefault(李逵, 铁牛));//铁牛System.out.println(m.getOrDefault(史进, 九纹龙));//九纹龙System.out.println(m.size());//6//containKey(key)检测key是否包含在Map中时间复杂度O(logN)// 按照红黑树的性质来进行查找// 找到返回true否则返回falseSystem.out.println(m.containsKey(林冲));//trueSystem.out.println(m.containsKey(史进));//false// containValue(value): 检测value是否包含在Map中时间复杂度: O(N)// 找到返回true否则返回falseSystem.out.println(m.containsValue(豹子头));//trueSystem.out.println(m.containsValue(九纹龙));//false// 打印所有的key// keySet是将map中的key防止在Set中返回的for(String s : m.keySet()){System.out.print(s );//宋江 无名 李逵 林冲 武松 鲁智深 }System.out.println();// 打印所有的value// values()是将map中的value放在collect的一个集合中返回的for(String s : m.values()){System.out.print(s );//及时雨 null 铁牛 豹子头 行者 花和尚}System.out.println();// 打印所有的键值对// entrySet(): 将Map中的键值对放在Set中返回了for(Map.EntryString, String entry : m.entrySet()){System.out.println(entry.getKey() --- entry.getValue());}System.out.println();//宋江---及时雨//无名---null//李逵---铁牛//林冲---豹子头//武松---行者//鲁智深---花和尚}4. Set的说明
Set与Map主要的不同有两点Set是继承自Collection的接口类Set中只存储了Key。
4.1 常见方法说明
方法解释boolean add(E e)添加元素但重复元素不会被添加成功void clear()清空集合boolean contains(Object o)判断 o 是否在集合中Iterator iterator()返回迭代器boolean remove(Object o)删除集合中的 oint size()返回set中元素的个数boolean isEmpty()检测set是否为空空返回true否则返回falseObject[] toArray()将set中的元素转换为数组返回boolean containsAll(Collection? c)集合c中的元素是否在set中全部存在是返回true否则返回falseboolean addAll(Collection? extendsE c)将集合c中的元素添加到set中可以达到去重的效果
注意
Set是继承自Collection的一个接口类Set中只存储了key并且要求key一定要唯一TreeSet的底层是使用Map来实现的其使用key与Object的一个默认对象作为键值对插入到Map中的Set最大的功能就是对集合中的元素进行去重实现Set接口的常用类有TreeSet和HashSet还有一个LinkedHashSetLinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。Set中的**Key不能修改**如果要修改先将原来的删除掉然后再重新插入TreeSet中不能插入null的keyHashSet可以。TreeSet和HashSet的区别
Set底层结构TreeSetHashSet底层结构红黑树哈希桶插入/删除/查找时间复杂度O(log2(N)O(1)是否有序关于Key有序不一定有序线程安全不安全不安全插入/删除/查找区别按照红黑树的特性来进行插入和删除1. 先计算key哈希地址 2. 然后进行插入和删除比较与覆写key必须能够比较否则会抛出ClassCastException异常自定义类型需要覆写equals和hashCode方法应用场景需要Key有序场景Key是否有序不关心需要更高的时间性能
4.2 TreeSet的使用案例
public static void TestSet(){SetString s new TreeSet();// add(key): 如果key不存在则插入返回ture// 如果key存在返回falseboolean isIn s.add(apple);s.add(orange);s.add(peach);s.add(banana);System.out.println(s.size());//4System.out.println(s);//[apple, banana, orange, peach]isIn s.add(apple);// add(key): key如果是空抛出空指针异常//s.add(null);// contains(key): 如果key存在返回true否则返回falseSystem.out.println(s.contains(apple));//trueSystem.out.println(s.contains(watermelen));//false// remove(key): key存在删除成功返回true// key不存在删除失败返回false// key为空抛出空指针异常s.remove(apple);System.out.println(s);//[banana, orange, peach]s.remove(watermelen);System.out.println(s);//[banana, orange, peach]IteratorString it s.iterator();while(it.hasNext()){System.out.print(it.next() );}System.out.println();//banana orange peach}
