上海工信部网站,wordpress常用标签,扬州建设投资集团网站,yellow高清免费观看在线上一篇我们聊到了排序相关内容#xff0c;这一篇我们对Map和Set进行一系列说明#xff0c;大家自取。 1.搜索树
1.1 概念
二叉搜索树又称二叉排序树#xff0c;它或者是一棵空树#xff0c;或者是具有以下性质的二叉树:
若它的左子树不为空#xff0c;则左子树上所有节… 上一篇我们聊到了排序相关内容这一篇我们对Map和Set进行一系列说明大家自取。 1.搜索树
1.1 概念
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:
若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树 int[] array {5,3,4,1,7,8,2,6,0,9};
1.2 操作-查找 若根节点不为空
如果根节点key查找key 返回ture如果根节点key 查找key 在其左子树查找如果根节点key 查找key 在其右子树查找
1.3 操作-插入
1. 如果树为空树即根 null直接插入 如果是空树直接插入然后返回ture
2. 如果树不是空树按照查找逻辑确定插入位置插入新结点 1.按照二叉搜索树的性质查找到插入结点的位置
root--5 510 rootroot-right parentrootroot--7 710 rootroot-right parentrootroot--8 810 rootroot-right parentrootroot--9 910 rootroot-right parentroot
2.插入新节点
1.4 操作-删除难点
设待删除结点为 cur, 待删除结点的双亲结点为 parent
1. cur.left null
cur 是 root则 root cur.rightcur 不是 rootcur 是 parent.left则 parent.left cur.rightcur 不是 rootcur 是 parent.right则 parent.right cur.right
2. cur.right null
cur 是 root则 root cur.leftcur 不是 rootcur 是 parent.left则 parent.left cur.leftcur 不是 rootcur 是 parent.right则 parent.right cur.left
3. cur.left ! null cur.right ! null
需要使用替换法进行删除即在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点中再来处理该结点的删除问题
1.5 实现
public class BinarySearchTree {public static class Node {int key;Node left;Node right;public Node(int key) {this.key key;}}private Node root null;/*** 在搜索树中查找 key如果找到返回 key 所在的结点否则返回 null* param key* return*/public Node search(int key) {Node cur root;while (cur ! null) {if (key cur.key) {return cur;} else if (key cur.key) {cur cur.left;} else {cur cur.right;}} return null;} /*** 插入* param key* return true 表示插入成功, false 表示插入失败*/public boolean insert(int key) {if (root null) {root new Node(key);return true;} Node cur root;Node parent null;while (cur ! null) {if (key cur.key) {return false;} else if (key cur.key) {parent cur;cur cur.left;} else {parent cur;cur cur.right;}} Node node new Node(key);if (key parent.key) {parent.left node;} else {parent.right node;} return true;} /*** 删除成功返回 true失败返回 false* param key* return*/public boolean remove(int key) {Node cur root;Node parent null;while (cur ! null) {if (key cur.key) {break;} else if (key cur.key) {parent cur;cur cur.left;} else {parent cur;cur cur.right;}} // 该元素不在二叉搜索树中if(null cur){return false;} /* 根据cur的孩子是否存在分四种情况1. cur左右孩子均不存在2. cur只有左孩子3. cur只有右孩子4. cur左右孩子均存在看起来有四种情况实际情况1可以与情况2或者3进行合并只需要处理是那种情况即可除了情况4之外其他情况可以直接删除情况4不能直接删除需要在其子树中找一个替代节点进行删除*/return true;}
}
1.6 性能分析
插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多。
但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 最优情况下二叉搜索树为完全二叉树其平均比较次数为
最差情况下二叉搜索树退化为单支树其平均比较次数为
1.7 和 java 类集的关系
TreeMap 和 TreeSet 即 java 中利用搜索树实现的 Map 和 Set实际上用的是红黑树而红黑树是一棵近似平衡的二叉搜索树即在二叉搜索树的基础之上 颜色以及红黑树性质验证关于红黑树的内容后序再进行讲解。
2. 搜索
2.1 概念及场景
Map和set是一种专门用来进行搜索的容器或者数据结构其搜索的效率与其具体的实例化子类有关。以前常见的搜索方式有
1. 直接遍历时间复杂度为O(N)元素如果比较多效率会非常慢
2. 二分查找时间复杂度为 ,但搜索前必须要求序列是有序的
上述排序比较适合静态类型的查找即一般不会对区间进行插入和删除操作了而现实中的查找比如
1. 根据姓名查询考试成绩
2. 通讯录即根据姓名查询联系方式
3. 不重复集合即需要先搜索关键字是否已经在集合中
可能在查找时进行一些插入和删除的操作即动态查找那上述两种方式就不太适合了本节介绍的Map和Set是一种适合动态查找的集合容器。
2.2 模型
一般把搜索的数据称为关键字Key和关键字对应的称为值Value将其称之为Key-value的键值对所以模型会有两种
1. 纯 key 模型比如
有一个英文词典快速查找一个单词是否在词典中快速查找某个名字在不在通讯录中
2. Key-Value 模型比如
统计文件中每个单词出现的次数统计结果是每个单词都有与其对应的次数单词单词出现的次数梁山好汉的江湖绰号每个好汉都有自己的江湖绰号
而Map中存储的就是key-value的键值对Set中只存储了Key。
3. Map 的使用 3.1 关于Map的说明
Map是一个接口类该类没有继承自Collection该类中存储的是K,V结构的键值对并且K一定是唯一的不能重复。
3.2 关于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.3 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 对应的映射关系SetK keySet()返回所有 key 的不重复集合CollectionV values()返回所有 value 的可重复集合SetMap.EntryK, V entrySet()返回所有的 key-value 映射关系boolean containsKey(Object key)判断是否包含 keyboolean containsValue(Object value)判断是否包含 value
注意
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删除掉然后再来进行重新插入。
7. TreeMap和HashMap的区别
Map底层结构TreeMapHashMap底层结构红黑树哈希桶插入/删除/查找时间复杂度O(1)是否有序关于Key有序无序线程安全不安全不安全插入/删除/查找区别需要进行元素比较通过哈希函数计算哈希地址比较与覆写key必须能够比较否则会抛出ClassCastException异常自定义类型需要覆写equals和hashCode方法应用场景需要Key有序场景下Key是否有序不关心需要更高的时间性能
3.4 TreeMap的使用案例
import java.util.TreeMap;
import java.util.Map;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());System.out.println(m);// put(key,value): 注意key不能为空但是value可以为空// key如果为空会抛出空指针异常//m.put(null, 花名);str m.put(无名, null);System.out.println(m.size());// 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(史进));//GetOrDefault(): 如果key存在返回与key所对应的value如果key不存在返回一个默认值System.out.println(m.getOrDefault(李逵, 铁牛));System.out.println(m.getOrDefault(史进, 九纹龙));System.out.println(m.size());//containKey(key)检测key是否包含在Map中时间复杂度O(logN)// 按照红黑树的性质来进行查找// 找到返回true否则返回falseSystem.out.println(m.containsKey(林冲));System.out.println(m.containsKey(史进));// containValue(value): 检测value是否包含在Map中时间复杂度: O(N)// 找到返回true否则返回falseSystem.out.println(m.containsValue(豹子头));System.out.println(m.containsValue(九纹龙));// 打印所有的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 );} System.out.println();// 打印所有的键值对// entrySet(): 将Map中的键值对放在Set中返回了for(Map.EntryString, String entry : m.entrySet()){System.out.println(entry.getKey() --- entry.getValue());} System.out.println();
}
4. Set 的说明
Set与Map主要的不同有两点Set是继承自Collection的接口类Set中只存储了Key。
4.1 常见方法说明
方法解释boolean add(E e)添加元素但重复元素不会被添加成功void clear()清空集合boolean contains(Object o)判断 o 是否在集合中IteratorE 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? extends E c)将集合c中的元素添加到set中可以达到去重的效果
注意
1. Set是继承自Collection的一个接口类
2. Set中只存储了key并且要求key一定要唯一
3. TreeSet的底层是使用Map来实现的其使用key与Object的一个默认对象作为键值对插入到Map中的
4. Set最大的功能就是对集合中的元素进行去重
5. 实现Set接口的常用类有TreeSet和HashSet还有一个LinkedHashSetLinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。
6. Set中的Key不能修改如果要修改先将原来的删除掉然后再重新插入
7. TreeSet中不能插入null的keyHashSet可以。
8. TreeSet和HashSet的区别
Set底层结构TreeSetHashSet底层结构红黑树哈希桶插入/删除/查找时间复杂度O(1)是否有序关于Key有序不一定有序线程安全不安全不安全插入/删除/查找区别按照红黑树的特性来进行插入和删除1. 先计算key哈希地址 2. 然后进行插入和删除比较与覆写key必须能够比较否则会抛出ClassCastException异常自定义类型需要覆写equals和hashCode方法应用场景需要Key有序场景下Key是否有序不关心需要更高的时间性能
4.2 TreeSet的使用案例
import java.util.TreeSet;
import java.util.Iterator;
import java.util.Set;
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());System.out.println(s);isIn s.add(apple);// add(key): key如果是空抛出空指针异常//s.add(null);// contains(key): 如果key存在返回true否则返回falseSystem.out.println(s.contains(apple));System.out.println(s.contains(watermelen));// remove(key): key存在删除成功返回true// key不存在删除失败返回false// key为空抛出空指针异常s.remove(apple);System.out.println(s);s.remove(watermelen);System.out.println(s);IteratorString it s.iterator();while(it.hasNext()){System.out.print(it.next() );} System.out.println();
} 内容很长关于Map和Set的内容就这些大家自行理解下一篇我们将继续哈希表相关内容大家有需要的持续关注。
